程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NOJ1113 斐波那契數應用 模擬

NOJ1113 斐波那契數應用 模擬

編輯:C++入門知識

NOJ1113 斐波那契數應用 模擬


題目描述

知道斐波那契數嗎?下面是它的一個定義:
F1 = 1
F2 = 2
Fn+1 = Fn+Fn-1 ,這裡n>1

每個正整數x 可寫為不同斐波那契數的總和,因而意味著存在數k 和數 b1, b2, …, bk,使得x=b1*F1+ …+ bi*Fi+ … +bk*Fk, 其中bk = 1,bi (1≤i < k)為0或1。簡言之,我們可寫為: b(x) = (bk, bk-1, …, b1)。 為使表示唯一,我們要求對所有i > 1,bi * 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.
下面請你寫一個程序,根據上述算法將公裡轉換為英裡。

輸入

輸入第一行包含t,需要轉換的距離數目 (0

輸出

對於每個距離x 公裡,輸出算出的y 英裡。

樣例輸入

5
42
100
180
300
360

樣例輸出

26
62
111
185
222

思路

模擬….本來想直接拿換算公式過來套,發現和題目有誤差 = = 大水題

代碼

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 23;
int f[maxn];
int n;
bool used[maxn];
int main()
{
    f[1] = 1; f[2] = 2;
    for(int i = 3 ; i < maxn ; i ++) f[i] = f[i-1]+f[i-2];
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        int pt;
        fill(used,used+maxn,false);
        for(pt = 1 ; pt < maxn ; pt ++) {
            if(f[pt] > n) break;
        }
        used[pt-1] = true;
        int tmp = f[pt-1];
        for(int i = pt-2 ; i >= 1 ; i --) {
            if(tmp == n) break;
            if(used[i+1]) {
                continue;
            }else {
                if(f[i]+tmp <= n) {
                    tmp += f[i];
                    used[i] = true;
                }
            }
        }
        int ans = 0;
        for(int i = 2 ; i < maxn ; i ++) {
            if(used[i]) ans += f[i-1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved