Attachment '2012-11-09.f2n.rec.py'

Download

   1 #!/usr/bin/env python
   2 # coding: utf
   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 n = input("Введите число: ")
  12 
  13 # f(4n) = f(2n) =                                       = 1*f(n) + 0*f(n+1)
  14 # f(4n+1) = f(2n) + f(2n+1) = f(n) + f(n) + f(n+1)      = 2*f(n) + 1*f(n+1)
  15 # f(4n+2) = f(2n+1) = f(n) + f(n+1)                     = 1*f(n) + 1*f(n+1)
  16 # f(4n+3) = f(2n+1) + f(2n+2) = f(n) + f(n+1) + f(n+1)  = 1*f(n) + 2*f(n+1)
  17 # …
  18 # => всегда только 2 значения, отличаются лишь коэффициенты:
  19 # a*f(2n) + b*f(2n+1) = (a+b)*f(n) + b*f(n+1)
  20 # a*f(2n+1) + b*f(2n+2) = a*f(n) + (a+b)*f(n+1)
  21 a,b = 1,0
  22 while n>0:
  23     if n%2:
  24         b+=a
  25     else:
  26         a+=b
  27     n /= 2
  28 print b

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.