程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10479(找規律+遞歸)

uva 10479(找規律+遞歸)

編輯:C++入門知識

uva 10479(找規律+遞歸)


題意:有一個初始序列第一個數字是0,
規律是把前一次推出來的每一個數字x,先接x個0,然後接x+1。
0 –> 1 –> 02 –> 1003 –> 02110004
那麼這個序列就變成0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4…
問序列裡第n個數字是多少,0 < n < 2^63。

題解:首先可以看出這個序列的第2^k個數字一定是k,然後從第2^k個數字往前看一定是緊接著k-1個0,k-2個1 ,k-3個02,k-4個1003…,一直到k-i為1,把n在k-i這個序列的循環節中位置找到,然後遞歸下去直到可以確定它的值。

#include 
#include 
#define ll unsigned long long
ll n, f[65];

void dfs(int r, ll cur, ll len) {
    if (cur >= len - (r - 1)) {
        printf(0
);
        return;
    }
    len = len - (r - 1);
    for (int i = 1, j = r - 2; j > 0; i++, j--) {
        if (cur >= len - j * f[i - 1]) {
            cur = ((cur - (len - j * f[i - 1])) % f[i - 1]) + 1;
            len = f[i - 1];
            if (cur == len)
                printf(%d
, i);
            else
                dfs(i, cur, len);
            return;
        }
        len = len - j * f[i - 1];
    }
}

int main() {
    f[0] = 1;
    for (int i = 1; i < 64; i++)
        f[i] = f[i - 1] * 2;
    while (scanf(%lld, &n) == 1 && n) {
        int l;
        for (int i = 0; i < 64; i++) {
            if (n < f[i]) {
                l = i - 1;
                break;
            }
        }
        if (f[l] == n)
            printf(%d
, l);
        else {
            int r = l + 1;
            dfs(r, n, f[r]);
        }
    }
    return 0;
}

 

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