您当前位置：首页 > php开源 > php教程 > UVA 10479 The Hendrie Sequence 规律

UVA 10479 The Hendrie Sequence 规律

来源：程序员人生发布时间：2015-05-27 08:20:15 阅读次数：3124次

题目大意：1个序列，刚开始由0变到了1，接着往后1个个变化下去
变化的规则是，如果当前数是k，就在这个序列的最后面加上k－1个0，再加上k＋1
现在问这个序列的第n个数是多少

解题思路：这是有规律的，第2的k次方个数恰好是k
如果当前数是k，且k恰好是2的n次方，那末这个数前面就有n－1个0，n－2个1，n－3个02组合，以此类推
如果要求第n个数是多少，只需要找到n是哪一个k之前的，然后依照上面的规律顺次递归下去便可

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 64
typedef unsigned long long ull;
ull pos[maxn], num[maxn];

void init() {
    num[0] = num[1] = 1;
    for(int i = 2; i < maxn; i++)
        num[i] = num[i - 1] * 2;
    pos[1] =  2;
    for(int i = 2; i < maxn; i++)
        pos[i] = pos[i - 1] * 2;
}

int dfs(ull len, int n) {
    if(len == 0) {
        return n;
    }
    int now = 0;    
    for(int i = n - 1; i > 0; i--) {
        if(len > i * num[now]) 
            len -= i * num[now];
        else {
            if(now == 0 || now == 1)  {
                return now;
            }
            len = (len - 1) % num[now];
            return dfs(len, now);
        }
        now++;
    }
}

int main() {
    init();
    long long n;
    while(scanf("%lld", &n) == 1 && n) {
        if(n == 1) {
            printf("0
");
            continue;
        }
        for(int i = 1; i <= 64; i++) {
            if(n <= pos[i]) {
                printf("%d
", dfs(pos[i] - n, i));
                break;
            }
        }
    }
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 Maven 依赖本地jar包

下一篇 2015年创业中遇到的技术问题：111-120

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点