A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© donkey2 中级黑马   /  2014-11-13 12:49  /  2101 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 donkey2 于 2014-11-15 10:08 编辑

A/B/C/D/E5个人在某天夜里合伙去捕鱼,到凌晨时都疲惫不堪,于是各自找地方睡觉,第二天,A第一个醒来,他将鱼分成5份,把多余的一条鱼扔掉,拿走自己的一份。B第二个醒来,也将鱼分成5份,把多余的一条鱼扔掉,拿走自己的一份。C/D/E依次醒来,按同样的方法拿鱼。问他们合伙至少捕了多少条鱼?
*问题分析与算法设计方法一
试探法:
根据题意,总计将所有的鱼进行了五次平均分配,每次分配时的策略是相同的,即扔掉一条鱼后剩下的鱼正好分成五份,然后拿走自己的一份,余下其它的四份。假定鱼的总数为X,则X可以按照题目的要求进行五次分配:X-1后可被5整除,余下的鱼为4*(X-1)/5。若X满足上述要求,则X就是题目的解。

#include<stdio.h>
int main()
{
int n,i,x,flag=1; /*flag:控制标记*/
for(n=6;flag;n++) /*采用试探的方法。令试探值n逐步加大*/
{
for(x=n,i=1&&flag;i<=5;i++)
if((x-1)%5==0) x=4*(x-1)/5;
else flag=0; /*若不能分配则置标记falg=0退出分配过程*/
if(flag) break; /*若分配过程正常结束则找到结果退出试探的过程*/
else flag=1; /*否则继续试探下一个数*/
}
printf("Total number of fish catched=%d\n",n); /*输出结果*/
}
运行结果:
Total number of fish catched = 3121
进一步讨论
程序采用试探法,试探的初值为6,每次试探的步长为1。这是过分保守的做法。可以在进一步分析题目的基础上修改此值,增大试探的步长值,以减少试探次数。

4 个回复

倒序浏览

方法二(递归算法)
#import <Foundation/Foundation.h>

int sub(int n);
//int getNumber(int n);
//int number;
int main(int argc, const char * argv[]) {
    @autoreleasepool {
//        // insert code here...
//        NSLog(@"Hello, World!");
//       number = getNumber(5);
//        NSLog(@"%i",number);
int number;
number  = sub(5);
NSLog(@"%i",number);
    }

    return 0;

}


int sub(int n)
{
    if(n == 1)
    {
        static int i = 0;
        do {
            i++;
        } while (i % 5 != 0);
        return (i + 1); //5人平分后多出一条鱼
    }else
    {
        int t;
        do {
            t = sub(n - 1);
        } while (t % 4 != 0);
        return (t / 4 * 5+1);
    }
}

分析:
输入5是想求倒数第五个人拿之前有多少鱼。
n = 5,一直往前递归,n = 4,n=3,n=2。。。
当n=2时,就时倒数第二个人(第四人)拿鱼的时候,有多少鱼。
那么,由题目可以知道,倒数第二个人拿鱼时,剩余的鱼应该也能满足减去1后能被5整除。
又由于,倒数第三人取过鱼后,剩余的鱼数一定能被4整除。所以,也要满足这个条件。
从而,sub(5)往下递归到sub(2),再递归sub(1),算出sub(2)之后再回溯给sub(3),sub(4),sub(5)看看是否依次能够满足条件,不满足就继续 i++ , 知道满足sub(5),往下的所有都满足,就得到了要求的数。就可以得到sub(5)。

废死个脑筋,吃饭去了,想的头晕。

回复 使用道具 举报
精髓:只考虑当前步骤,下一步就让下一步去做。
回复 使用道具 举报
我为什么不能发帖子?应该去哪里发啊
回复 使用道具 举报
dongdong0227 发表于 2014-11-13 19:30
我为什么不能发帖子?应该去哪里发啊

不可能不能发吧?提示为啥不能发呀。我是正在走入学流程,让在这个区域发的。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马