应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 上次很是失败，再来一个，大家给点鼓励呀！
71/1返回列表
查看: 1133  |  回复: 6
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 1 个 程序强帖 ，点击这里进行查看

微尘、梦想

木虫 (知名作家)

[交流] 上次很是失败，再来一个，大家给点鼓励呀！ 已有3人参与

五只猴子采得一堆桃，它们约定次日早起来分。半夜里，一只猴子偷偷起来，把桃均分成五堆后，发现还多一个，它吃了这桃子，拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃了这个桃子，拿走了其中一堆。第三只，第四只，第五只猴子都依次如此做了。问桃子数最少有多少个?
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
任风云变幻，我笑对人生！
1楼 2011-04-19 18:17:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+5): 说的非常详细呀，看能不能贴出代码，让大家看一下 2011-04-20 16:03:02
微尘、梦想(程序强帖+1): 2011-04-23 17:43:06
设总桃子数为x[0]，经过1个猴子分后，剩余桃子数为x[1]...经过n个猴子分后，剩余桃子数为x[n]，于是有

x[n] = (x[n-1] - 1)*4/5

变形得

(x[n]+4)/(x[n-1]+4) = 4/5

即若令q[n]=x[n]+4，则{q[n]}为等比数列~

于是乎有

x[n]+4 = (x[0]+4)*(4/5)^n                【这里的^表示指数】

即

x[0] = (5/4)^n * (x[n]+4) - 4

假设一共有n个猴子无压力执行了分桃，那么n-1个猴子分桃后的桃子数，必定满足“减1后能被5整除”的条件，于是令x[n-1]=5k+1，k为整数

那么

x[0] = (5/4)^(n-1) * (x[n-1]+4) - 4
变为式子
x[0] = (5/4)^(n-1) * (5k+5) - 4 = 5^n * (k+1)/(4^(n-1)) -4

因为x[0]必为整数，故(k+1)/(4^(n-1))必须为正整数，而x[0]取最小值时，取(k+1)/(4^(n-1))=1即可

故~

n猴分桃的问题，原来那堆桃子数量最少为5^n-4
其中，n>=2，当n=5时，桃子数最小值为3121


PS：
上面对于n猴分桃的推广，仍然是基于“每个猴子都把桃子分成5堆，然后发现多一个，于是吃掉一个，拿走一堆”的做法假设，而实际上这么做并不大符合逻辑，于是这个分桃问题可以扩展为：

“n只猴子采得一堆桃，它们约定次日早起来分。半夜里，一只猴子偷偷起来，把桃均分成n堆后，发现还多一个，它吃了这桃子，拿走了其中一堆。第二只猴子醒来，又把桃子均分成n堆后，还是多了一个，它也吃了这个桃子，拿走了其中一堆。第三只，第四只......第n只猴子都依次如此做了。问桃子数最少有多少个?”

试试看上面的扩展吧

[ Last edited by sudo on 2011-4-19 at 19:50 ]
赞一下(3人) 回复此楼
2楼2011-04-19 19:48:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
发现2楼的扩展也很简单...照这个思路解就行....

x[0]最小值为n^n - n + 1
赞一下(1人) 回复此楼
3楼2011-04-19 20:09:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+5): 谢谢参与，答案是3121，2楼分析的比较透彻，你可以按那个思路再试一下！ 2011-04-20 16:05:44
2楼分析是对的,第一次看错了题目,以为是分2堆.重写了,代码比较乱
CODE:
#include
#include

int main(int args, char* argv[])
{
        int i, n, p;
        bool flag = false; //循环标志
       
        n = 2; //起始种子
       
        while(!flag)
        {
                p = n; //当前桃子数

                for(i=0;i<5;i++)
                {
                        if((p-1)%5==0) //减1后可以分5堆
                        {
                                flag = true; //改变标志
                                p = (p-1)*4/5; //下一个猴子分的桃子数
                        }
                        else
                        {
                                flag = false; //减1不能分5堆,继续外循环
                                break; //直接跳出内循环
                        }       
                }

                if (flag) //内循环结束后判断标志
                        break; //如果可以按条件分好,跳出外循环

                n += 1; //桃子数+1
        }

        printf("桃子共有: %d 个.\n",n); //打印结果
       
        system("PAUSE");
    return 0;
}

结果
CODE:
桃子共有: 3121 个.

[ Last edited by libralibra on 2011-4-20 at 16:43 ]
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
4楼2011-04-20 03:57:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+5): 谢谢参与，不知道你运行成功了没，答案是3121，为什么我编译成功，却得不出结果呢，还有就是我感觉这样不方便，每次都要在命令提示符下运行，一般来说，像这种小程序，没必要实用main函数参数吧…… 2011-04-20 16:16:15
楼上的代码明显有问题，手算：
1 *5 + 1 = 6
这里的6不能被4整除，也就是说，不是原来的4/5
代码应该是回溯性质的：
CODE:
#include
#include
//自顶向下分析，用于验证
//第n只猴子，看到剩余s个桃子
int funcup(int n, int s){
  if((s-1)%5 != 0){
    return 0;
  }
  printf("less:%d, eated:%d, take off:%d--%d\n", s, s-1, (s-1)/5, (s-1)%5);
  if(n == 1){
    return (s-1)/5 * 4;
  }
  return funcup(n-1, (s-1)/5*4);
}
//自底向上分析，用于计算
//看到s个桃子，第n个猴子，总共nn个猴子
int funcdown(int s, int n, int nn){
  int i;
  //最后一只猴子不需要满足4等分条件
  if(n == nn){
    return s;
  }
  if(s%4 != 0){
    return 0;
  }
  return funcdown(s/4*5 + 1, n + 1, nn);
}
int main(int argc, char **argv){
  int i, s, n = atoi(argv[1]);
     //i表示早上最终剩下的桃子数
  for(i = 4; i < n; i+=4){
    //第一只猴子看到的桃子需满足四等分条件
    s = funcdown(i/4*5 + 1, 1, 5);
    if(s){
      printf("s:%d---:\n", s);      //这个打印晚上猴子摘回来的桃子数
      if(s = funcup(5, s)){            //验证
        printf("--->moring less %d, %d...\n", s, i);
        break;               //去掉可以得到所有的可行解
      }
    }
  }
  return 0;
}

[ Last edited by huycwork on 2011-4-20 at 16:34 ]
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
5楼2011-04-20 10:02:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想: 嗯，我也觉得这样对编程有好处，不过这需要大家的参与才行啊，你要有什么试题的话，可以拿出来让大家一起做做，呵呵……建议你看看那个置顶的帖子，不过要注意要求哦，否则会被处罚滴！ 2011-04-20 16:53:03
是3121没错,第一次看错题目了,代码重写了,还是比较乱
希望多出这种帖子,大家多交流
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
6楼2011-04-20 16:45:43
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3): 谢谢参与活动，另外你真的是学文艺美学的吗？ 2011-04-21 12:02:03
其实都有解析解了，代码就没必要了吧~

嗯，这是按照2楼的扩展问题来写的...
CODE:
#include

int main(){
    unsigned int peach=1, monkey, temp;

    printf("Input the number of monkeys:");
    scanf("%d", &monkey);
    if(monkey<2 || monkey>9) return 1;

    for(temp=0; temp         peach *= monkey;
    }
    peach = peach-monkey+1;

    printf("Peach minimum=%d\n", peach);

    return 0;
}

无出错检测~

PS：一般来说解析解能得到简单、效率高的程序，当然也有例外，比如斐波那契数列的话，解析解就不好转化为程序求了

[ Last edited by sudo on 2011-4-21 at 09:26 ]
赞一下(2人) 回复此楼
7楼2011-04-21 09:18:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 微尘、梦想 的主题更新
71/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +4 2h7du0nuhk 2026-02-07 4/200 2026-02-07 22:24 by ioveiuleh5
[硕博家园] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 4/200 2026-02-07 22:11 by ioveiuleh5
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 5/250 2026-02-07 22:06 by ioveiuleh5
[教师之家] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 5/250 2026-02-07 22:04 by ioveiuleh5
[教师之家] 有院领导为了换新车，用横向课题经费买了俩车 +7 瞬息宇宙 2026-02-04 7/350 2026-02-07 21:47 by tfang
[找工作] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 5/250 2026-02-07 21:46 by ioveiuleh5
[公派出国] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 6/300 2026-02-07 21:44 by ioveiuleh5
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 6/300 2026-02-07 21:31 by ioveiuleh5
[教师之家] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 6/300 2026-02-07 21:26 by ioveiuleh5
[硕博家园] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 6/300 2026-02-07 21:11 by ioveiuleh5
[有机交流] 酰胺脱乙酰基 10+5 chibby 2026-02-03 12/600 2026-02-07 19:29 by 江东闲人
[硕博家园] 售SCI一区文章，我:8 O5 51O 54,科目齐全 +3 2h7du0nuhk 2026-02-07 3/150 2026-02-07 18:31 by 6ntj4f1rhx
[基金申请] 同年申请2项不同项目，第1个项目里不写第2个项目的信息，可以吗 +4 hitsdu 2026-02-06 4/200 2026-02-07 13:07 by jurkat.1640
[基金申请] 有时候真觉得大城市人没有县城人甚至个体户幸福 +9 苏东坡二世 2026-02-04 10/500 2026-02-07 12:37 by 小毛球
[考博] 天津大学招2026.09的博士生，欢迎大家推荐交流（博导是本人） +4 a793625982 2026-02-05 5/250 2026-02-07 10:57 by a793625982
[公派出国] CSC & MSCA 博洛尼亚大学能源材料课题组博士/博士后招生｜MSCA经费充足、排名优 +4 雨念 2026-02-01 6/300 2026-02-06 23:32 by MelissaPon
[基金申请] 面上项目申报 +3 Tide man 2026-02-01 3/150 2026-02-05 22:56 by god_tian
[硕博家园] 博士延得我，科研能力直往上蹿 +7 偏振片 2026-02-02 7/350 2026-02-04 17:36 by 陈氏帝国
[基金申请] 面上基金申报没有其他的参与者成吗 +5 默默的小虫子 2026-01-31 5/250 2026-02-04 11:26 by 学员fOzRO9
[教师之家] 遇见不省心的家人很难过 +18 otani 2026-02-03 22/1100 2026-02-04 11:06 by tangmnt
信息提示
关闭
请填处理意见
关闭