ВУЗ:
Составители:
Рубрика:
Формат вывода
файл Output.txt содержит числа N и M.
2. Алгоритм решения.
Алгоритм решения - чисто математический. Рассмотрим
последовательность чисел
А(1), А(2), .. , А(n),..,
где А(k) - число монет в сундуке на k-й год . Из условия задачи
получаем
A(1)=N,
A(2)=N-M,
A(3)=2N-M,
A(4)=3N-2M,
A(5)=5N-3M,
A(6)=8N-5M,
........
A(X)=F(X)N-F(X-1)M=Y,
........
где F(n) - последовательность чисел Фибоначчи , которые
определяются рекуррентными соотношениями
F(1) = 1,
F(2) = 1,
F(K) = F(K-1)+F(K-2), K>2.
Вполне очевидно, что для нахождения M и N достаточно найти
целочисленное решение уравнения
F(X)N - F(X-1)M = Y. (*)
Такое уравнение, вообще говоря, имеет счетное множество
решений. Однако в дан ном случае это множество конечно,
поскольку A(n)>=0 для всех n и
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
