帮帮忙!大家帮我看下用什么算法!我想用递归的!但不知道从合做起!!

jayj

海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三、第四、第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？(要用C语言啊)

[ 本帖最后由 jayj 于 2006-4-13 23:07 编辑 ]

powerwind

1. 
   
2. #include<iostream>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int x=1;
   
8.     for(int i=0;i<5;i++)
   
9.     x=x*5+1;
   
10.     cout<<x<<endl;
    
11. }
    

复制代码

不知这样行不行?

COD

楼上的肯定错了.楼主,最后还剩多少桃知不知道?

powerwind

我是错了.
再想想!

jayj

如果知道我都会做了!!

gyCai

这道题好像最后有两个未知数，只能求出范围，无法得到一个确切的结果。大家可以从数学方面考虑一下。

xiezixu1983

范围？　那就行了吧　题目要求最小值

gyCai

#include<stdio.H>
int p(int x,int y);
static int k;

void main()
{
    int re,i;
        for(i=1;i<5000;i++)
        {
        k=0;
        re=p(i,5);
                if(k==6)
                {
                        printf("resule is %d\n",re);
                    break;
                }
        }
}

int p(int x,int y)
{
   int a;
   k++;
   if(y>0)
   {
           if((x-1)%5==0)
           {
          a=(x-1)*4/5;
          p(a,y-1);
           }
   }
   return x;
}

[ 本帖最后由 gyCai 于 2006-4-14 17:31 编辑 ]

jayj

做啊  !

gyCai

运行结果为3121

gyCai

老大，数学计算是一回事儿，要把它用程序表达出来又是另外一回事儿了。不知道对不对呢？

jayj

范围都溢出了!

gyCai

int 的范围在普通的32位计算机上（IBM和Intel）是-32768~32767

gyCai

我这个算法其实不能说是真正意义上的递归，其中还用了类似于穷举的东西，如果单纯用递归我做不出来。还忘wool王和hjack等高手指点一下。
谢谢

[ 本帖最后由 gyCai 于 2006-4-14 17:34 编辑 ]

jayj

还有很多问题!

黯然销魂

1. //Flash ActionScript 1.0
   
2. //逆归, 穷举范围1~500
   
3. function getAmount(monkeyCount, lastCount) {
   
4.         var eachCount;
   
5.         if (monkeyCount == 1) {
   
6.                 eachCount = lastCount;
   
7.         } else {
   
8.                 eachCount = getAmount(monkeyCount-1, lastCount)/4;
   
9.         }
   
10.         return eachCount*5+1;
    
11. }
    
12. var tempCount;
    
13. for (i=1; i<=500; i++) {
    
14.         tempCount = getAmount(5, i);
    
15.         if ((tempCount-Math.floor(tempCount)) != 0) {
    
16.                 continue;
    
17.         } else {
    
18.                 trace("共有"+tempCount+"只桃子, 最后一只猴子那份有"+i+"只桃子.");
    
19.                 break;
    
20.         }
    
21. }
    

复制代码

output:
共有3121只桃子, 最后一只猴子那份有255只桃子.

黯然销魂

1. //Flash ActionScript 1.0
   
2. //完全逆归版
   
3. function getAmount(monkeyCount, lastCount) {
   
4.         var eachCount;
   
5.         if (monkeyCount == 1) {
   
6.                 eachCount = lastCount;
   
7.         } else {
   
8.                 do {
   
9.                         eachCount = getAmount(monkeyCount-1, lastCount)/4;
   
10.                         if ((eachCount-Math.floor(eachCount)) != 0) {
    
11.                                 lastCount++;
    
12.                                 flag = true;
    
13.                         } else {
    
14.                                 flag = false;
    
15.                         }
    
16.                 } while (flag == true);
    
17.         }
    
18.         return eachCount*5+1;
    
19. }
    
20. trace("共有"+getAmount(5, 1)+"只桃子.");
    

复制代码

output:
共有3121只桃子.

黯然销魂

呀, 楼主居然要C语言的...写法参照我第二个版本...在递归函数内部判断是否为整数即可.

黯然销魂

1. 
   
2. /*C Edition*/
   
3. #include <stdio.h>
   
4. int getamount(int monkeycount, int lastcount){
   
5.         int eachcount;
   
6.         int tempcount;
   
7.         int flag;
   
8.         if(monkeycount==1)
   
9.                 eachcount=lastcount;
   
10.         else{
    
11.                 do{
    
12.                         tempcount=getamount(monkeycount-1,lastcount);
    
13.                         if(tempcount%4==0){
    
14.                                 eachcount=tempcount/4;
    
15.                                 flag=0;
    
16.                         }else{
    
17.                                 lastcount++;
    
18.                                 flag=1;
    
19.                         }
    
20.                 }while(flag);
    
21.         }
    
22.         return eachcount*5+1;
    
23. }
    
24. main(){
    
25. printf("There are %d peaches!\n",getamount(5,1));
    
26. }
    

复制代码

output:
There are 3121 peaches!

[ 本帖最后由 黯然销魂 于 2006-4-15 23:44 编辑 ]

黯然销魂

注, 第2个参数表示最后一只猴子每份的个数.