C语言实现将任意一个整数转换成有限个fibonacci数之和

你的名字 2022-03-08 11:58 198阅读 0赞

**主要思路：**  
1.首先计算一个包含最大数据范围的fibonacci数表；  
2.逆序循环遍历数表，对输入整数进行拆解。

/*--------------------------------------------------------------------
    功能：将任意一个整数转换成几个fibonacci数之和
    可以有多行输入，每行一个整数(本程序范围以10000以内为例)，最后以0结束输入；
    输入示例：
    45
    99
    100
    1000
    10000
    0
    输出示例：
    45 = 34 + 8 + 3
    99 = 89 + 8 + 2
    100 = 89 + 8 + 3
    1000 = 987 + 13
    10000 = 6765 + 2584 + 610 + 34 + 5 + 2
    ---------------------------------------------------------------------
    Author：Zhang Kaizhou
    Date: 2019-3-15 10:26:10
    -------------------------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 50
    #define N 22
    
    int fibonacci_table[MAXSIZE];
    
    typedef struct node{ // 定义一个结点数据类型用于存放原始数据及最终结果
        int num;
        int res[MAXSIZE];
        int len;
        struct node * pnext;
    } Node;
    
    void init_fibonacci_table();
    void compute_res(Node * pnew);
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p);
    void list_print(Node * phead);
    
    int main(){
        Node * phead = NULL, * ptail = NULL;
        int n;
    
        init_fibonacci_table();
        while(scanf("%d", &n), n != 0){
            Node * pnew = (Node *)calloc(1, sizeof(Node));
            pnew->num = n;
            compute_res(pnew);
            list_tail_insert(&phead, &ptail, pnew);
        }
        list_print(phead);
    
        return 0;
    }
    
    void init_fibonacci_table(){ // 初始化fibonacci数表，第21个fibonacci数是10964
        int i;
        fibonacci_table[1] = 1;
        fibonacci_table[2] = 1;
        for(i = 3; i < N; i++){
            fibonacci_table[i] = fibonacci_table[i - 1] + fibonacci_table[i - 2];
        }
        return;
    }
    
    void compute_res(Node * p){ // 计算最终结果
        int i, t = p->num;
        p->len = 0;
        for(i = N - 1; i > 0; i--){
            if(fibonacci_table[i] <= t && t != 0){ // 逆序遍历数表，找到小于等于原始数据的最大fibonacci数
                p->res[p->len++] = fibonacci_table[i];
                t -= fibonacci_table[i]; // 循环遍历，直至差值为0结束
            }
        }
        return;
    }
    
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p){
        if(* pphead == NULL){
            * pphead = p;
            * pptail = p;
        }else{
            (* pptail)->pnext = p;
            * pptail = p;
        }
        return;
    }
    
    void list_print(Node * phead){
        int i;
        while(phead != NULL){
            printf("%d = ", phead->num);
            for(i = 0; i < phead->len - 1; i++){
                printf("%d + ", phead->res[i]);
            }
            printf("%d\n", phead->res[i]);
            phead = phead->pnext;
        }
    }