| 灰色轨迹 回复于：2003-08-03 18:10:50
|
是不是老师出的题目，你拿到这里来找答案了，这样可不好，自己做出来才对
|
| threehair 回复于：2003-08-03 18:12:49
|
呵呵，自己想想吧
思考也是一种乐趣~~~
|
| clion 回复于：2003-08-03 18:35:40
|
是呀，多多思考啊，自己找答案
|
| loveguohuasai 回复于：2003-08-03 19:56:32
|
[quote:2e56f0b86e="灰色轨迹"]是不是老师出的题目，你拿到这里来找答案了，这样可不好，自己做出来才对[/quote:2e56f0b86e]
自己看书的，看到这道题想了很久都想不到，用递归
但是只是有点阻碍。
说说看
|
| aero 回复于：2003-08-03 20:57:53
|
不用递归啊，想想规律用循环最好了。下面的代码调试过了。
[code:1:6568fcdd9f]#include <stdio.h>
int count=0;
int step=1;
int fun(int n){
int sum=0;
while(n){
sum+=step;
count++;
if ( count%4==0 )
step++;
n--;
}
return sum;
}
int main(){
int n;
printf("input n:");
scanf("%d",&n);
printf("result:%d\n",fun(n));
}
[/code:1:6568fcdd9f]
|
| 灰色轨迹 回复于：2003-08-03 21:11:32
|
#include <stdio.h>
int cow(int all_cow, int can_born, int i_born, int ii_born, int iii_born, int year)
{
all_cow += can_born;
can_born += iii_born;
iii_born = ii_born;
ii_born = i_born;
i_born = (all_cow - ii_born - iii_born)>can_born?(all_cow - ii_born - iii_born):can_born;
year--;
if (year == 0)
{
return all_cow;
}
else
{
cow(all_cow, can_born, i_born, ii_born, iii_born, year);
}
}
int main(int argc, char* argv[])
{
if (argc != 2)
{
exit(-1);
}
printf("%d\n", cow(1, 0, 1, 0, 0, atoi(argv[1])));
}
不知道对不对
楼上的兄弟
第100年是不是234467045头牛？
|
| loveguohuasai 回复于：2003-08-03 22:08:00
|
[quote:b1f14fef92="灰色轨迹"]}
不知道对不对
楼上的兄弟
第100年是不是234467045头牛？[/quote:b1f14fef92]
我也差不多做出了，差不多像上面那个。
|
| aero 回复于：2003-08-03 22:31:05
|
呵呵，上面大意了做错了。这回应该对了，用递归做的。刚才仔细想了想，没想出来用非递归做的方法。有一点想法：
如果把这个数列看成是连续的，那么牛增长数量的函数似乎是一个n阶可导的函数。是不是这样的函数就必须用递归做，
用非递归就做不出来呢？
求非递归做法。
仔细想想，这题还是挺难的，不过，也许是我太面了，呵呵。
我的算法太不好了，算了2分钟了100的还没计算出来。
[code:1:7b7bb7561b]
#include <stdio.h>
int inc(int);
int fun(int n){ /*计算第n年有多少牛的函数。*/
if ( n==1 ) return 1;
return inc(n)+fun(n-1);
}
int inc(int n){ /*计算第n年牛的增长率的函数*/
if ( n<5 ) return 0;
else if ( n==5 ) return 1; /*满4周岁的时候开始生小牛，即第5年的增长率为1。*/
else return inc(n-1)+inc(n-4);
}
int main(){
int n;
printf("\ninput n:");
scanf("%d",&n);
printf("result:%d\n",fun(n));
}
[/code:1:7b7bb7561b]
|
| 灰色轨迹 回复于：2003-08-03 22:48:33
|
aero
如果能推导一个公式出来应该可以不用递归了，这对数学基础要求就高了：（
|
| aero 回复于：2003-08-03 23:02:34
|
呵呵，是啊。
对了，楼上的，我用TC2。0编译你的程序，怎么给50多，给100的时候就计算出负的值啊？
还有，你的程序里，第四个年头算的是牛3周岁的时候吧？这样，你第七年的时候就会有6头牛，而我的算法才有4头牛。
我的递归算100，快半小时了，还没结果。
算55的时候就有时间感了，结果是19795288。
还有，你的main函数里调用的atoi函数，是干什么的呀？
今天没时间了，去睡觉，明天继续想。
|
| loveguohuasai 回复于：2003-08-03 23:49:56
|
[quote:b4bd8732a6="灰色轨迹"]aero
如果能推导一个公式出来应该可以不用递归了，这对数学基础要求就高了：（[/quote:b4bd8732a6]
我可以推出一个公式，我就是用公式做的，不过要分开，0<=n<=3;n=4,n=5;n>5这几段，应该可以，后面用一个循环好象都、可以了，我还没有做，应该可以
|
| 小飞爱使申华 回复于：2003-08-04 00:36:53
|
这是我的：
[code:1:a669fc2613]/* 若一头小母牛，从出生起第四个年头开始每年生一头母牛，
* 按此规律，第n年有多少头母牛？
*/
#include <stdio.h>
long num_cow(int n)
{
int i;
long sum = 1;
for (i = 3; i < n; i++)
sum += num_cow(n - i);
return sum;
}
void main()
{
int n;
printf("please input n years: ");
scanf("%d",&n);
printf("Kao: %ld\n", num_cow(n));
}[/code:1:a669fc2613]
题目出的不清楚，这第四年算几岁啊 （这一出生算第几年啊），虚岁是4岁，实足是3岁，我是按实足3岁算的，如果要按实足4岁，把我的code中 i 的初始值由3改为4就行。
唉，搂住，你有什么公式，拿出来大伙瞧瞧，把你的code也贴出来吧，还有，你最好把这个帖子的标题改了，改为（关于母牛的算法问题），这样比较好，一目了然。
|
| loveguohuasai 回复于：2003-08-04 02:06:51
|
[quote:434aeede5e="小飞爱使申华"]
题目出的不清楚，这第四年算几岁啊 （这一出生算第几年啊），虚岁是4岁，实足是3岁，我是按实足3岁算的，如果要按实足4岁，把我的code中 i 的初始值由3改为4就行。
唉，搂住，你有什么公式，拿出来大伙瞧瞧，把..........[/quote:434aeede5e]
应该是这样的：在第四年初生一头，第四年初有两头，这样下去，每头牛在第四年初开始生第一头，大于第四年就继续生。
在第六年开始，第n年的头数为sum=born(k-1)+(k-5)，意思就是第n-1年有a头，n有b头，n+1有c头，那c=b+(n+1-5),b=a+(n-5),
直接来说就是明年减去今年的数量比今年减去年的数量大1。
我用vc:
#include<iostream.h>
long born( unsigned int k)
{
if(k<=5)
return 3;
else
{int sum;
sum=born(k-1)+(k-5);
return sum;
}
}
void main()
{
int n,a;
cin>>n;
a=born(n);
if(n<=3)
{int sum=1;
cout<<"when k<=3,there isonly "<<sum<<"cow!"<<endl;
}
else if(n==4||n==5)
{
int sum=n-2;
cout<<"when k==4||k==5,there is "<<sum
<<" cow!"<<endl;
}
else
cout<<"when the year is"<<n<<",the number of cow is:"
<<a<<endl;
}
如果要看它每一步的计算结果，如下：
#include<iostream.h>
long born( unsigned int k)
{
if(k<=5)
return 3;
else
{int sum;
sum=born(k-1)+(k-5);
cout<<"when the year is"<<n<<",the number of cow is:"
<<a<<endl;
return sum;
}
}
void main()
{
int n,a;
cin>>n;
a=born(n);
if(n<=3)
{int sum=1;
cout<<"when k<=3,there isonly "<<sum<<"cow!"<<endl;
}
else if(n==4||n==5)
{
int sum=n-2;
cout<<"when k==4||k==5,there is "<<sum
<<" cow!"<<endl;
}
else
cout<<"when the year is"<<n<<",the number of cow is:"
<<a<<endl;
}
我算得n=100只是4563头，其实我也觉得不可能有上面这些人算得那么多，因为只是等差（公差只是每一年增加1）增加而已
|
| loveguohuasai 回复于：2003-08-04 02:44:41
|
[quote:a301a797b2="loveguohuasai"]
应该是这样的：在第四年初生一头，第四年初有两头，这样下去，每头牛在第四年初开始生第一头，大于第四年就继续生。
在第六年开始，第n年的头数为sum=born(k-1)+(k-5)，意思就是第n-1年有a头，n有b头，n+1?.........[/quote:a301a797b2]
不是，公式应该是f(n)=f(n-1)+f(n-3)，这次绝对是对的了
|
| loveguohuasai 回复于：2003-08-04 02:59:52
|
[quote:4af61d9e4a="loveguohuasai"]
不是，公式应该是f(n)=f(n-1)+f(n-3)，这次绝对是对的了[/quote:4af61d9e4a]
n=45时得12322413，n=100时要很久不知道为什么。不等了
|
| 小飞爱使申华 回复于：2003-08-04 03:09:06
|
[quote:5878c0a961="loveguohuasai"]
不是，公式应该是f(n)=f(n-1)+f(n-3)，这次绝对是对的了[/quote:5878c0a961]
你这也算递归啊！
|
| 小飞爱使申华 回复于：2003-08-04 03:09:43
|
[quote:562d5f3e45="loveguohuasai"]
不是，公式应该是f(n)=f(n-1)+f(n-3)，这次绝对是对的了[/quote:562d5f3e45]
可你这也是递归啊！只要自己调自己就算了。
|
| loveguohuasai 回复于：2003-08-04 03:10:09
|
[quote:4fefd94953="loveguohuasai"]
n=45时得12322413，n=100时要很久不知道为什么。不等了[/quote:4fefd94953]
#include<iostream.h>
long born( unsigned int k)
{
if(k<4)
return 1;
else
{int sum;
sum=born(k-1)+born(k-3);
return sum;
}
}
void main()
{
int n;
cin>>n;
long a=born(n);
if(n<4)
{int sum=1;
cout<<"when n<4,there is only "<<sum<<" cow!"<<endl;
}
else
cout<<"when the year is"<<n<<",the number of cow is:"
<<a<<endl;
}
n=70就要很久了，是什么 问题？
|
| 小飞爱使申华 回复于：2003-08-04 03:13:25
|
因为有递归，要压栈，很费资源的。
|
| stuff990 回复于：2003-08-04 08:48:54
|
不知道是不是我想的太简单了，大家看看我的（程序来不急写了）
A:分为5类: 1。生的生牛 2。一年生牛 3。2年生牛，4。3年生牛 5多产的牛（一年生一头^_^）
B:每过一年 1－>2 ,2->3, 3->4, 5=5+3; 1=5+3;(牛长大一岁,第5类生出小牛)
c:循环b直到n, 牛的总数就是1+2+3+4+5
|
| loveguohuasai 回复于：2003-08-04 13:03:25
|
[quote:2955690f34="小飞爱使申华"]
可你这也是递归啊！只要自己调自己就算了。[/quote:2955690f34]
我觉得一定是要递归的，不用递归的话我觉得很难。
|
| zlzj2010 回复于：2003-08-04 15:06:23
|
我简单写了个递归算法,不知可以么?
我是按牛第四年开始生的,即第四年应该有5头牛,改了一下,应该没什么问题了!
[code:1:a1975219cb]
long fun(int n){
if (n>3)
return fun(n-1)+fun(n-3);
else if(n==3)
return 1;
else if(n==2)
return 1;
else if(n=1)
return 1;
}
main (){
int n;
printf("input n");
scanf("%d",&n);
printf("the result:%ld",fun(n));
}
[/code:1:a1975219cb]
|
| zlzj2010 回复于：2003-08-04 15:30:56
|
非递归算法:
[code:1:f5aed2889c]
long fun(int n){
long a1=1;
long a2=1;
long a3=1;
long a4=1;
int i=0;
long sum=0;
for (i=4;i<n+1;i++){
a4=a1+a3;
a1=a2;a2=a3;a3=a4;
}
sum=a4;
return sum;
}
main (){
int n;
printf("input n");
scanf("%d",&n);
printf("the result:%ld",fun(n));
}
[/code:1:f5aed2889c]
|
| unicorns 回复于：2003-08-04 16:05:14
|
我的非递归算法，不过不是能带参数的，如果想带参数也可以
那就要用链表了，但是算法是一样的，存储方式不同而已。
[code:1:3ca634ec31]
main (){
unsigned long year[100] ;//每年出生的牛数量
unsigned long ulResult ;
unsigned long sum ;//每年的育龄母牛数量
int i,j ;
sum = 0 ;
for (i = 0; i < 100; i ++){
if (i == 0){
year[i] = 1 ;
continue ;
}
if (i - 3 < 0){
year[i] = 0 ;
}else{
for (j = 0; j <= i -3; j ++)
sum += year[j] ;
year[i] = sum;
sum = 0 ;
}
}
for (i = 0; i < 100; i ++)
ulResult += year[i] ;
printf ("ulResult = [%lu]", ulResult) ;
}
[/code:1:3ca634ec31]
最后结果是234467045
是100年的，用了不到1秒时间，呵呵
|
| unicorns 回复于：2003-08-04 16:12:42
|
还可以优化一下
[code:1:ec3ebab270]
main (){
unsigned long year[100] ;
unsigned long ulResult ;
unsigned long sum ;
int i,j ;
sum = 0 ;
year[0] = 1 ;
year[1] = 0 ;
year[2] = 0 ;
for (i = 3; i < 100; i ++){
sum += year[i - 3] ;
year[i] = sum ;
}
for (i = 0; i < 100; i ++)
ulResult += year[i] ;
printf ("ulResult = [%lu]", ulResult) ;
}
[/code:1:ec3ebab270]
复杂度只有2n
|
| li2002 回复于：2003-08-04 20:09:21
|
好像结果有问题吧，不到100年数值早溢出了，不相信算算60年的数量比100年的多：3，808，901，426 >234，467，045
|
| aero 回复于：2003-08-04 21:53:02
|
我的递归算法：
[code:1:669d8b2851]#include <stdio.h>
int inc(int);
int fun(int n){ /*计算第n年有多少牛的函数。*/
if ( n==1 ) return 1;
return inc(n)+fun(n-1);
}
int inc(int n){ /*计算第n年牛的增长率的函数*/
if ( n<5 ) return 0;
else if ( n==5 ) return 1; /*满4周岁的时候开始生小牛，即第5年的增长率为1。*/
else return inc(n-1)+inc(n-4);
}
int main(){
int n;
printf("\ninput n:");
scanf("%d",&n);
printf("result:%d\n",fun(n));
}
[/code:1:669d8b2851]
我的非递归算法：
[code:1:669d8b2851]#include <stdio.h>
long int fun(int n){
long int i_born=0; /*满1周岁的牛的数目，下面的类似*/
long int ii_born=0;
long int iii_born=0;
long int iv_born=0;
long int can_born=0; /*今年能生产的牛的数目*/
long int sum=1; /*总数*/
int i;
for (i=0;i<n;i++) {
can_born+=iv_born;
sum+=can_born;
iv_born=iii_born;
iii_born=ii_born;
ii_born=i_born;
i_born=can_born;
if (!i) i_born=1;/*第一年的时候有1头牛满一岁*/
}
return sum;
}
int main(){
int n;
printf("\ninput n:");
scanf("%d",&n);
printf("result:%ld\n",fun(n));
}
[/code:1:669d8b2851]
目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目不是等差的增长的，他的增长数率越来越快，其实它的增长速率的增长率也是越来越快的，如果把这些值看成是连续的，应该是一个无限阶可导的函数，并不是等差的。用笔算，把总数和增长率都列出来，算到15年左右就能看出来了。
还有“小飞爱使申华”对loveguohuasai的疑问，我觉得算是递归啊，一种间接递归，怎么不算递归呢？
stuff990的想法是对的，是应该分出小于4岁的牛多大的各有多少，然后计算，这也正是我的非递归算法的思想。但是，如果仔细分析就会发现，牛的总数并不是一个等差数列那样简单。
zlzj2010的做法里有一个致命的错误，并不是fun(n)=fun(n-1)+fun(n-3)，是的确，fun(n-3)的牛在n年可以生牛了，但并不是仅仅这些牛可以生啊，fun(n-1)里也有很大一部分牛可以在第n年继续生小牛啊，你的程序里把这一部分漏掉了。
unicorns的做法是正确的，他是以牛3周岁开始生小牛算的，但是计算100年的确有问题，正如li2002所说，因为年份大的时候每年增长的牛的数量大大超乎了想象，造成了数组的溢出，这一点把year数组打印出来就可以很容易看出来，有很多的负值。如果计算50年就不会造成溢出。我的非递归算法德的结果和unicorns的一样，个人觉得这组结果就是正确的了。如下：（也包括了100年的错误结果，unsigned long int是系统给的最长的数据了，如果要计算准确的话得自己构造数据类型。麻烦了，没做，如果递归的话，也应该是这个错误结果。虽然是错误的，也有一定的参考价值。）
3周岁开始生牛，50年：83316385，100年：234467045
4周岁开始生牛，50年：3951206， 100年：566194214
从两个100年的结果也能看出来溢出的错误。
我的非递归程序的想法和stuff990的想法是类似的，我是以4周岁开始生小牛为准，用了4个变量统计各个时期小于4周岁（不可生育牛）的数量，来计算每年可生育牛的数量和牛的总数的。
而公式，我觉得如果以4周岁开始生小牛为准的话（3周岁开始的可以类推，程序也很好改），应该是：
f(n)=f(n-1)+inc(n); /*去年牛的数量，和今年增长的牛的数量的和*/
inc(n)=inc(n-1)+inc(n-4); /*去年增长的数量（生这些牛的牛今年还可以生），和新成熟的可以生牛的牛的数量（就是4年以前出生的牛）*/
我的非递归算法就是用这两个公式做的，不过计算一个年份的时候要两次陷入inc的递归，复杂度很高，效率很差。觉得“小飞爱使申华”的递归算法很好。“灰色轨迹”的递归算法也很好，我就是在这个递归算法的启示下写出的我的非递归算法。
还有，就是大家贴上来的程序最好能多写点注释，方便阅读和理解。
最后，感谢loveguohuasai提出这么好的问题，也非常荣幸能在这里和大家这么高兴的讨论问题，言辞之中有得罪的地方还请见谅。
|
| 小飞爱使申华 回复于：2003-08-04 22:24:20
|
aero老兄不错，码了不少字，分析得也很有理，好！
我还正愁这么一大堆code，也不知对错，很容易误人子弟的，现在好了，有人出来评判一下，再次感谢。
PS：我对loveguohuasai的疑问，其实是想说这也是一种递归，后来发现表达得有歧意，立马在楼下又加了一句，呵呵。
|
| loveguohuasai 回复于：2003-08-05 02:48:23
|
[quote:3ae9ad03fd="aero"]目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目..........[/quote:3ae9ad03fd]
我想问一下，我知道第一种我是想错了的，第二种也错吗？我觉得不可能错，其实就是一句话可以把它解释清楚：今年的数量是去年的数量加上四年前（就是f(n-3))的数量（因为四年前的牛在今年开始生牛，知道这个算法不是很简单吗？就是要用到递归。我觉得这样的算法绝对是最简单的了。
|
| loveguohuasai 回复于：2003-08-05 02:51:27
|
[quote:a267056a6d="aero"]目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目..........[/quote:a267056a6d]
我没有发觉你也提到那条公式，f(n)=f(n-1)+f(n-3)(或者n-4)，这样本来就是递归了，不用递归简直是犯贱啊 。一个递归，都不用几句就搞定了。
|
| ehewang 回复于：2003-08-05 05:30:26
|
[color=green:a79960e314]#include<stdio.h>
void main()
{
long int f[100];
int i;
f[0]=1;f[1]=1;f[2]=1;
for(i=3;i<100;i++)
f[i]=f[i-1]+f[i-3];
printf("%ld",f[99]);
} [/color:a79960e314]
|
| zlzj2010 回复于：2003-08-05 08:50:10
|
[quote:88093f4e6a="aero"]zlzj2010的做法里有一个致命的错误，并不是fun(n)=fun(n-1)+fun(n-3)，是的确，fun(n-3)的牛在n年可以生牛了，但并不是仅仅这些牛可以生啊，fun(n-1)里也有很大一部分牛可以在第n年继续生小牛啊，你的程序里把这一部分漏掉了[/quote:88093f4e6a]
我觉得地fun(n)年能生小牛的牛的不正是fun(n-3)么？fun(n-1)里是有牛可以生小牛，但它在第n年能生的刚好是fun(n-3)呀，
不只我这思路是否正确？
|
| unicorns 回复于：2003-08-05 09:37:18
|
[quote:474e8fe2d9="aero"]目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目..........[/quote:474e8fe2d9]
PFPF,没想到100就能溢出啊 :oops:
这些牛真的太牛了。
aero也比较牛。呵呵
|
| loveguohuasai 回复于：2003-08-05 09:48:14
|
[quote:aab7cb1754="zlzj2010"]
我觉得地fun(n)年能生小牛的牛的不正是fun(n-3)么？fun(n-1)里是有牛可以生小牛，但它在第n年能生的刚好是fun(n-3)呀，
不只我这思路是否正确？[/quote:aab7cb1754]
你不明白吗？这就是一个总局的想法，抛开其他的只在一个四年内考虑。
“今年的数量等于去年加上四年前的数量“，绝对是这样，否则要递归做什么？
像你说的，（n-1)年也有生牛，但不是在n年啊，在n+2年才生的，意思你也说明白了，在今年（第n年）可以生牛的牛数就是n-3年的数（f(n-3))，不就是f(n)=f(n-1)+f(n-3).绝对没有错
|
| 小飞爱使申华 回复于：2003-08-05 11:48:45
|
对，如果是f(n)=f(n-1)+f(n-3).，那程序更简单了（main函数不变）：
[code:1:13f7ddc4f6]
long num_cow(int n){
return (n < 4) ? 1 : num_cow(n-1) + num_cow(n-3);
}
[/code:1:13f7ddc4f6]
|
| chdonald 回复于：2003-08-05 13:33:55
|
呵呵，分析得太好了，我当时的做法，没放上来，不过也是同样的问题：递归效率低，而且数据溢出，不知道我的结果对不对：30年 39865头
PS：牛不会活100岁的：）
[code:1:475444ad25]#include <stdio.h>
int cow(int n)
{
unsigned long sum = 1, i;
if (n <= 3) sum += 0;
else {
for (i = 4; i <= n; i++)
sum += cow(i-3);
}
return(sum);
}
main()
{
int n;
printf("input n years, from 1\n");
scanf("%d", &n);
printf("total is %ld\n", cow(n));
} [/code:1:475444ad25]
|
| wangz 回复于：2003-08-05 17:09:38
|
[quote:3a86af5c66="chdonald"]呵呵，分析得太好了，我当时的做法，没放上来，不过也是同样的问题：递归效率低，而且数据溢出，不知道我的结果对不对：30年 39865头
PS：牛不会活100岁的：）
#include <stdio.h>
int cow(int n)
{
..........[/quote:3a86af5c66]
30年我只算出328头，怎么差这么多？？
大家算个小一点的，比如10年，看看结果怎样，10年可以手工算出来： 18头。
大家看看自己的算法对不对！
|
| zlzj2010 回复于：2003-08-05 17:24:49
|
[quote:68aad20f4e="wangz"]
30年我只算出328头，怎么差这么多？？
大家算个小一点的，比如10年，看看结果怎样，10年可以手工算出来： 18头。
大家看看自己的算法对不对！[/quote:68aad20f4e]
不对把,10年应该是19头,
30年是39865
|
| loveguohuasai 回复于：2003-08-05 18:12:22
|
[quote:eb6f527fa6="chdonald"][/quote:eb6f527fa6]
n=30,得到39865，对
|
| aero 回复于：2003-08-05 18:37:05
|
真的不好意思，呵呵，昨天没有仔细看。
loveguohuasai和zlzj2010的做法的确是对的。而且f(n)=f(n-1)+f(n-3)的公式的确是太漂亮了，今天仔细又看了看才理解。
我觉得这的确是最简单的递归思想了，呵呵，昨天发的帖子，真是对不起了。
用这个公式递归的话，每一层会陷入两个递归，复杂度很高。但如果利用f(n-1)递归里计算出来的f(n-3)结果的话，写出程序的话就非常漂亮了。
呵呵，再次向loveguohuasai和zlzj2010致歉。
|
| aero 回复于：2003-08-05 18:47:27
|
[quote:d10bb1e5bc="loveguohuasai"]
我没有发觉你也提到那条公式，f(n)=f(n-1)+f(n-3)(或者n-4)，这样本来就是递归了，不用递归简直是犯贱啊 。一个递归，都不用几句就搞定了。[/quote:d10bb1e5bc]
用不用递归，的确是看自己的喜好，但是如果你稍微有点常识的话就会知道，递归是及其耗费系统资源的算法。尤其你上面的公式，如果不加优化就递归的话，更是浪费资源！就这个问题来说，你用大家写的非递归算法算一遍，很容易就体会出速度的差异了。这还只是个小问题，更何况大的问题，大的工程。源代码的精简不是最重要的，目标代码的优化才是真正的目标。而代码优化最重要的就是对算法的优化。
话又说回来，即使这个问题用不用非递归没什么分别。那你就要问自己来这里讨论的目的了。我们不是为了单单解决这样一个个简单的问题，而是为了从这一个个的问题中学到东西，多多思考用不同的算法解决问题。
因此，对于“不用递归简直是犯贱”的说法，很是不受用！！！！我想，技术论坛里讨论技术的帖子里也不应该出现这样的话。
|
| aero 回复于：2003-08-05 18:53:39
|
4周岁开始生小牛：10年：10，30年：6272
3周岁开始生小牛：10年：19，30年：39865
PS：看哪，这就是晚生优生的结果。
|
| flw 回复于：2003-08-05 19:03:30
|
大家其实可以考虑一下另外的一条途径：
如何利用 C++ 的特性而得出与以上讨论的完全不同的另外一种算法？
提示：牺牲空间，换取时间。
|
| miniboot 回复于：2003-08-05 19:12:30
|
第4年开始生。
year0:0=1,1=0,2+=0
year1:0=0,1=1,2+=0
year2:0=0,1=0,2+=1
year3:0=1,1=0,2+=1
year4:0=1,1=1,2+=1
year5:0=1,1=1,2+=2
year6:0=2,1=1,2+=3
year7:0=3,1=2,2+=4
year8:0=4,1=3,2+=6
year9:0=6,1=4,2+=9
the totle cows=19
n=10的结果。总数为19。
n=30 。总数为39865。
|
| 北冥天 回复于：2003-08-05 19:48:01
|
各位大狭
如果溢出
不能用
long double 替换 long int 吗？
是不是long double 算得比较久啊？
|
| loveguohuasai 回复于：2003-08-05 20:48:51
|
[quote:8cf6a7c4e2="aero"]
用不用递归，的确是看自己的喜好，但是如果你稍微有点常识的话就会知道，递归是及其耗费系统资源的算法。尤其你上面的公式，如果不加优化就递归的话，更是浪费资源！就这个问题来说，你用大家写的非递归算法..........[/quote:8cf6a7c4e2]
我的意思是这道题如果不用递归的话，实在很麻烦，
用递归一条公式就搞定，我觉得简单很多
|
| aero 回复于：2003-08-05 21:20:07
|
用递归的话，代码看起来是简洁很多，但是复杂度实在是太高了。
看看我写的非递归算法，找好规律，也不是很麻烦，一个循环就搞定了。
|
| clion 回复于：2003-08-05 21:21:57
|
高明
|
| loveguohuasai 回复于：2003-08-05 21:35:26
|
[quote:bfd9ad964c="aero"]用递归的话，代码看起来是简洁很多，但是复杂度实在是太高了。
看看我写的非递归算法，找好规律，也不是很麻烦，一个循环就搞定了。[/quote:bfd9ad964c]
你不是也用了递归求fun(n-1)吗？
|
| 小飞爱使申华 回复于：2003-08-05 22:04:41
|
[quote:66e43ca403="loveguohuasai"]
你不是也用了递归求fun(n-1)吗？[/quote:66e43ca403]
老大，没有啊，他的非递归算法的确没用递归。
结论：大家都挺厉害的，不错。（不过还是题目写的好，如果改为公牛，可能就没这么多人讨论了，呵呵）
flw老大，就看你的C++算法了，等待ing.
|
| loveguohuasai 回复于：2003-08-05 22:32:40
|
[quote:31fe7a871b="aero"]用递归的话，代码看起来是简洁很多，但是复杂度实在是太高了。
看看我写的非递归算法，找好规律，也不是很麻烦，一个循环就搞定了。[/quote:31fe7a871b]
我怎么都觉得很麻烦。你的非递归算法在哪里？
|
| sdupoplar 回复于：2003-08-05 22:44:30
|
[code:1:65d57a2a88]//////////
#include<vector>
#include<string>
#include<numeric>
#include<iostream>
using namespace std;
bool cow_number(vector<int>& vec,int number)
{
if(number>100||number<0)return false;
else{
for(int n=vec.size();n<number;n++)
vec.push_back(accumulate(vec.begin(),vec.end()-2,0));
return true;
}//end else
return true;
}//end cow_number(......
int main()
{
int a[]={1,0,0,1};
int flag=0;
vector<int> temp_vec(a,a+4);
cout<<"请输入年龄数"<<endl;
cin>>flag;
cow_number(temp_vec,flag);
cout<<"今年牛的中数是:";
cout<<accumulate(temp_vec.begin(),temp_vec.begin()+flag,0)<<endl;
system("pause");
return 0;
}//end int main()
[/code:1:65d57a2a88]
开始随手写的有误，现在可以了。
|
| 小飞爱使申华 回复于：2003-08-05 23:11:39
|
[quote:ba27d43466="loveguohuasai"]
我怎么都觉得很麻烦。你的非递归算法在哪里？[/quote:ba27d43466]
老大，你这眼神也忒。。。，在本贴第2页往下数第13贴，紧接着他的递归算法就是非递归算法。
还有，我说sdupoplar，你的code用[code:1:ba27d43466]..[/code:1:ba27d43466]廓起来排排版好不好，看着晕。
|
| 胡青牛 回复于：2003-08-05 23:59:54
|
好多牛啊~~~哇哈哈哈啊哈
|
| loveguohuasai 回复于：2003-08-06 00:10:39
|
[quote:e17d930cda="sdupoplar"],1}
int flag=0;
vector<int> temp_vec(a,a+4)
cout<<“请输入年龄数”<<endl;
cin>>flag;
cow_number(temp_vec,falg);
cout<<"今年牛的中数是:";
cout<<a..........[/quote:e17d930cda]
为什么要用两个#include<iostream>
我不明白
|
| 胡青牛 回复于：2003-08-06 00:14:10
|
aero 真臭屁1~~~~~~~~~
|
| 小飞爱使申华 回复于：2003-08-06 00:18:37
|
[quote:ad5ed54760="胡青牛"]aero 真臭屁1~~~~~~~~~[/quote:ad5ed54760]
不要随便骂人，请具体说说哪里Chou Pi了，说出理由，俺让你骂。
|
| sdupoplar 回复于：2003-08-06 07:11:55
|
[quote:6c62fefd0d="loveguohuasai"]为什么要用两个#include<iostream>
我不明白 [/quote:6c62fefd0d]
我不小心多写了一个呀！
|
| aero 回复于：2003-08-06 11:53:48
|
楼上的理由，晕~~
^_^,不过,这样的bug谁都犯过,在所难免了.
|
| wangz 回复于：2003-08-06 14:38:04
|
|
| flw 回复于：2003-08-07 10:49:26
|
大家看看我的程序：
[code:1:d16e186820]# include <stdio.h>
class cow
{
public:
static cow *head;
static cow *tail;
static unsigned long cowCount;
int age;
cow *next;
cow()
{
age = 0;
next = ( cow * ) NULL;
}
void grow(void)
{
age++; // 年龄长了一岁。
if ( age >= 4 )
{ // 第四个年头起，下崽。
cow *child = new cow;
tail->next = child;
tail = child;
cowCount++;
}
}
};
unsigned long cow::cowCount = 0;
cow *cow::head = NULL;
cow *cow::tail = NULL;
int main( void )
{
int years = 30;
cow *cows = new cow;
cow::head = cows;
cow::tail = cows;
cow::cowCount = 1;
for( int i=0; i<years; i++ )
for( cow *ptr = cow::head; ptr != NULL; ptr = ptr->next ) // 一年过去了，每牛（注意：不能叫“每人”）给我长一岁。
ptr->grow();
printf( "result: [%ld]\n", cow::cowCount );
ptr = cow::head;
while( ptr != NULL )
{
cow *temp = ptr;
ptr = ptr->next;
delete temp;
}
return 1;
}[/code:1:d16e186820]
|
| 小飞爱使申华 回复于：2003-08-07 11:08:42
|
好，收藏ing。（老大把母牛一大家子都link起来了，呵呵）
|
| flw 回复于：2003-08-07 11:13:03
|
[quote:5b555a9a4d="小飞爱使申华"]好，收藏ing。[/quote:5b555a9a4d]
靠！你多少给些意见好不好？
|
| 小飞爱使申华 回复于：2003-08-07 11:32:11
|
好，意见是：最后内存没有释放，别的不错，O（表示圈阅）。
|
| flw 回复于：2003-08-07 11:34:58
|
[quote:60da069a95="小飞爱使申华"]意见是：最后内存没有释放[/quote:60da069a95]
呵呵。撒了个懒。
|
| chdonald 回复于：2003-08-07 12:01:19
|
许多问题还是用面向对象的方法解答可以简化：）
|
| 小飞爱使申华 回复于：2003-08-07 12:01:45
|
[quote:44312d5e1d="flw"]
呵呵。撒了个懒。[/quote:44312d5e1d]
哇，知道撒懒还不快改，不要误人子弟啊，老大。
|
| sdupoplar 回复于：2003-08-07 12:27:09
|
方法很好，思路比较容易理解，但是不是年多了，就太耗内存了？
|
| flw 回复于：2003-08-07 13:04:21
|
回楼上，情况的确是这样的。
[quote:b23a44405d="flw"]大家其实可以考虑一下另外的一条途径：
如何利用 C++ 的特性而得出与以上讨论的完全不同的另外一种算法？
提示：牺牲空间，换取时间。[/quote:b23a44405d]
所以说是“牺牲空间，换取时间”。
从某种程度上来讲，还是很划算的。
|
| flw 回复于：2003-08-07 13:11:45
|
已经加上了释放内存的那一段了。
|
| kj501 回复于：2003-08-07 13:46:58
|
我用vector重新实现flw的算法，正好考验一下stl的健壮性。
[code:1:cb6ecffebf]
#include<iostream>
#include<vector>
using namespace std;
class Cow;
vector< class Cow *> ver;
class Cow {
int age;
public:
Cow():age(0) {}
void grow(void) {
age++; // 每年长了一岁。
if ( age >= 4 ) { // 第四个年头起生小牛。
ver.push_back(new Cow);
}
}
};
int main()
{
int years = 40;
ver.push_back(new Cow);
for( int i=0; i<years; i++ )
for( int j=0; j<ver.size(); j++)
ver[j]->grow();
//输出结果
cout<<ver.size()<<endl;
//释放内存
for(int i=0; i<ver.size(); i++)
delete ver[i];
}
[/code:1:cb6ecffebf]
算到years=40时，出来的结果是1822473。计算years=50时就狂读硬盘了，所有我没有继续。由此看来stl的容器能够支持的元素个数是很大的，但不知道最大是多少，什么时候能溢出？
|
| HopeCao 回复于：2003-08-07 16:50:50
|
我也做了一个：
[code:1:bdb4ed2a3f]
#include <stdlib.h>
#include <stdio.h>
#define MAX_STRING_LEN 128
static void Add(const char *, const char *, char *);
int main(int argc, char **argv)
{
char szCowCount[MAX_STRING_LEN];
char szLastCount3[MAX_STRING_LEN];
char szCount3[MAX_STRING_LEN];
char szCount2[MAX_STRING_LEN];
char szCount1[MAX_STRING_LEN];
int iYears;
int i;
iYears = atoi(argv[1]);
for (i = 1; i <= iYears; ++i)
{
switch(i)
{
case 1:
case 2:
case 3:
strcpy(szCowCount, "1");
break;
case 4:
strcpy(szCowCount, "2");
break;
case 5:
strcpy(szCowCount, "3");
strcpy(szCount3, "1");
strcpy(szCount2, "1");
strcpy(szCount1, "1");
break;
default:
if (strlen(szCowCount) >= MAX_STRING_LEN)
goto OUT;
strcpy(szLastCount3, szCount3);
Add(szCowCount, szCount3, szCowCount);
//szCowCount = szLastCowCount + szCount3;
Add(szCount3, szCount2, szCount3);
//szCount3 += szCount2;
strcpy(szCount2, szCount1);
strcpy(szCount1, szLastCount3);
break;
}
}
OUT:
printf("Yead:[%d]; Cow number:[%s].\n", iYears, szCowCount);
}
//
// 字符串数据相加.
//
static void Add(const char *pcFirst, const char *pcSecond, char *pcAdd)
{
char szFirstAdd[MAX_STRING_LEN];
char szAdd[MAX_STRING_LEN];
int i;
int iFirst;
int iSecond;
int iAdd;
int iFirstLen;
int iSecondLen;
int iMinLen;
int iOver = 0;
int n;
iFirstLen = strlen(pcFirst);
iSecondLen = strlen(pcSecond);
if (iFirstLen < iSecondLen)
iMinLen = iFirstLen;
else
iMinLen = iSecondLen;
for (i = 0; i < iMinLen; ++i)
{
szFirstAdd[i] = pcFirst[iFirstLen - i - 1] - 48 + pcSecond[iSecondLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
if (iFirstLen > iMinLen)
{
for (; i < iFirstLen; ++i)
{
szFirstAdd[i] = pcFirst[iFirstLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
}
else
{
for (; i < iSecondLen; ++i)
{
szFirstAdd[i] = pcSecond[iSecondLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
}
if (iOver == 1)
szFirstAdd[i++] = '1';
for (n = 0; n < i; ++n)
szAdd[i - n - 1] = szFirstAdd[n];
szAdd[i] = '\0';
strcpy(pcAdd, szAdd);
return;
}
[/code:1:bdb4ed2a3f]
测试了几个跟flw兄的结果一致，不知道数字大了会不会错，请各位测试一下！
要是没有问题的话下次来讨论算法！！！
|
| kj501 回复于：2003-08-07 19:41:05
|
强，不过years只能算到767，768以上出来的数字全都一样。
|
| sdupoplar 回复于：2003-08-07 19:47:23
|
有没有注意，程序最后占了多少内存呢？
|
| aero 回复于：2003-08-07 21:02:28
|
这个版好久没这么热闹了。
一天没来，这么多code了，偶分析不过来了，太面了，落下了，来叫声好。
|
| aero 回复于：2003-08-07 22:46:53
|
看了后来的，又评论了一点，臭屁一下。
flw的算法的确是非常新颖，想法也非常的有创意。
但是，偶还是觉得不如偶的非递归算法好（嘻嘻）。
flw的算法中为每头牛创建了一个节点，异常庞大的内存消耗自不必说，偶觉得创建节点的开销也是蛮大的，因为毕竟不是原有的数据类型。在者，在每一年的循环中都要历遍一次链表，这个也是不小的一笔时间开销吧？
当然，这个用链表的想法应该是这个帖子里最有创意的想法了吧，版主到底是版主。
HopeCao的想法也很好，用字符串代替原有的数据类型以拓展可以求解的空间，可以计算到700多，想法非常好。
|
| 小飞爱使申华 回复于：2003-08-07 23:54:10
|
我模仿flw老大的C++版，做了一个java版本，给大家找找乐，有兴趣请看：
[url]http://www.chinaunix.net/forum/viewtopic.php?p=882955#882955[/url]
还有，flw老大，你的code还有小问题，释放内存那段，ptr没有声明过吧。应改为Cow *ptr = cow::head;
|
| 海滨 回复于：2003-08-08 02:31:06
|
一头牛，引来兄弟无数呀
哈哈哈哈哈哈哈哈：）
|
| 小飞爱使申华 回复于：2003-08-08 02:44:16
|
[quote:ad77f4bb38="海滨"]一头牛，引来兄弟无数呀
哈哈哈哈哈哈哈哈：）[/quote:ad77f4bb38]
不不，关键是“母”牛。
|
| 海滨 回复于：2003-08-08 05:18:56
|
有这等事
很严重呀，要是改成“美女”真不知道会是什么样的呢~！
|
| HopeCao 回复于：2003-08-08 08:54:55
|
修改了一下：
[code:1:4ee5af127b]
#include <stdlib.h>
#include <stdio.h>
#define MAX_STRING_LEN 1024
static void Add(const char *, const char *, char *);
int main(int argc, char **argv)
{
char szCowCount[MAX_STRING_LEN];
char szLastCount3[MAX_STRING_LEN];
char szCount3[MAX_STRING_LEN];
char szCount2[MAX_STRING_LEN];
char szCount1[MAX_STRING_LEN];
int iYears;
int i;
iYears = atoi(argv[1]);
for (i = 1; i <= iYears; ++i)
{
if (i == 1)
{
strcpy(szCowCount, "1");
strcpy(szCount3, "0");
strcpy(szCount2, "0");
strcpy(szCount1, "1");
}
else
{
if (strlen(szCowCount) >= MAX_STRING_LEN)
goto OUT;
strcpy(szLastCount3, szCount3);
Add(szCowCount, szCount3, szCowCount);
Add(szCount3, szCount2, szCount3);
strcpy(szCount2, szCount1);
strcpy(szCount1, szLastCount3);
}
}
OUT:
printf("Yead:[%d]; Cow number:[%s].\n", i - 1, szCowCount);
}
//
// 字符串数据相加.
//
static void Add(const char *pcFirst, const char *pcSecond, char *pcAdd)
{
char szFirstAdd[MAX_STRING_LEN];
char szAdd[MAX_STRING_LEN];
int i;
int iFirst;
int iSecond;
int iAdd;
int iFirstLen;
int iSecondLen;
int iMinLen;
int iOver = 0;
int n;
iFirstLen = strlen(pcFirst);
iSecondLen = strlen(pcSecond);
if (iFirstLen < iSecondLen)
iMinLen = iFirstLen;
else
iMinLen = iSecondLen;
for (i = 0; i < iMinLen; ++i)
{
szFirstAdd[i] = pcFirst[iFirstLen - i - 1] - 48 + pcSecond[iSecondLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
if (iFirstLen > iMinLen)
{
for (; i < iFirstLen; ++i)
{
szFirstAdd[i] = pcFirst[iFirstLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
}
else
{
for (; i < iSecondLen; ++i)
{
szFirstAdd[i] = pcSecond[iSecondLen - i - 1] + iOver;
if (szFirstAdd[i] - 48 >= 10)
{
szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
iOver = 1;
}
else
iOver = 0;
}
}
if (iOver == 1)
szFirstAdd[i++] = '1';
for (n = 0; n < i; ++n)
szAdd[i - n - 1] = szFirstAdd[n];
szAdd[i] = '\0';
strcpy(pcAdd, szAdd);
return;
}
[/code:1:4ee5af127b]
看来大家都没有仔细看我的程序。
|
| HopeCao 回复于：2003-08-08 09:01:01
|
原来算法前面已经有了！！！
白忙了这么久！
|
| helloggx 回复于：2003-08-08 15:39:16
|
#include<math.h>
#include<iostream>
main()
{
int i,j,m;
int years=50; //50 年
static unsigned long cow[41]; //牛只能活40年,分别为一岁的牛,二岁的牛...
static unsigned long cowCount;
for(i=1;i<41;i++)
{
cow[i]=0;
}
cow[1]=5;
for (m=1;m<years+1;m++)
{
cowCount=0;
for(i=4;i<21;i++) //牛到20岁就不生了
{
cowCount=cowCount+cow[i];
}
for(i=40;i>1;i--)
{
cow[i]=cow[i-1];
}
cow[1]=cowCount;
}
cowCount=0;
for(i=1;i<41;i++)
{
cowCount=cowCount+cow[i];
}
cout<<cowCount<<endl;
|
| yhzz 回复于：2003-08-08 17:01:36
|
[code:1:1bab5950cb]#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <string>
#include <vector>
using namespace std;
int cowgo(int num)
{
int i;
int cow=0,baby1,baby2,baby3;
int temp;
cow=baby2=baby3=0;
baby1=1;
for (i=num;i>0;i--)
{
temp=baby3;
baby3=baby2;
baby2=baby1;
baby1=cow;
cow=cow+temp;
}
return cow+baby1+baby2+baby3;
}
main()
{
int i;
scanf("%d",&i);
cout<<cowgo(i)<<endl;
}
[/code:1:1bab5950cb]
|
| aero 回复于：2003-08-08 19:21:21
|
呵呵，看来也没有什么新的算法了，继续关注。
|
| helloggx 回复于：2003-08-08 19:49:54
|
#include<math.h>
#include<iostream>
main()
{
int i,j,m;
int years=50; //50 年
float cow[41]; //牛只能活40年,分别为一岁的牛,二岁的牛...
float cowCount; //cow[],cowcolunt用float才能算到100,否则到70几就有益出了
for(i=1;i<41;i++)
{
cow[i]=0;
}
cow[1]=5;
for (m=1;m<years+1;m++)
{
cowCount=0;
for(i=4;i<21;i++) //牛到20岁就不生了
{
cowCount=cowCount+cow[i];
}
for(i=40;i>1;i--)
{
cow[i]=cow[i-1];
}
cow[1]=cowCount;
}
cowCount=0;
for(i=1;i<41;i++)
{
cowCount=cowCount+cow[i];
}
cout<<cowCount<<endl;
|
| hoxide 回复于：2003-08-08 23:51:02
|
[code:1:0d5149f3f9]
#include<math.h>
#include<iostream.h>
#define ARRAY_LONG 50
#define CHILD_AGE 4
#define MOTHER_AGE 20
#define DIE_AGE 40
//考虑到将来处理更大的规模,所以用模板
template<class NUM>
class cow
{
public:
cow(int y) {year=y;}
int work();
int show_population()
{
cout<<result;
return 0;
}
private:
int year;
NUM result;
int dec_pa(int &pa)
{
//循环数组退格
pa += (ARRAY_LONG -1);
pa %= ARRAY_LONG;
return pa;
}
};
template <class NUM>
int cow<NUM>::work()
{
int pa_zero,
pa_child,
pa_mother,
pa_die;
NUM count_child,
count_mother,
count_grannie;
NUM *cyc_queue = new NUM(ARRAY_LONG);
for (int j =0 ;j<ARRAY_LONG ;j++)
{
cyc_queue[j] = 0;
}
//c++ 自动对数据初始化为零值
cyc_queue[1] = 1;
pa_zero = 1; //为了语义上的统一性，数组从1开始计数
pa_child = CHILD_AGE;
pa_mother = MOTHER_AGE;
pa_die = DIE_AGE;
count_child = 1;
count_mother = 0;
count_grannie =0;
//开始计数
for (int i=0 ;i<year ;i++)
{
//新的一年长一岁
//循环数组向后退
dec_pa(pa_zero);
dec_pa(pa_child);
dec_pa(pa_mother);
dec_pa(pa_die);
//年老的母牛死了:(
count_grannie -= cyc_queue[pa_die];
//到年龄的母牛不能生了,变奶奶了
count_grannie += cyc_queue[pa_mother];
count_mother -= cyc_queue[pa_mother];
//小牛变成大母牛
count_mother += cyc_queue[pa_child];
count_child -= cyc_queue[pa_child];
//小牛
cyc_queue[pa_zero] = count_mother;//一只母牛生一只小牛
count_child += cyc_queue[pa_zero];//新生的小牛加进去
}
//最后一共有几头?
//小牛+母牛+老牛
result = count_child + count_mother + count_grannie;
return 0;
}
main()
{
int year;
cout<<"please input year:";
cin>>year;
cow<unsigned long> foo(year);
foo.work();
foo.show_population();
return 0;
}
[/code:1:0d5149f3f9]
大家帮我排排错吧，反正结果和大家的程序不一样
|
| aero 回复于：2003-08-09 12:05:59
|
呵呵，好，还考虑到了牛的养老问题。
|
| 小飞爱使申华 回复于：2003-08-09 12:17:55
|
faint, 怎么题目都变了，牛还有节育的，升天的，再下去要考虑10岁那年母牛改嫁，一年生了两。
|
| hoxide 回复于：2003-08-09 13:55:39
|
那就更有趣了
比如每个年龄的牛按一定比例死掉，
小牛夭折，高龄产妇，
最重要的是公牛跑到哪儿去了，
母牛会自交啊？
|
| aero 回复于：2003-08-09 19:04:01
|
在下去就变成养牛场的模拟软件了，是不是算一个项目啊。^_^
|
| hoxide 回复于：2003-08-09 20:17:45
|
算阿，很有趣的。等有钱了我买个农场，就用这个。
大家努力啊
|
| topmint 回复于：2003-08-11 19:00:01
|
[code:1:657c8b031d]START
LEA GR1,1 ;f(n-1)
LEA GR2,1 ;f(n-2)
LEA GR3,1 ;f(n-3)
LEA GR4,3 ;年数 or 结果
ST GR4,Y
LOOP LD GR4,Y
CPA GR4,YEAR
JPZ FINISH
LEA GR4,1,GR4
ST GR4,Y
ST GR1,D
ADD GR3,D
ST GR3,D
LEA GR3,0,GR2
LEA GR2,0,GR1
LD GR4,D
LEA GR1,0,GR4
JMP LOOP
ST GR4,NUM
FINISH EXIT
YEAR DC 10
Y DS 1
D DS 1
NUM DS 1
END[/code:1:657c8b031d]
|
| pupilzeng 回复于：2003-08-11 22:55:49
|
[code:1:f09bed4099]
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int
main(int argc, char** argv)
{
if(argc != 2)
{
exit(1);
}
int year = atoi(argv[1]);
vector<long long> count(year, 1);
for ( int i = 2; i < year; i ++)
count[i + 1] = count[i] + count[i - 2];
cout << "In the " << year <<"th year, there are(is) "
<< count[year - 1] << " cows\n";
}
[/code:1:f09bed4099]
关键就在那个for循环。
就是f(n) = f(n - 1) + f(n - 3) 的实现。[/code]
|
| pupilzeng 回复于：2003-08-11 23:05:59
|
[code:1:551fe2e06b]
#include <deque>
#include <cstdlib>
#include <iostream>
using namespace std;
int
main(int argc, char** argv)
{
if(argc != 2)
{
cout << "just accept 1 parameter\n";
exit(1);
}
int year = atoi(argv[1]);
deque<long long> count(4, 1);
count.pop_back();
for ( int i = 2; i < year; i ++)
{
count.push_back(count[0] + count[2]);
count.pop_front();
}
cout << "In the " << year <<"th year, there are(is) "
<< count[1] << " cows\n";
}
[/code:1:551fe2e06b]
同样是n级别的时间复杂度，但是空间复杂度变为1，deque的空间只有4.
不知道这个在时间上跟上一个有什么区别，不过估计也很难反映出来测试到117时就溢出了。
|
| sylpjx 回复于：2003-08-14 15:14:17
|
真是不知道母牛是否可以活一百岁，还有是不是真的每四年一头，不符合实际吗。
|
| quanliking 回复于：2003-08-21 03:54:12
|
看了大伙的高见，受益非浅，但总觉得解释的还不是很清楚，偶尔在用麻将牌摆弄了一下，有了自己的想法，忍不住要写一下。
疯狂的奶牛(母牛产仔问题)
首先做个约定,假定母牛在每年的春季(年初)才生育，该年的其它时间不生育(吃草，做胎教 :)；新出生的小宝宝，要过满 4 周岁(整 4 年)，才长大成人，从事传宗接代工作。
先来看看最初的这头母牛(鼻祖，怎么来的，无性繁殖吗？)，出生在公元 xxx 年初,为了简化统计，假定为 00 年(届),那么从 00 年初到 01 年初，刚好过了一整年，以此类推：到了 04 年初，整 4 年，此时该母牛怀胎十月，顺利产下一子(是 mm 噢)，用图表表示：
[code:1:568487ff01]
year 4
0 *
1
2
3
4 *
[/code:1:568487ff01]
星号表示每年增加(出生)牛口，总牛口为 2，有生育能力的牛口为 1 。
我们来看看第 8 年初的情况：
[code:1:568487ff01]
year 8
0 *
1
2
3
4 *
5 *
6 *
7 *
8 * *
[/code:1:568487ff01]
很容易看出第 8 年出生的数目比第 7 年多 1 ，原因是 04 届已经到了生产年龄，总牛口为 7, 有生育能力者为 2(也就是说下一年至少有 2 个生产力。
继续看第 9 年初的情况：
[code:1:568487ff01]
year 9
0 *
1
2
3
4 *
5 *
6 *
7 *
8 * *
9 * * *
[/code:1:568487ff01]
这次大伙都能猜到为什么了，原因是除了 00 和 04 届，05 届也开始生育了，它们是以后的新生产力。
最后让我们看一副抓图，以便找出规律来：
|
| | quanliking 回复于：2003-08-21 04:29:50
| 当到了第 19 个年头，很容易看出规律来了，请看 19 这个位置：
红线圈出来这部分是相隔 4 届，即 15 届的牛所生；圈前这部分是 15 届的前几届牛所生，数目刚好等于 18 届出生的牛口。
如果 n 表示年数，f(n) 表示该年出生的牛口：
[code:1:8579137553]
1 ( n = 0 )
f(n) = 0 ( 0 <= n <= 3 )
f(n-1) + f(n-4) ( n >= 4 )
[/code:1:8579137553]
如果要计算总牛数 ( 假定牛长生不老，青春永驻 )， count 为牛总数：
[code:1:8579137553]
int count = 0;
for ( i = 0; i <= n; i++)
count += f(i)
[/code:1:8579137553]
下面是我写的程序源码：
[code:1:8579137553]
#include <stdio.h>
#define YEAR 1000 // 计算到 1000 年,自行修改
int main( char argc, char **argv)
{
int year;
if ( argc == 1)
year = 10; // 默认计算 10 年
else {
if ( argc >= 2 && atoi(argv [1]) >= 0 && atoi(argv [1]) <= YEAR)
{
year = atoi(argv [1]);
printf ("year: %d\n", year);
}
else {
printf ("年数错误，请保持在 0 ~ 1000 范围内的整数\n");
return 0;
}
}
int born [YEAR] = {0}; // 存储该年出生奶牛数目
unsigned long count = 0; // 到 n 年为止全部母牛总数
int i;
for ( i = 0; i <= year; i++) { // 计算该年出生奶牛数目
if ( i <= 3 )
born [i] = (i == 0) ? 1 : 0;
else
born [i] = born [i - 1] + born [ i -4 ];
}
for ( i = 0; i <= year; i++) {
printf ("%3d ", i);
int j;
for ( j = 0; j < born[i]; j++)
printf ("*");
printf ("\n");
count += born [i];
}
printf ("total cow number after %d year: %lu\n", year, count);
return 0;
}
[/code:1:8579137553]
我这里用了数组 born [] ，用来存储每年出生的牛口，当然如果年数比较大，还应该把 int born [] 改成 long born [] 需要占用一定的内存，但不大，获得的是很快的计算速度。
用数组保存结果，能方便奶牛的主人查看每年的出生记录，以及牛的牛龄，比如规定节育年限，应该比较容易能写出来。
上面的分析，不敢保证正确，因为结果和有些人不同。
| | db_info 回复于：2003-08-21 12:04:04
| 不会吧，第100年时，第1头母牛总共生了97，第2头母牛总共生了94，第3头母牛总共生了91，依此，所以100年绝对不会超过1到100的和5050=（100+1）*100/2哦，最多也只是97+94+91+...+1=(97+1)*32/2=736头，不知是否认同？
| | flw 回复于：2003-08-21 12:18:11
| 呵呵。我的答案不一定是效率最高的，但是理解起来绝对是最简单的，而且结果也绝对是正确的。凡是和我的结果不同的，当然就是错的。
| | quanliking 回复于：2003-08-21 15:39:11
| [quote:2e7e823e92="db_info"]不会吧，第100年时，第1头母牛总共生了97，第2头母牛总共生了94，第3头母牛总共生了91，依此，所以100年绝对不会超过1到100的和5050=（100+1）*100/2哦，最多也只是97+94+91+...+1=(97+1)*32/2=736头，不知是否认同?..........[/quote:2e7e823e92]
不好意思，完全错误。考虑得也太不够周到了。
第 1 头母牛生了 97 没错；
第 2 头母牛生了 94 也没错；
第 3 头母牛生了 91 就大错特错了。
原因是第 3 头是第 1 头所生，出生只比第 2 头晚了 1 年，所以到了 100 年，它应该生了 93 头。下面得“绝对”两字就站不住脚了。
而且照这个思路是越往下就越复杂了，不妨花点时间看看我的分析。
| | quanliking 回复于：2003-08-21 16:55:48
| [quote:b446fe0497="flw"]呵呵。我的答案不一定是效率最高的，但是理解起来绝对是最简单的，而且结果也绝对是正确的。凡是和我的结果不同的，当然就是错的。[/quote:b446fe0497]
刚才编译了一下老大用 c++ 链表写的,里面有一处小问题，我用的是 g++ ，改正过来了，同时改动了一下 main () 好让它接受参数，不要介意，以下是改好的代码：
[code:1:b446fe0497]
// 修改自 cow_flw.cpp
# include <stdio.h>
# include <iostream>
# define YEAR 100
class cow
{
public:
static cow *head;
static cow *tail;
static unsigned long cowCount;
int age;
cow *next;
cow()
{
age = 0;
next = ( cow * ) NULL;
}
void grow(void)
{
age++;
if ( age >= 4 )
{
cow *child = new cow;
tail->next = child;
tail = child;
cowCount++;
}
}
};
unsigned long cow::cowCount = 0;
cow *cow::head = NULL;
cow *cow::tail = NULL;
int main( char argc, char **argv)
{
int years;
if ( argc == 1)
years = 10; // 默认计算 10 年
else {
if ( argc >= 2 && atoi(argv [1]) >= 0 && atoi(argv [1]) <= YEAR)
{
years = atoi(argv [1]);
printf ("year: %d\n", years);
}
else {
printf ("年数错误，请保持在 0 ~ 100 范围内的整数\n");
return 0;
}
}
cow *cows = new cow;
cow::head = cows;
cow::tail = cows;
cow::cowCount = 1;
cow *ptr = cow::head; // 指针 ptr 在此处定义
for( int i=0; i<years; i++ )
for( ptr = cow::head; ptr != NULL; ptr = ptr->next ) // 这里改动了一下，指针定义我拿到了嵌套外部
ptr->grow();
printf( "result: [%ld]\n", cow::cowCount );
ptr = cow::head;
while( ptr != NULL )
{
cow *temp = ptr;
ptr = ptr->next;
delete temp;
}
return 1;
}
[/code:1:b446fe0497]
flw 兄的约定是整整 3 周岁，就是 365 * 3 天，而我的是 4 周岁，这样的话，我的代码调整如下(修改两个数字)：
[code:1:b446fe0497]
#include <stdio.h>
#define YEAR 1000 // 计算到 1000 年,自行修改
int main( char argc, char **argv)
{
int year;
if ( argc == 1)
year = 10; // 默认计算 10 年
else {
if ( argc >= 2 && atoi(argv [1]) >= 0 && atoi(argv [1]) <= YEAR)
{
year = atoi(argv [1]);
printf ("year: %d\n", year);
}
else {
printf ("年数错误，请保持在 0 ~ 1000 范围内的整数\n");
return 0;
}
}
int born [YEAR] = {0}; // 存储该年出生奶牛数目
unsigned long count = 0; // 到 n 年为止全部母牛总数
int i;
for ( i = 0; i <= year; i++) { // 计算该年出生奶牛数目
if ( i <= 2 ) // 这里由 3 改成 2
born [i] = (i == 0) ? 1 : 0;
else
born [i] = born [i - 1] + born [ i -3 ]; // 这里由 4 改成 3
}
for ( i = 0; i <= year; i++) {
printf ("%3d ", i);
int j;
for ( j = 0; j < born[i]; j++)
printf ("*");
printf ("\n");
count += born [i];
}
printf ("total cow number after %d year: %lu\n", year, count);
return 0;
}
[/code:1:b446fe0497]
计算结果和 flw 的结果刚好相差一年，也就是说：
我的 10 年是 28 头；
flw 11 刚好 28 头；
以此类推，除此之外完全一样。
我思考了一下，主要是对第一年的理解可能有所不同，我是算每年的年初产牛，具体谁对谁错，还没细想。
这里提到效率问题：
用链表操作，越到下面，效率低的可怜，要是计算 100 年，怕是等不了，内存不够大，估计可能还会死机，不过这里用到 c++ 面象对象的思想还是很不错的。
算法其实很简单，就两个循环，一个计算每年出生的牛数，另外一个用来统计总的牛数。理解上，只要你照我写的耐心看一下，只会比链表来的简单。
| | quanliking 回复于：2003-08-22 00:02:56
| 如果约定 3 周岁开始生育：
每年农场出生的牛数为 f(n)：
[code:1:eb1bcda0bc]
1 , n = 0
f(n) = 0 , n = 1 || 2
f(n - 1) + f(n - 3) n >= 3
[/code:1:eb1bcda0bc]
[code:1:eb1bcda0bc]
f(0) = 1
f(1) = 0
f(2) = 0
f(3) = f(2) + f(0)
f(4) = f(3) + f(1)
f(5) = f(4) + f(2)
......
f(n-1) = f(n-2) + f(n-4)
f(n) = f(n-1) + f(n-3)
把左边一列相加得到母牛的总数目：
Sum(n) = f(0) + f(1) +...+ f(n)
等号右边第一列相加,把最后一列也加起来，刚好得到以下式子：
Sum(n) = Sum(n - 1) + Sum(n - 3)
加上初始条件:
Sum(0) = Sum(1) = Sum(2) = 1
[/code:1:eb1bcda0bc]
我想这个式子应该不陌生了,跟楼上几位朋友推出来的一样吧！
可以这样理解：
n-1 年的母牛总数到了 n 年，一头没少，全活得好好的，而且它们中处于生育年龄母牛们还生了不少小宝宝，数目刚好等于相隔三年前母牛的总数目。
| | aero 回复于：2003-08-22 08:25:04
| 我晕，现在这帖子还被顶了上来，也没有什么新的算法，还是原先讨论过的算法在不停的贴代码。
| | 小飞爱使申华 回复于：2003-08-22 08:29:48
| [quote:be73690d52="aero"]我晕，现在这帖子还被顶了上来，也没有什么新的算法，还是原先讨论过的算法在不停的贴代码。[/quote:be73690d52]
呵呵，就这帖子，比清茶斋还热闹。
| | great3779 回复于：2003-08-26 10:01:02
| 这是递归调用的好题啊。
是精华！
| | 山山水水 回复于：2003-08-27 05:01:02
| 大家好，我是新手（C&linux）近来看此题，工作闲暇与几位同事闲聊得出一结果：16637075746565964头牛！！！有点夸张了吧？？？
对题目首先进行假设处理：每头牛寿命无限
解题思路：首先，同样受前帖子解题思想的影响考虑用递归，但发现就单纯从牛繁殖且用年份度量的话，很短时间后，牛的数目的增长已经不单单是线性指数关系了所以先否定了递归调用+牛繁殖且用年份度量的解题思路。
其次，对核裂变公式的推敲更加认识到用线性时间变量去度量以高阶指数形式改变数量的解题思路关键在公式的形成，因为再好、再超前的硬件也经不住N（线性时间变量）的考验！！！
所以认识到就此题所设，及我自身数学水平有限而采用以下方法与步骤：
1、不采用线性时间变量，而采用牛的生产周期时间做变量（关键）；
2、用电子表格，划分4个阶段（列，注：牛的生产周期）罗列100年（行），观察数据变化推出基本可行公式；
3、用for循环实现。
附程序（草）
main()
{
double a,a1,a2,a3;/*分别为：生产牛，1年牛，2年牛，3年牛*/
double temp,sum;
int i;
a=1;a1=1;a2=1;a3=1;/*第6年（共4头牛）各周期的牛*/
for(i=7;i<=100;i++)
{
a=(a+a3);
a1=a;
temp=a2;
a2=(a-a3);
a3=temp;
}
sum=a+a1+a2+a3;
printf("sum=%f\n",sum);
}
完
| | duisburg 回复于：2003-08-27 21:57:20
| 刚刚来到这儿，就看到这么一篇帖子，受益匪浅！
以后会常来，还请各位老大关照！
| | blazewater 回复于：2003-08-31 15:45:09
| 性能最好，最容易理解的解决方法上场了！！
#define AGE_1 0 //一岁的牛
#define AGE_2 1 //二岁的牛
#define AGE_3 2 //三岁的牛
#define AGE_4 3 //大于或者等于四岁的牛，可以生牛的牛；
int main(void)
{
int cow[4]；
int years = 0;
//初始化，只有一头一岁的母牛；
cow[AGE_1] = 1;
cow[AGE_2] = 1;
cow[AGE_3] = 1;
cow[AGE_4] = 1;
printf("input Years? ");
scanf("%d", years);
for (int i=1; i<=years; i++)
{
//三岁的猪都长了一岁，所以放到四岁的数组中来；
cow[AGE_4] += cow[AGE_3];
//2岁的猪也长了一岁，放到三岁的数组中来；
cow[AGE_3] = cow[AGE_2];
//1岁的猪也长了一岁，放到二岁的数组中来；
cow[AGE_2] = cow[AGE_3];
//1岁的猪是由今年四岁的和大于四岁的猪生的；
cow[AGE_1] = cow[AGE_4];
}
printf("all cow is : %d", cow[0] + cow[1] + cow[2] + cow[3]);
}
不好意思，一直以为是猪，应该是牛，呵呵。。。
其他的几种不大让我满意的解决方法：
solution1:
#include <stdio.h>
#include <stdlib.h>
int total_n(int year)
{
if (year <= 3) return 1;
if (year == 4) return 2;
return total_n(year-1)+total_n(year-3);
}
int main(void)
{
printf("50 years go by, total pigs: %d\n", total_n(50));
return 1;
}
solution2:
#include <iostream.h>
struct pig
{
int age;
// int mother;
int children;
};
int count_pigs(int year)
{
int i, j, k, m;
int count, count_tmp;
pig pigs[102400000];
//init;
i=j=k=m=0;
count=count_tmp=1;
for (i=0; i<10240; i++)
{
pigs[i].age=0;
// pigs[i].mother=0;
pigs[i].children=0;
}
//years go by...;
for(i=1; i<=year; i++)
{
cout << "现在是第" << i << "年:" << endl;
for (j=0; j<count_tmp; j++)
{
pigs[j].age++;
// cout << " 第" << j << "头猪的年龄是:" << pigs[j].age << endl;
// cout << " 她共生了" << pigs[j].children << "头小猪" << endl;
if (pigs[j].age >= 4)
{
pigs[j].children++;
pigs[count++].age=1;
// pigs[count-1].mother=j;
pigs[count-1].children=0;
// cout <<" 她今年生了一头小猪" << count -1 << endl;
}
}
count_tmp=count;
cout << "\t" << "第" << i << "年猪的总数: " << count << endl;
}
cout << "total pigs: " << count << endl;
return count;
}
int main(void)
{
int years=0;
//get year;
cout << "input years: ";
cin >> years;
count_pigs(years);
}
solution3:
#include <stdio.h>
#define n 70
struct year{
int yearnum;
long pignum;
};
struct year yearslot[n];
int main(){
yearslot[0].yearnum=1;
yearslot[0].pignum=1;
for(int i=1;i<n;i++)
{
long num=0;
for(int j=0;j<=i-3;j++)
{
num+=yearslot[j].pignum;
}
printf("year %d's pig num = %ul\n",i+1,num);
yearslot[i].pignum=num;
yearslot[i].yearnum=1;
for(int j=0;j<i;j++)
yearslot[j].yearnum++;
}
long num=0;
for(int i=0;i<n;i++)
num+=yearslot[i].pignum;
printf("all pig is:%ul\n",num);
}
| | unicorns 回复于：2003-09-01 09:18:56
| 楼上的
这样算不了几年你的cow[AGE_4]就溢出了，
和我n天前写的那个用数组的算法没什么大区别
看起来似乎空间上比每年一个数组元素要节省空间
实际上几下就溢出了，没什么新意啊
n天前的帖子还被顶上来
hoho，我看母牛可以休矣
| | alq974120alq 回复于：2003-09-01 18:25:00
| 我觉得应该是，有几个状态，记录一年生一头的有几个，需要4年才生的有几个，需要3年的有几个，需要两年的有几个，下一年就生的有几个，这样累加应该呢计算出来吧，
这只是我的看法，大家讨论一下，交流交流
| | alq974120alq 回复于：2003-09-01 18:32:23
| int func(int year)
{
int sum=0;
int one=0,two=0,three=0,four=1;
int tmp;
for(int i=0; i<year; i++)
{
sum+=one;
tmp = one;
one+=two;
two=three;
three=four;
four = tmp;
}
return sum;
}
| | aero 回复于：2003-09-02 08:27:28
| [quote:004f27654a="unicorns"]溢出了，
和我n天前写的那个用数组的算法没什么大区别
看起来似乎空间上比每年一个数组元素要节省空间
实际上几下就溢出了，没什么新意啊
n天前的帖子还被顶上来
hoho，我看母牛可以休矣[/quote:004f27654a]
严重同意，大家好好看看前面的帖子，不要在贴同样的算法了。
| | alq974120alq 回复于：2003-09-02 08:30:13
| 没注意前面的，真实无聊
| | 小飞爱使申华 回复于：2003-09-02 12:39:59
| 我倒啊。。。。。。。。。。
大家还在干母牛啊！
| | hangne 回复于：2003-09-26 15:58:13
| 为什么要那么复杂呢?
可以推出公式. M = 2 + (n - 5) *( n - 4) / 2. (n >= 4)
赫赫, 不知对不对.
| | hangne 回复于：2003-09-26 16:49:07
| 哦, 上面的公式不对. 应该是:
f(n) = f(n-1) + f(n - 3).
当n < 4 时, f(n) = 0.那就可以用递归了.
| | badeager 回复于：2003-09-26 16:57:45
| 其实应该再加一个条件，比如牛只能活到40岁等等，这样会更好些
| | pollora 回复于：2003-09-26 21:09:41
| 呵呵，加上年龄怎么做啊
比如20
| | 无术 回复于：2003-10-03 09:07:02
| 在下初学C(四天了)，所以写了一个粗略的非可执行码来以供参详。
在下以四年后牛一头为标准，也就是第五年初生出。
Howcow(int n)
{
int i;
long int addcow[n+1],x=0;//加一是在下习惯，数组值表示每年新增牛数。
if(n<=4) printf("1");
else if(n==5) printf("2");
else {
addcow[0]=addcow[1]=addcow[2]=addcow[3]=0;
addcow[4]=1;
for(i=5;i<n;i++)
addcow[i]=addcow[i-1]+addcow[i-4];
for(i=0;i<n;i++)
x=addcow[i]+x;
printf(x+1值)；//加一是为了加上所有母牛的母亲这头牛
}
main()
{
int n;
scanf(输入N值)；/*N为年数*/
Howcow(n);
}
新增牛数量是一个整数序列，所以用在计数问题上应该比递归要快。
| | pallam 回复于：2003-11-19 11:41:12
| 呵呵,来一个看看
#include <string.h>
#include <math.h>
#define NYEARS 50
#define BORN 3
int born(int year)
{
int tmp,count=0,son=0;
tmp = year-BORN;
if ( tmp<=0 ) return 0;
count = tmp;
for ( ;tmp>=0;tmp-- )
{
son = son + born( tmp );
}
return count+son;
}
void main()
{
int itmp;
for (itmp = NYEARS;itmp>=0;itmp--)
printf( "%d years later cows=[%ld]\n",itmp,born(itmp)+1 );
exit(0);
}
| | tanchanghe 回复于：2004-02-25 15:23:16
| 看了一下楼主的帖子,大家都在研究算法,我非常赞成不用递归, 但是这位仁兄用的循环有点多,我写了个小程序,大家给研究研究,请多提意见
int main(int argc, char *argv[])
{
long cow;
int year;
cow = 0;
year = 0;
if(argc != 2)
{
printf("year must be entered!\n");
exit(0);
}
sscanf(argv[1], "%d", &year);
cow = get_cow(year);
printf("----year = %d\n----cow = %u\n", year, cow);
}
int get_cow(int year)
{
long new_cow;
long total;
long cow[3];
int i;
new_cow = 0;
memset(&cow, 0x00, sizeof(cow));
cow[0] = 1;
total = 0;
for(i = 1; i <= year; i++)
{
new_cow = cow[2];
cow[2] += cow[1];
cow[1] = cow[0];
cow[0] = new_cow;
}
total =cow[0] + cow[1] + cow[2];
return total;
}
| | tanchanghe 回复于：2004-02-25 15:25:56
| 以下是简单的调试结果
[83] % ./cow 1
----year = 1
----cow = 1
[85] % ./cow 2
----year = 2
----cow = 1
[86] % ./cow 3
----year = 3
----cow = 2
[87] % ./cow 4
----year = 4
----cow = 3
[88] % ./cow 5
----year = 5
----cow = 4
[89] % ./cow 6
----year = 6
----cow = 6
[90] % ./cow 9
----year = 9
----cow = 19
[91] % ./cow 10
----year = 10
----cow = 28
[92] % ./cow 11
----year = 11
----cow = 41
[93] % ./cow 99
----year = 99
----cow = 234467045
[94] % ./cow 100
----year = 100
----cow = 2494520797
[95] % ./cow 101
----year = 101
----cow = 3985051102
[96] %
| | myweb123 回复于：2004-02-29 21:08:43
| 是有个公式的，好像叫什么斐波拉契的。
| | 编程菜鸟 回复于：2004-03-13 10:53:49
| 各位，有没有流程图啊！！！！
我很菜， 看程序很累，有没有图让我学习一下吧！
:) ：)
谢谢了！！！
| | gybcb 回复于：2004-03-17 18:37:26
| 不知道大家有没有注意到第二页上stuff990的算法？
无论从效率上来讲，还是从空间上来讲都是最小的。
为什么没有人注意？
| | luzy1976 回复于：2004-03-18 16:21:26
| F(1)=F(2)=F(3)=1
F(4)=2
F(n)=F(n-1)+F(n-4) [n>4]
条件是又足够多而且强壮的[b:7af0726146]公牛[/b:7af0726146]！
要不然增长率会变小的。
| | flyingsilverfox 回复于：2004-05-18 09:55:24
| Here is the simplest solution:
最简单的算法：
#include <iostream>
using namespace std;
long TallyCow(long n)
{
if (n < 4) return 1;
long year[n+1];
year[0] = year[1] = year[2] = year[3] = 1;
for (long i = 4; i <= n; ++i)
{
year[i] = year[i-1] + year[i-4];
}
return year[n];
}
int main()
{
cout << TallyCow(50) << endl; // result is 5453761
return 0;
}
From Massachusetts, USA
| | improgrammer 回复于：2004-05-21 12:11:18
| 8) int calc_cow(int n)
{
int cows[]={1,0,0,0},i;
for(i=0;i<n;++i)
{
int t=cows[3];
cows[3]+=cows[2];
cows[2]+=cows[1];
cows[1]+=cows[0];
cows[0]=t;
}
return cows[0]+cows[1]+cows[2]+cows[3];
}
| | improgrammer 回复于：2004-05-21 12:16:35
| 上面有误！
unsigned calc_cow(unsigned n)
{
unsigned cows[]={1,0,0,0},i;
for(i=0;i<n;++i)
{
unsigned t=cows[3];
cows[3]+=cows[2];
cows[2]=cows[1];
cows[1]=cows[0];
cows[0]=t;
}
return cows[0]+cows[1]+cows[2]+cows[3];
}
cows[50]==5453761
| | eagerly1 回复于：2004-07-17 14:32:53
| 看完了，感谢楼上诸位
| | Asker 回复于：2004-09-25 17:30:57
| 为什么都是生的母牛？
| | sniperfox 回复于：2004-09-25 21:20:26
| long borncow(int n)
{
int i;
long born[4]={1,1,1,2};
for(i=0;i<((n%4 == 0) ? n/4-1 : n/4);i++){
born[0]=born[3]+born[1];
born[1]=born[0]+born[2];
born[2]=born[1]+born[3];
born[3]=born[2]+born[0];
}
return born[(n+3)%4];
}
| | sniperfox 回复于：2004-09-25 21:37:11
| 我觉得像这种递推f(n)=f(n-1)+f(n-3)公式用非递归算法求解都有一种模式
born[0]=born[3]+born[1]; 0 3 1
born[1]=born[0]+born[2]; 1 0 2
born[2]=born[1]+born[3]; 2 1 3
born[3]=born[2]+born[0]; 3 2 0
直接按着顺序写，像0 1 2 3 ，再修改一下OK了
^_^
| | sniperfox 回复于：2004-09-25 22:09:19
| long borncow(int n)
{
int i;
long born[5]={1,1,1,1,2};
for(i=0;i<((n%5 == 0) ? n/5-1 : n/5);i++){
born[0]=born[4]+born[1];
born[1]=born[0]+born[2];
born[2]=born[1]+born[3];
born[3]=born[2]+born[4];
born[4]=born[3]+born[0];
}
return born[(n+4)%5];
}
都成模式了^_^
测试代码
int main()
{
int n=0;
printf("Input n=");
scanf("%d",&n);
printf("%ld",borncow(n));
exit(1);
}
只是测试，所以写的简单，没有考虑出错情况：）
| | napleon 回复于：2004-09-25 22:45:02
| 把题目改一下：
一个女孩80年出生,当她20岁的时候(2000)年开始生孩子，每年生一女孩，生到40岁为止。请问：N年后，她有多少子孙？
| | zerglot 回复于：2004-10-15 16:00:46
| 有意思
| | xtugrad 回复于：2004-10-15 17:21:19
| 我写的，很垃圾，但是好像可以算出来
#include "stdafx.h"
#define year 10
void main()
{
int moggy=1;
int year1=0;
int year2=0;
int array[year];
for (int i=0;i<year;i++)
array[i]=1;
if (year<4)
std::cout<<"moggy numbers="<<moggy<<"\n";
else
{
array[3]=2;
for(int i=4;i<year;i++)
array[i]=array[i-1]+array[i-4];
moggy=array[year-1];
std::cout<<"moggy numbers="<<moggy<<"\n";
}
}
| | shiyiming 回复于：2004-10-15 19:02:17
| 是不是老师出的题目，你拿到这里来找答案了，这样可不好，自己做出来才对
| | ge126 回复于：2004-10-15 22:12:20
| 个人版的母牛
PS：测试一下GCC的扩展
[code:1:c5237e31d3]#include <stdio.h>
int main()
{
int n;
int cow[15]={2,3,4,6,9,13,19,28,41,60,88,129};
printf("input n years, from 1\n");
scanf("%d", &n);
switch(n)
{
case 0 ...3:
printf("total is %d\n",1);
break;
case 4 ...15:
printf("total is %ld\n", cow[n-4]);
break;
default:
printf("Sorry,The Cow is dead!");
}
return 0;
} [/code:1:c5237e31d3]
| | 轩辕砍刀 回复于：2004-10-22 23:57:12
| C/C++版的精华也有这样的东东啊
一年多前的贴子了，好大的坑啊！！！
其实是Fibonacci斐波那契数列的变形了，原始的递进间隔是3
1，1，2，3，5，8，13，21，34… 从第三年起，n(i)=n(i-1)+n(i-2)
现在的间隔改成4，就是
1，1，1，2，3，4，6，9，13… 从第四年起，n(i)=n(i-1)+n(i-3)
如果是5，就是
1，1，1，1，2，3，4，5，7，10，14… 从第五年起，n(i)=n(i-1)+n(i-4)
…………………………………………� |
|
|
