Нужно было решить задачу методом динамического программирования(решение ниже). Кто-нибудь может рассказать о рекурсивном спуске? Где, что почитать. Потому что все, что я имею сейчас, это небольшой пример ниже.(Так как эту задачу теперь необходимо решить рекурсивным спуском)
UPD: добавил решение с использованием рекурсии, но не уверен, что это можно назвать рекурсивным спуском
Решение методом динамического программирования:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
double minPoly( const string &S, double x )
{
int LEN = S.size();
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';
for ( int run = 2; run <= LEN; run++ )
{
for ( int i = 0, j = i + run - 1; i <= LEN - run; i++, j++ )
{
P[i][j][0] = 10 * P[i][j-1][0] + P[j][j][0];
for ( int deg = 1; deg < run; deg++ )
{
P[i][j][deg] = P[i][i][0] + x * P[i+1][j][deg-1];
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 );
}
int main()
{
string S;
double x;
cout << "Input S: "; cin >> S;
cout << "Input x: "; cin >> x;
cout << "Minimum polynomial is " << minPoly( S, x ) << '\n';
}
С использованием рекурсии:
#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';
}