XTUOJ1375Fibonacci-创新互联

XTU OJ 1375 Fibonacci 题目描述

小明非常喜欢 F i b o n a c c i Fibonacci Fibonacci数列，数列为 f 1 = 1 , f 2 = 2 , f n = f n − 1 + f n − 2 f_1=1,f_2=2,f_n=f_n{−}_1+f_n−_2 f1=1,f2=2,fn=fn−1+fn−2。小明想知道对于一个整数 n n n，使得 n = f i + f j + f k n=f_i+f_j+f_k n=fi+fj+fk的组合有多少种？比如 5 = 1 + 1 + 3 5=1+1+3 5=1+1+3 或者 5 = 1 + 2 + 2 5=1+2+2 5=1+2+2,有2种。注意 1 + 2 + 2 1+2+2 1+2+2 和 2 + 1 + 2 2+1+2 2+1+2 被认为是同一种。

创新互联是一家从事企业网站建设、成都网站设计、做网站、行业门户网站建设、网页设计制作的专业网站建设公司，拥有经验丰富的网站建设工程师和网页设计人员，具备各种规模与类型网站建设的实力，在网站建设领域树立了自己独特的设计风格。自公司成立以来曾独立设计制作的站点成百上千家。输入

第一行是一个整数 1 ≤ T ≤ 1000 ) 1≤T≤1000) 1≤T≤1000)，表示样例的个数。
每个样例是一个整数 n ( 3 ≤ n ≤ 109 ) n(3≤n≤109) n(3≤n≤109)。

输出

依次每行输出一个样例的结果，为一个整数。

样例输入

2
3
5

样例输出

1
2

题解：换了一个思路来写，思路就都写在代码注释里了

// 基本思路：
// 1、先将斐波那契数列制表；
// 2、找出所有相加可以等于n的组合，将他们存入二维数组，然后排序
// 3、每次数组有新元素进来都将它们与数组内原有的进行比较，发现有重复这组新元素就跳过，否则就cnt++
#includevoid sort(int num[]){//排序函数
    int i, j;
    for(i = 0; i< 2; i++){//选择排序
        for(j = i + 1; j<= 2; j++){if(num[i]< num[j]){int temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }
}
int cmp(int a[], int b[]){//比较两数组的函数
    int i, flag = 0;
    for(i = 0; i<= 2; i++){if (a[i] != b[i]) {flag = 1;
            break;
        }
    }
    return flag;
}

int main(){int T;
    int n;
    scanf("%d", &T);
    while (T--){scanf("%d", &n);
        int i, j, k, cnt = 0;
        int t = 0, u;
        int f[45] = {0}, s[1000][3] = {0};
        f[1] = f[2] = 1;//这里我是从1开始的
        for (i = 3; i< 45; i++){//斐波那契数列打表，只打到44是因为第44个: 1134903170，第45个: 1836311903，而题目要求n< 10 ^ 9
            f[i] = f[i - 1] + f[i - 2];
        }
        for (i = 1; i< 45; i++){if (f[i] >n) break;
            for (j = 1; j< 45; j++){for (k = 1; k< 45; k++){if (f[i] + f[j] + f[k] == n) {t++;
                        s[t][0] = f[i], s[t][1] = f[j], s[t][2] = f[k];//将f[i], f[j], f[k]存入数组
                        sort(s[t]);//排序
                        for(u = 1; u< t; u++){if (cmp(s[t], s[u]) == 0) goto next;//遇到和之前相同的就跳出
                        }
                        cnt++;
                        next: ;
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：XTUOJ1375Fibonacci-创新互联
本文地址：http://jkwzsj.com/article/djeddc.html

XTUOJ1375Fibonacci-创新互联

其他资讯