Прикреплённый файл «fn.py»
Загрузка 1 #!/usr/bin/python
2 # coding: utf-8
3 '''
4 Функция f(n) для целых неотрицательных п определена так:
5
6 f(0)=0; f(1)=1; f(2n)=f(n); f(2n+1)=f(n)+f(n+1)
7
8 Для данного N найти и напечатать f(N). Обязательное условие: N столь велико, что недопустимо заводить массив из N чисел (равно как и массив, длина которого растет с ростом числа N).
9 '''
10
11 def fn(n):
12 '''Решение:
13 Каждое рекуррентное преобразование приводит к вычислению функции
14 всего от двух значений, k и k+1; изменяются только коэффициенты:
15 '''
16 c0, c1 = 1, 0 # f(N)==c0*f(n)+c1*f(n+1)
17 if n<2: return n
18 while n>1:
19 if n%2: # n==2k+1 => c0*(f(k)+f(k+1))+c1*f(k+1)==c0*f(k)+(c0+c1)*f(k+1)
20 c1+=c0
21 else: # n==2k => c0*f(k)+c1*(f(k)+f(k+1))==(c0+c1)*f(k)+c1*k(k+1)
22 c0+=c1
23 n/=2
24 return c0+c1
25
26 print fn(input())
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:35, 0.3 KB) [[attachment:Sav_2_function.py]]
- [получить | показать] (2011-09-26 11:35:35, 1.1 KB) [[attachment:fn.py]]
Вам нельзя прикреплять файлы к этой странице.