aerosmith-ի խոսքերից
ես այդ խնդիրը լուծել եմ C++-ով , բայց եթե մեծ N-եմ վերցնում , շատ դանդաղ ա հաշվում, չնայած կոմպս շատ հզորա, վերցրել էի 10000 թիվը և այն հաշվեց մոտ 10 րոպեում, իսկ ալգորիթմն էլ շատ կոռեկտ էր, դրանից բացի էլ ուրիշ ալգորիթմն չգտա։
վերցնում ես մաքսիմալ չափի մասիվ(խոսքի 10000000).
նրա i-րդ էլեմենտում պետք է գրված լինի i թիվը 1,2,3,4,5 թվերի գումարի տեսքով ներկայացնելու համար եղանակների քանակը:
Այդ մասիվի տարրերը սկսում ենք հերթով լրացնել, օգտագործելով դրանից առաջ ստացված մասսիվի տարրերի արժեքները - դա կոչվում է դինամիկ ծրագրավորում.
Հիմա լուծումը
Կոդ:
...........
int MAX = 10000000;
int a[MAX+1];
a[0] = 1;
for(int i=1; i<=5; i++)
for(int j=1; j<=MAX; j++)
if (j - i >= 0) a[j] += a[j-i];
int N;
cin >> N;
if (N <= MAX) cout << N; else cout << "N is too big";
............
կարող ես փորձել աշխատացնել և ստուգել քո ծրագրի արդյունքների հետ, հնարավոր է, որ ճիշտ չեմ հասկացել կամ ալգորիթմը սխալ եմ գրե
Էջանիշներ