c - 不重复 1 的 0-1 序列

Question

我的任务是编写一个程序，其中输入是 2 的指数，输出是序列数(最大 2^n 序列中)，其中彼此之间没有 1。 (n<=50)

例如，输入 3，输出为 5，因为 2^3=8，在 8 种可能性中，唯一可接受的可能性是:(000, 001, 010, 100, 101) 和 (110,011,111) Not Acceptable ，因为有 2 个或多个 1 彼此相邻。

我的程序在 31 之前工作正常，到了 32 就停止工作，我猜是溢出问题。我尝试了 long int 和 unsigned int，但这些似乎都没有帮助。

#include <stdio.h>
#include <math.h>

main(){
    int t,i,n,j,ki;
    scanf("%d",&t);
    for (i=1;i<=t;i++){
            scanf("%d",&n);
            ki=pow(2,n)-(n*(n-1))/2;
            printf("Scenario #%d:\n%d\n\n",i,ki);
    }
    return 0;
}

帮帮我吧。

Answer 1

对于变量 ki :

第 1 步:使用 unsigned long long而不是int .

第 2 步:使用 1<<n而不是pow(2,n) .

第 3 步:使用 llu%而不是%d .

int main()
{
    int t,i,n;
    unsigned long long ki,one=1;
    scanf("%d",&t);
    for (i=1;i<=t;i++)
    {
        scanf("%d",&n);
        ki = (one<<n)-n*(n-1)/2;
        printf("Scenario #%d:\n%llu\n\n",i,ki);
    }
    return 0;
}