UVA 10479 The Hendrie Sequence 规律

发布时间：2020-12-13 20:41:21 所属栏目：PHP教程来源：网络整理

导读：题目大意：1个序列，刚开始由0变到了1，接着往后1个个变化下去变化的规则是，如果当前数是k，就在这个序列的最后面加上k－1个0，再加上k＋1 现在问这个序列的第n个数是多少解题思路：这是有规律的，第2的k次方个数恰好是k 如果当前数是k，且k恰好是2的n次

题目大意：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;
            }
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!