Preparing NOJ

斐波那契数应用

1000ms 65536K

Description:

知道斐波那契数吗?下面是它的一个定义:

  • F1 = 1
  • F2 = 2
  • Fn+1 = Fn+Fn-1 这里n>1
  •  

    每个正整数x 可写为不同斐波那契数的总和因而意味着存在数k 和数 b1, b2, ..., bk使得x=b1*F1+ ...+ bi*Fi+ ... +bk*Fk, 其中bk = 1bi (1i < k)01。简言之我们可写为 b(x) = (bk, bk-1, ..., b1) 为使表示唯一我们要求对所有i > 1bi * bi-1 = 0

    利用斐波那契数我们可以将公里单位距离 x 转换为相应的英里单位距离 y首先以斐波那契系统表示b(x)写下x。其次b(x)中数字右移一位最后一位删除),得到b(y)。第三b(y)中计算总数来算出 y

    例如42以斐波那契系统表示为(1,0,0,1,0,0,0,0)。第二步,我们通过右移得到 (1,0,0,1,0,0,0)。第三步,我们计算0*1 + 0*2 + 0*3 + 1*5 + 0*8 + 0*13 + 1*21 = 26.

    下面请你写一个程序,根据上述算法将公里转换为英里。

    Input:

    输入第一行包含t,需要转换的距离数目 (0<t<25000)。下面t 行的每一个包含一个整数距离x (2 < x < 25000)公里。

    Output:

    对于每个距离x 公里,输出算出的y 英里。

    Sample Input:

    5
    42
    100
    180
    300
    360

    Sample Output:

    26
    62
    111
    185
    222

    Note:

    本题由旧版NOJ导入,来源:“IBM南邮杯”团队赛2009

    Info

    NOJ

    Provider NOJ

    Code NOJ1113

    Tags

    Submitted 4

    Passed 4

    AC Rate 100%

    Date 04/20/2019 10:03:10

    Related

    Nothing Yet