一个递归问题 - 编程论坛

#2

qq10235692232011-03-25 18:02

怎么了？

#3

pangding2011-03-25 23:07

变化了的 fibonacci 数列。

#4

lucky5635912011-03-26 08:38

回溯法

#5

pcbaichi2011-03-26 11:03

这貌似是递归思想的入门题，斐波那契数列的变形而已

#6

moon_peak2011-03-28 22:03

以下是引用qq1023569223在2011-3-25 18:02:22的发言：

怎么了？

求具体思路啊

#7

moon_peak2011-03-28 22:04

以下是引用pangding在2011-3-25 23:07:59的发言：

变化了的 fibonacci 数列。

具体思路是什么啊？我纠结了好几天了

#8

pangding2011-03-29 15:41

以下是引用moon_peak在2011-3-28 22:04:43的发言：

具体思路是什么啊？我纠结了好几天了

我觉得算是比较无聊的题目。当然难度挺大的，主要是小母牛还得等3年才能生小牛……

有空我想想看吧。

#9

moon_peak2011-03-29 16:09

回复 8楼 pangding

谢谢了

#10

autumn12022011-03-29 17:13

都说不难，怎么没人回答啊，
我先说下我的思路，

int sum = 1; //全局变量，初始为1头小母牛……这称呼真……

void CowBirth(int current_year, int birth_year)  //current只目前是第几年，从1开始，birth_year是此牛的出生于第几年
{
    if( current_year > N)  //N为输入的年数
        return;
    if(current_year - birth_year >= 3)  //成年……
    {
        sum++;//生了
        if(!(current_year%2))   //是只母牛
            CowBirth(current_year + 1, current_year);  //新出生的母牛的分支
    }
    CowBirth(current_year + 1, birth_year);   //等待明年继续……
}

#11

pangding2011-03-29 21:42

果然不是很难，今天上午把公牛母牛的事想复杂了。代码我觉得都不用我写了，我算了前 50 项（不知道为什么非要用递归，这个纯用递归慢的一塌糊涂。）：
括号里的是前一项和后一项的差（换句话说，当前项加上那个括号里的数是下一项），括号里的就是 fibonacci 数列。

1       [0]
1       [0]
1       [1]
2       [1]
3       [1]
4       [2]
6       [2]
8       [3]
11      [3]
14      [5]
19      [5]
24      [8]
32      [8]
40      [13]
53      [13]
66      [21]
87      [21]
108     [34]
142     [34]
176     [55]
231     [55]
286     [89]
375     [89]
464     [144]
608     [144]
752     [233]
985     [233]
1218    [377]
1595    [377]
1972    [610]
2582    [610]
3192    [987]
4179    [987]
5166    [1597]
6763    [1597]
8360    [2584]
10944   [2584]
13528   [4181]
17709   [4181]
21890   [6765]
28655   [6765]
35420   [10946]
46366   [10946]
57312   [17711]
75023   [17711]
92734   [28657]
121391  [28657]
150048  [46368]
196416

之前给的表对错行了，现在修正了。

[ 本帖最后由 pangding 于 2011-3-29 22:43 编辑 ]

#12

pangding2011-03-29 23:09

给个代码吧，感觉帮人帮到底好一点。
虽然后来推了一下，发现不是很难，但还是比较有趣味性。收回之前说的此题无聊的话。

程序代码：

#include <stdio.h>

#define N 20

int f(int n)
{
    if (n <= 0 ) return -1;      // 这个是错误处理吧. 这个函数不接受负数参数.

    switch (n) {
        // 本来这个递推数列, 只要用给出前4项(看后面的用了n-4就知道)
        // 但给出 5 项之后,奇数的情况可以从 4 阶递归, 降成 3阶的.
        // 能显著提高程序的速度, 比较值. 虽然还是很慢吧...
        case 1: case 2: case 3:
                return 1;
        case 4: return 2;
        case 5: return 3;

        default:
            if (n&1) return 3*f(n-2) - f(n-3) - f(n-4);  // 奇数的情况
            else return 2*f(n-1) - f(n-2);              // 偶数的情况.
    }
}

int main(int argc, char *argv[])
{
    int i;
    for (i = 1; i < N; i++)
        printf("%d\n", f(i) );

    return 0;
}

[ 本帖最后由 pangding 于 2011-3-29 23:15 编辑 ]

#13

moon_peak2011-03-30 13:20

回复 12楼 pangding

学习了