#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
斐波那契数列。0、1、1、2、3、5、8、13、21、34、……。 前两个数相加之和等于第三个数
'''
from pip._vendor.distlib.compat import raw_input


'''
循环
'''
def test1(num):
    a=0;
    b=1;
    c=0;
    if num==1:
        print("第%d个斐波那契数是%d" %(num,a))
        return 
    if num==2:
        print("第%d个斐波那契数是%d" %(num,b))
        return 
    for i in range(3,num+1):
        c=a+b;
        a=b;
        b=c;
        
        
    print("第%d个斐波那契数是%d" %(num,c))


'''
递归
'''
def test2(num):
    if num==1:
        return 0;
    if num==2:
        return 1
    if num>2:
        return test2(num-1)+test2(num-2)
    
num=raw_input("请输入数字")
num=int(num)
test1(num)
print("第%d个斐波那契数是%d" %(num,test2(num)))