【问题】最初只有1头乳牛，第2年长成1头小牛，第3年成为1头中牛，第4年长成大牛(成年牛)并生下1头乳牛。
假设大牛永远不死且每年产乳牛，问：若干年（例如20年）后总共有多少头牛？
【递推法编程】
考虑用二维数组 niu[i][j]表达第i年牛的数目：
用niu[i][0]表示“乳牛”数目；
用niu[i][1]表示“小牛”数目；
用niu[i][2]表示“中牛”数目；
用niu[i][3]表示“大牛”数目。
初始条件： niu[1][0]=1（代表第1年拥有1头乳牛）
依题意，递推公式应该是这样：
niu[i+1][0] = niu[i][3]+niu[i][2]（明年的乳牛数等于今年的大牛数与中牛数之和）
niu[i+1][1] = niu[i][0]（明年的小牛数等于今年的乳牛数）
niu[i+1][2] = niu[i][1]（明年的中牛数等于今年的小牛数）
niu[i+1][3] = niu[i][2]+niu[i][3]（明年的大牛数等于今年的中牛数加上今年的大牛数）
下面是 VC6.0 C 编程：
#include <stdio.h>
int main( void )
{
    static unsigned long niu[51][4];//可推算50年！
    int iy,year = 20;//此处假设推算第20年的牛总数
    niu[1][0] = 1; //初值
    for(iy=1; iy<year; iy++)
    {
        niu[iy+1][0] = niu[iy][3]+niu[iy][2];//（明年的乳牛数等于今年的大牛数与中牛数之和）
        niu[iy+1][1] = niu[iy][0];//（明年的小牛数等于今年的乳牛数）
        niu[iy+1][2] = niu[iy][1];//（明年的中牛数等于今年的小牛数）
        niu[iy+1][3] = niu[iy][2]+niu[iy][3];//（明年的大牛数等于今年的中牛数加上今年的大牛数）
    }
    printf("第%d年：乳牛%lu头，小牛%lu头，中牛%lu头，大牛%lu头，总共%lu头\n",year,niu[year][0],
    niu[year][1],niu[year][2],niu[year][3],niu[year][0]+niu[year][1]+niu[year][2]+niu[year][3]);
    return(0);
}


[ 本帖最后由 yu_hua 于 2010-10-31 12:18 编辑 ]

// １楼程序的改进版（省略二维数组 niu[ ][ ]）
// 仅用４个变量记录逐年的牛的数目
#include <stdio.h>
int main( void )
{
    int iy,year = 25;    // 此处假设推算第25年的牛总数
    unsigned long niu0=1,niu1=0,niu2=0,niu3=0;  //初值
    for(iy=2; iy<=year; iy++)
    {
        niu3+= niu2;     //（明年的大牛数等于今年的中牛数加上今年的大牛数）
        niu2 = niu1;     //（明年的中牛数等于今年的小牛数）
        niu1 = niu0;     //（明年的小牛数等于今年的乳牛数）
        niu0 = niu3;     //（明年的乳牛数等于明年的大牛数）
        printf("第%2d年：乳牛%5lu头，小牛%5lu头，中牛%5lu头，大牛%5lu头，总共%5lu头\n"
               ,iy, niu0, niu1, niu2, niu3, niu0+niu1+niu2+niu3 );
    }
    return(0);
}

２楼程序的运行结果如下
第 2年：乳牛    0头，小牛    1头，中牛    0头，大牛    0头，总共    1头
第 3年：乳牛    0头，小牛    0头，中牛    1头，大牛    0头，总共    1头
第 4年：乳牛    1头，小牛    0头，中牛    0头，大牛    1头，总共    2头
第 5年：乳牛    1头，小牛    1头，中牛    0头，大牛    1头，总共    3头
第 6年：乳牛    1头，小牛    1头，中牛    1头，大牛    1头，总共    4头
第 7年：乳牛    2头，小牛    1头，中牛    1头，大牛    2头，总共    6头
第 8年：乳牛    3头，小牛    2头，中牛    1头，大牛    3头，总共    9头
第 9年：乳牛    4头，小牛    3头，中牛    2头，大牛    4头，总共   13头
第10年：乳牛    6头，小牛    4头，中牛    3头，大牛    6头，总共   19头
第11年：乳牛    9头，小牛    6头，中牛    4头，大牛    9头，总共   28头
第12年：乳牛   13头，小牛    9头，中牛    6头，大牛   13头，总共   41头
第13年：乳牛   19头，小牛   13头，中牛    9头，大牛   19头，总共   60头
第14年：乳牛   28头，小牛   19头，中牛   13头，大牛   28头，总共   88头
第15年：乳牛   41头，小牛   28头，中牛   19头，大牛   41头，总共  129头
第16年：乳牛   60头，小牛   41头，中牛   28头，大牛   60头，总共  189头
第17年：乳牛   88头，小牛   60头，中牛   41头，大牛   88头，总共  277头
第18年：乳牛  129头，小牛   88头，中牛   60头，大牛  129头，总共  406头
第19年：乳牛  189头，小牛  129头，中牛   88头，大牛  189头，总共  595头
第20年：乳牛  277头，小牛  189头，中牛  129头，大牛  277头，总共  872头
第21年：乳牛  406头，小牛  277头，中牛  189头，大牛  406头，总共 1278头
第22年：乳牛  595头，小牛  406头，中牛  277头，大牛  595头，总共 1873头
第23年：乳牛  872头，小牛  595头，中牛  406头，大牛  872头，总共 2745头
第24年：乳牛 1278头，小牛  872头，中牛  595头，大牛 1278头，总共 4023头
第25年：乳牛 1873头，小牛 1278头，中牛  872头，大牛 1873头，总共 5896头

//如果只求牛的总数，则编程更简单
//首先总结规律

　　　　　　乳牛数　　小牛数　　中牛数　　大牛数
第1年　　　　　１　　　　０　　　　０　　　　０
第2年　　　　　０　　　　１　　　　０　　　　０
第3年　　　　　０　　　　０　　　　１　　　　０
第4年　　　　　１　　　　０　　　　０　　　　１
第5年　　　　　１　　　　１　　　　０　　　　１
第6年　　　　　１　　　　１　　　　１　　　　１
第7年　　　　　２　　　　１　　　　１　　　　２
第8年　　　　　３　　　　２　　　　１　　　　３
第9年　　　　　４　　　　３　　　　２　　　　４
第10年　　　　 ６　　　　４　　　　３　　　　６
。。。。。。。。。。。。。。。。。。。。。。。。。。。
第　k　年的乳牛数、小牛数、中牛数、大牛数分别是：a，b，c，d。则有
第Ｋ+１年的乳牛数、小牛数、中牛数、大牛数分别是：c+d，a，b，c+d；
第Ｋ+２年的乳牛数、小牛数、中牛数、大牛数分别是：b+c+d，c+d，a，b+c+d；
第Ｋ+３年的乳牛数、小牛数、中牛数、大牛数分别是：a+b+c+d，b+c+d，c+d，a+b+c+d；
第Ｋ+４年的乳牛数、小牛数、中牛数、大牛数分别是：a+b+2c+2d，a+b+c+d，b+c+d，a+b+2c+2d；
不难看出：
第Ｋ+４年的乳牛数（a+b+2c+2d）恰好等于第K、K+1、K+2年乳牛数之和；
第Ｋ+４年的小牛数（a+b+c+d）恰好等于第K、K+1、K+2年小牛数之和；
第Ｋ+４年的中牛数（b+c+d）恰好等于第K、K+1、K+2年中牛数之和（但要求d＝a）；
第Ｋ+４年的大牛数（a+b+2c+2d）恰好等于第K、K+1、K+2年大牛数之和（但要求d＝a）。

#include <stdio.h>
int main( void )
{
    int i,year=25; //此处假设推算第25年的牛总数
    unsigned long niu[51]={0,1,1,1};
    for(i=4; i<=year; i++)
    {
        niu[i]=niu[i-2]+niu[i-3]+niu[i-4];
        printf("第%2d年：共有%lu头牛\n",i,niu[i]);
    }
    return(0);
}

果然很牛

//４楼的程序还可以写成递归程式
//但是存在栈空间消耗殆尽的风险
#include <stdio.h>
unsigned long cow(int year)
{
    if(year==0)
       return 0;
    else if(year<=3)//第1、2、3年
       return 1;  //始终只有1头牛
    else
       return cow(year-2)+cow(year-3)+cow(year-4);
}
int main( void )
{
    int year;
    printf("算至第几年？");
    scanf("%d",&year);
    printf("共有%lu头牛。\n",cow(year));
    return 0;
}



[ 本帖最后由 yu_hua 于 2010-10-31 09:25 编辑 ]

你头型是哪个猪头？