Цэрэг

Тавил:
Эгнэж жагссан цэргүүдээс дайнд оролцох цэргүүдийг сонгохдоо аль ч хоёр зэрэгцээ цэргийг 2-ууланг нь сонгохгүй байхаар шийджээ. Тэгвэл N (2<N<10^9) цэргээс сонголт хийж болох нийт боломжийн тоог ол.
[Эх бодлого]

Бодолт:
Динамик програмчлал ашиглан бодъё.
Сүүлийн цэргийг сонгох эсвэл сонгохгүй байх гэсэн 2 боломж бий...
1. Хэрвээ сонгоогүй бол түүнээс өмнөх цэргүүдийг сонгох боломжийн тоотой нь тэнцүү: F(N-1)
2. Харин сонгосон гэж үзвэл зэрэгцээ 2 цэргийг 2-уулангсонгож болохгүй учир түүний өмнөх цэргийг заавал алгасах ёстой. Тиймээс сүүлчийн цэргийг сонгосон тохиолдлын тоо нь: F(N-2)-той тэнцүү. Бас нэг мартаж болохгүй онцгойдуу тохиолдол байгаа нь зөвхөн сүүлчийн цэргийг дангаар нь сонгож болох ганц хувилбар юм. Өөрөөр хэлбэл сүүлчийн цэргээс өмнөх бүх цэргийг сонгохгүй гэсэн үг. Энэ тохиолдол нь F(N-2)-т багтахгүй юм. Тиймээс F(N-2)+1 болно.
Тэгэхлээр: F(N)=F(N-1)+F(N-2)+1 (*) болно.

Бодолт ингээд л болчихгүй. Учир нь N-н авч болох дээд утга нь 10^9 орчим. Тэгэхлээр (*) томьёогоор бодвол Log(N) хугацаа буюу 1 секундэд лав амжихгүй. Тиймээс жаахан сайжруулъя.
(*) томьёо нь бараг л алдарт Фибоначийн тооны аналитик загвар байгаа биз? Тиймээс энэ томьёогоор жаахан оролдвол F(N)=Fib(N+2)-1 болохыг түвэггүй мэдчихнэ. (Fib(N) - N-дүгээр фибоначийн тоо) Иймээс Fib(N)-г хурдан олох арга хайя.

F(N) функцийг бодвол Фибоначийн тоо нэлээн судлагдсан учир Wikipedia жаахан ухахад л:
Fib(2N) = Fib(N)^2 + 2*Fib(N)*Fib(N+1)
Fib(2N+1) = Fib(N)^2 + Fib(N+1)^2 (**)
гэсэн аятайхан томьёог олж болно. (**) Томьёог ашиглан Fib(N+2)-г Log2(N) буюу Log(N) хугацаанд бодно.