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

poj1953 World Cup Noise [1]

(1)ac代码

/*题意：给一个n(n<45)，用0/1组成一个长度为n的串，问没有相邻的1的串有多少？例如：n = 3时，000, 001, 010, 100, 101是可以的，而011, 110, 111不行。我的做法：n<45，有点懵，然后列出n=1~5的结果一看，发现是Fibonacci数列。1   22   33   54   85   13...*/#include 
   
    intmain() {    int n, k, i;    int ans[50] = {
  1, 2, 3};    for( i = 3; i < 45; i++ ) {        ans[i] = ans[i - 1] + ans[i - 2];    }    scanf("%d", &n);    for( i = 1; i <= n; i++ ) {        scanf("%d", &k);        printf("Scenario #%d:\n%d\n\n", i, ans[k]);    }    return 0;}
   

(2)最初版本，递归超时

#include 
   
    intf(int n) {    if( n == 1 ) {        return 2;    }    if( n == 2 ) {        return 3;    }    return f(n - 1) + f(n - 2);}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;}
   

转载地址：http://hpkxi.baihongyu.com/