Դինամիկ Ծրագրավորում
Դինամիկ Ծրագրավորումը այն «արվեստն» է, որի միջոցով ներկայիս վիճակը (state) կառուցում ենք նախորդ վիճակների հիման վրա: Հաշվարկներ կատարելիս մենք հաճախ օգտագործում ենք մինչ այդ ստացված արժեքները՝ նոր արժեքները ճշգրիտ հաշվելու համար: Դրա շատ լավ օրինակ է Ֆիբոնաչիի թվերը։ Ֆիբոնաչիի թվերը հնարավոր է ստանալ դինամիկ ծրագրավորման միջոցով.
Այսպիսով,
fib(2)-ը հաշվելիս հիմք ենք վերցնում fib(1)-ը և fib(0)-ն, ինչի արդյունքում ստանում ենք fib(2) = 1: Հաջորդ արժեքը, fib(3)-ը, ստացվում է fib(2) + fib(1) = 1 + 1 = 2. Նույն կերպ fib(4) = fib(3) + fib(2) = 2 + 1 = 3, իսկ fib(5) = fib(4) + fib(3) = 3 + 2 = 5, և այդպես շարունակ:Յուրաքանչյուր քայլով մենք հաշվում ենք Ֆիբոնաչիի հաջորդ արժեքը նախորդ արժեքների հիման վրա: Սա կարելի է գրել, օրինակ, ցուցակի միջոցով.
n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])Եթե
n = 5, ծրագիրը կարտածի 5, իսկ եթե n = 7, ապա 13:Այս պահի վիճակը (state) նախորդ վիճակների արժեքները հաշվի առնելով ստանալը հենց Դինամիկ Ծրագրավորման հիմնական գաղափարն է։
💡
Դինամիկ Ծրագրավորումը տեխնիկա է, որով ներկա վիճակը կառուցվում է նախորդ վիճակների հիման վրա:
Առաջադրանք - Տրիբոնաչիի թվերը
Ֆիբոնաչիի թվերով խաղալուց հետո դուք որոշեցիք փորձեր դնել Տրիբոնաչիի թվերի վրա: Դրանք սահմանված են հետևյալ կերպ.
Ձեր խնդիրն է պարզել
n-րդ Տրիբոնաչիի թիվը:Մուտք
Մուտքի միակ տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 30):Ելք
Ելքում պետք է տպել
n-րդ Տրիբոնաչիի թիվը:Օրինակներ
Մուտք | Ելք |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB