Attachment '2012-11-30.fib.py'

Download

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Последовательность чисел Фибоначчи определяется следующим образом: F0 = F1 = 1,
   5 
   6 Fn+1 = Fn+F n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.
   7 '''
   8 
   9 def fibN(n):
  10     '''Решение «в лоб»'''
  11     F0=F1=1
  12     for i in xrange(n-2):
  13         F0,F1=F1,F0+F1
  14     return F1%10
  15 
  16 def fibD(n):
  17     '''Решение с хранением только последних цифр'''
  18     F0=F1=1
  19     for i in xrange(n-2):
  20         F0,F1=F1,(F0+F1)%10
  21     return F1
  22 
  23 def fibP(n):
  24     '''Решение с вычислением периода'''
  25     F0=F1=1
  26     Per=[0]*100
  27     for i in xrange(n-2):
  28         if Per[F0*10+F1]:               # Уже было!
  29             break                       # Можно дальше не считать
  30         Per[F0*10+F1]=F1*10+(F0+F1)%10
  31         F0,F1=F1,(F0+F1)%10
  32     else:
  33         return F1
  34     return fibD(n%i)
  35 
  36 n=input()
  37 #print fibN(n)
  38 print fibD(n)
  39 print fibP(n)

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.