本文共 2252 字，大约阅读时间需要 7 分钟。

poj1953 World Cup Noise [2]

(1)另一种方法，有问题？

/*poj上WA因为最近在学计算机算法分析与设计的递归与分治策略，书中有提到Fibonacci数列，我想到了Fibonacci数列的非递归方式。但是不知道为什么，n<45时，输出和ac代码的输出是一样的，WA，下文有测试代码和输出截图。*/#include 
   
    #include 
    
     intf(int n) {    int a;    a = 1.0 / sqrt(5.0) * (pow((1 + sqrt(5.0)) / 2, n + 2) - pow((1 - sqrt(5.0)) / 2, n + 2));    return a;}intmain() {    int n, k, i, ans;    scanf("%d", &n);    for( i = 1; i <= n; i++ ) {        scanf("%d", &k);        ans = f(k);        printf("Scenario #%d:\n%d\n\n", i, ans);    }    return 0;}
    
   

(2)测试代码

#include 
   
    #include 
    
     intf(int n) {    int a;    a = 1.0 / sqrt(5.0) * (pow((1 + sqrt(5.0)) / 2, n + 2) - pow((1 - sqrt(5.0)) / 2, n + 2));    return a;}intmain() {    int i, mans;    int ans[50] = {
  1, 2, 3};    for( i = 3; i < 45; i++ ) {        ans[i] = ans[i - 1] + ans[i - 2];    }    for( i = 1; i < 45; i++ ) {        mans = f(i);        printf("i = %d, %d =? %d\n", i, ans[i], mans);    }    return 0;}
    
   

(3)难道是因为这样？

/*我请教老师，他说让我取n = 100试一下，谢谢老师。开始我用int直接做了，结果 n = 45 时，就溢出了。后面我又改用long long int试了一次，发现 n = 70时，用数组打表(ac代码)和用非递归的数学公式的结果就开始不一样了。（环境：win10专业版，codeblocks16.01)*/

(4)int测试代码

#include 
   
    #include 
    
     intf(int n) {    int a;    a = 1.0 / sqrt(5.0) * (pow((1 + sqrt(5.0)) / 2, n + 2) - pow((1 - sqrt(5.0)) / 2, n + 2));    return a;}intmain() {    int i, mans;    int ans[100] = {
  1, 2, 3};    for( i = 3; i < 100; i++ ) {        ans[i] = ans[i - 1] + ans[i - 2];    }    for( i = 1; i < 100; i++ ) {        mans = f(i);        printf("i = %d, %d =? %d\n", i, ans[i], mans);    }    return 0;}
    
   

(5)long long int测试代码

#include 
   
    #include 
    
     long longf(int n) {    long long a;    a = 1.0 / sqrt(5.0) * (pow((1 + sqrt(5.0)) / 2, n + 2) - pow((1 - sqrt(5.0)) / 2, n + 2));    return a;}intmain() {    int i;    long long mans;    long long ans[105] = {
  1, 2, 3};    for( i = 3; i < 100; i++ ) {        ans[i] = ans[i - 1] + ans[i - 2];    }    for( i = 1; i < 100; i++ ) {        mans = f(i);        printf("i = %d, %I64d =? %I64d\n", i, ans[i], mans);    }    return 0;}
    
   

(6)可是题目是这样说的

/*The first line contains the number of scenarios.For each scenario, you are given a single positive integer less than 45 on a line by itself.不是说好less than 45的吗？*/