c - 通过 Zeckendorf 定理进行斐波那契编码

Question

有一个代码可以根据 zeckendorf 定理将 x 解释为斐波那契编码。问题是代码对所有输入值都不有效。

示例:

输入 -> 输出

3 -> 100

4 -> 101

7 -> 1010

100 -> 1000010100

然而，当我输入值 34639092 时，输出是 101000010100101000000000100010011010，这是错误的答案(泽肯多夫定理)。

正确答案是101000010100101000000000100010010010，它们几乎相似，只是右边4的位置没有“1”。调试代码的时候可以看到这个“1”一定不会出现在错误的答案中。

我无法理解输出错误答案的原因。我怀疑代码中有错误。

#include <stdio.h>

int main()
{
    long count = -1;
    unsigned long a, b, k, x, supercount = 0,  sumc = 0;
    a = 0;
    b = 1;
    scanf ("%lu", &x);
    k = x;
    if (x == 0){
        printf("0");
    }
    for(;x > 0;){
        while ((k >= 0) && (a <= x-b)){
            a = a + b;
            b = a - b;
            k -= 1;
            count ++;
        }
        x -= a;
        sumc |= 1 << (count-1);
        b = 1;
        a = 0;
        count = -1;
    }
    unsigned long r = sumc;
    while (r != 0){
        r /= 2;
        supercount++;
    }
    int arr[supercount];
    for (int q = 0; q < supercount; q ++){
        if (sumc !=0 ){
            arr[q] = sumc % 2;
            sumc /= 2;
        }
    }
    for (int i = supercount-1; i >=0 ; i--){
        printf ("%d", arr[i]);
    }
}

Answer 1

问题似乎出在这里:

        sumc |= 1 << (count-1);

假设 unsigned long 在你的编译器上转换为 64 位，它应该是:

        sumc |= (unsigned long)1 << (count-1);

仅将 1 位存储到 arr 中的替代版本。与 Visual Studio 一起工作的微小变化。

#include <stdio.h>
typedef unsigned long long uint64_t;
int main()
{
    int arr[96] = {0};  /* fib(93) is max fib() <= 2^64 */
    int count;
    uint64_t a, b, x, y, z;
    scanf("%llu", &x);  /* llu needed for 64 bit input for VS */
    if (x == 0){
        printf("0\n");
        return 0;
    }
    y = x;          /* save x */
    while(x != 0){
        count = 0;  /* count == 0 => fib(2) */
        a = 1;      /* fib(2) == fib(count+2) */
        b = 1;      /* fib(1) == fib(count+1) */
        /* find largest fib(count+2) < x */
        while (a <= x-b){
            count++;    /* count += 1 */
            a = a + b;  /* a = fib(count+2) */
            b = a - b;  /* b = fib(count+1) */
        }
        x -= a;     /* subtract fib(count+2) from x */
        arr[count] = 1;
    }
    count = sizeof(arr)/sizeof(arr[0]);
    while(arr[--count] == 0);
    while(count >= 0){
        printf ("%d", arr[count]);
        count--;
    }
    printf("\n");
    /* check result */
    z = 0;
    a = 1;      /* fib(1) */
    b = 0;      /* fib(0) */
    for(count = 0; count < sizeof(arr)/sizeof(arr[0]); count++){
        a = a + b;  /* a = fib(count+2) */
        b = a - b;  /* b = fib(count+1) */
        if(arr[count] != 0)
            z += a;
    }
    if(y != z)
        printf("mistmatch\n");
    return 0;
}

这个版本更快，因为它只使用一个循环来找到所有总和为 x 的斐波那契数列。

#include <stdio.h>
typedef unsigned long long uint64_t;
int main()
{
    int arr[96] = {0};  /* fib(93) is max fib() <= 2^64 */
    int count;
    uint64_t a, b, x, y, z;
    /* these could be calculated with a one time loop */
    a = 12200160415121876738ull;    /* fib(93) */
    b = 7540113804746346429ull;     /* fib(92) */
    count = 93-2;                   /* not using fib(1) or fib(0) */
    scanf("%llu", &x);  /* llu needed for 64 bit input for VS */
    if (x == 0){
        printf("0\n");
        return 0;
    }
    y = x;          /* save x */
    while(x != 0){                  /* main loop */
        if(x >= a){                 /* if x >= fib(count+2) */
            x -= a;                 /*  update x and arr */
            arr[count] = 1;
        }
        count--;
        b = a - b;                  /* b = fib(count+1) */
        a = a - b;                  /* a = fib(count+2) */
    }
    count = sizeof(arr)/sizeof(arr[0]);
    while(arr[--count] == 0);
    while(count >= 0){
        printf ("%d", arr[count]);
        count--;
    }
    printf("\n");
    /* check result */
    z = 0;
    a = 1;      /* fib(1) */
    b = 0;      /* fib(0) */
    for(count = 0; count < sizeof(arr)/sizeof(arr[0]); count++){
        a = a + b;  /* a = fib(count+2) */
        b = a - b;  /* b = fib(count+1) */
        if(arr[count] != 0)
            z += a;
    }
    if(y != z)
        printf("mistmatch\n");
    return 0;
}