Dynamic programming

[onetwo12]

I can't understand how to realize program with the help of dymamic programming. I understand idea(below) but I can't write code

It is everything that I understand
1)Create dynamic array
2)Every index of that array is equel s[i]. (It's a[i])
3)Then we should fill value s[i] in a[s[i]]x
4)Realize formula to calculat x

for example:

s = 929
x = 18.014878
['929'] 929.0
['9', '29'] 531.4314727387517
['92', '9'] 254.13390533271604
['9', '2', '9'] 2965.8523410115067

MIN: ['92', '9'] 254.13390533271604

[MikeyBoy]

As always, it helps to break this down into tasks.

If I've understood this correctly, you need to:

- Obtain the number S as a string

- Identify every possible set of substrings of S, so that, for example, ['929'] is one such set, ['92', '9'] is another, etc

- For each such set:
- convert the substrings to numbers
- construct the corresponding form of the polynomial, e.g. 929.0, or 92 + (9 * x), etc
- calculate the value of the ponynomial, e.g. 929.0, or 254.13390533271604, etc

- Identify which of those results is the lowest

- Identify which of the sets of substrings corresponds to that lowest result

Have I understood that correctly?

If so, which of those steps is the one you are having trouble with?

Also, what do you mean by "dynamic programming"? Do you mean that your code must dynamically allocate memory on the heap? Or do you mean something else?

EDIT:

It looks as though you got some detailed answers to this question in an older thread of yours:

http://www.cplusplus.com/forum/general/277529/

What was wrong with those answers? And why are you creating multiple threads for the same question, rather than continuing to discuss this in the thread you already had?

[onetwo12]

If I've understood this correctly, you need to

It's true.
I understand this.
I don't understand how to realize it.
I even ask the help from freelance. But no one knows)

[MikeyBoy]

I asked you 7 questions.

You've answered just one of them.

You're not really serious about this, are you?

[keskiverto]

"dynamic programming" means probably: https://en.wikipedia.org/wiki/Dynamic_programming

[onetwo12]

- Obtain the number S as a string

- Identify every possible set of substrings of S, so that, for example, ['929'] is one such set, ['92', '9'] is another, etc

- For each such set:
- convert the substrings to numbers
- construct the corresponding form of the polynomial, e.g. 929.0, or 92 + (9 * x), etc
- calculate the value of the ponynomial, e.g. 929.0, or 254.13390533271604, etc

- Identify which of those results is the lowest

- Identify which of the sets of substrings corresponds to that lowest result

Have I understood that correctly?

I said that it is true

[onetwo12]

"dynamic programming" means probably: https://en.wikipedia.org/wiki/Dynamic_programming

yes

[MikeyBoy]

Ah, OK. Thanks, @keskiverto. I hadn't across that term before - my background isn't in maths. Makes sense that it would involve recursive programming - I was vaguely thinking along those lines when I read the problem description.

[lastchance]

I can't see this being very quick ...

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


double minPoly( const string &S, double x )
{
   int LEN = S.size();

   // P[i][j][d] holds the minimum polynomial of degree d using digits S[i]...S[j] (a "run" of digits of length j-i+1)
   // It is constructed successively from shorter run lengths
   vector< vector< vector<double> > > P( LEN, vector< vector<double> >( LEN, vector<double>( LEN, 0.0 ) ) );

   for ( int i = 0; i < LEN; i++ ) P[i][i][0] = S[i] - '0';                    // Polynomials of run 1 (single-digit constant)

   for ( int run = 2; run <= LEN; run++ )                                      // Successively find minima of different runs
   {                                                 
      for ( int i = 0, j = i + run - 1; i <= LEN - run; i++, j++ )             // This run is digits S[i] ... S[j]
      {
         P[i][j][0] = 10 * P[i][j-1][0] + P[j][j][0];                          // Zero-degree polynomial of this run
         for ( int deg = 1; deg < run; deg++ )                                 // Higher degree polynomials in this run
         {
            P[i][j][deg] = P[i][i][0] + x * P[i+1][j][deg-1];                  // Consider all the possible first "cut" points
            for ( int c = i + 1; c < j - deg + 1; c++ ) P[i][j][deg] = min( P[i][j][deg], P[i][c][0] + x * P[c+1][j][deg-1] );
         }
      }
   }

   return *min_element( P[0][LEN-1].begin(), P[0][LEN-1].begin()+LEN );        // Need the minimum (over all degrees) full run
}


int main()
{
   string S;
   double x;
   cout << "Input S: ";   cin >> S;
   cout << "Input x: ";   cin >> x;
   cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}

Input S: 929
Input x: 18.014878
Minimum polynomial is 254.134

[onetwo12]

I can't see this being very quick ...

I am very grateful to you.
Thanks!

[onetwo12]

I can't see this being very quick ...

Can you explain what is recursive descent?

I have only one example:

#include <iostream>
#include <list>

using namespace std;

list<string> get_subdirs(const string &path)
{
    
}

string path_concat(const string &path, const string &name)
{
  
}

string indent(int level)
{
   
    string result;
    for (size_t i = 0 ; i < level; ++i)
        result += '-';

    return result;
}

void print_directory(const string &path, int level = 1)
{
    list<string> subdirs = get_subdirs(path);

    for (list<string>::iterator it = subdirs.begin(); it != subdirs.end(); ++it)
    {
        string dir = *it;
        cout << indent(level) << dir << endl;
        print_directory(path_concat(path, dir), level + 1);
    }
}

int main(int argc, char *argv[])
{
    print_directory("C:\\");
    return 0;
}

[lastchance]

onetwo12 wrote:

Can you explain what is recursive descent?

No, I haven't got a computer science degree.

However, this is what you get if you build and then traverse your polynomials like a tree, which plausibly might be what is meant.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


double minPoly( const string &S, int i, double P1, double P2, double x, double xpower )
{
   if ( i == S.size() ) return P1 + P2;
   int digit = S[i] - '0';
   double left  = minPoly( S, i + 1, P1     , 10 * P2 + xpower * digit, x, xpower     );
   double right = minPoly( S, i + 1, P1 + P2,   ( xpower * x ) * digit, x, xpower * x );
   return min( left, right );
}


double minPoly( const string &S, double x )
{
   return minPoly( S, 1, 0, S[0] - '0', x, 1 );
}


int main()
{
   string S;
   double x;
   cout << "Input S: ";   cin >> S;
   cout << "Input x: ";   cin >> x;
   cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}

Input S: 929
Input x: 18.014878
Minimum polynomial is 254.134

[onetwo12]

However, this is what you get if you build and then traverse your polynomials like a tree, which plausibly might be what is meant.

As I understand it is that what I need
Thank you very much