Прикреплённый файл «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 из ссылки «[получить]», так как он чисто внутренний и может измениться.

Вам нельзя прикреплять файлы к этой странице.