返回列表 发帖
jinzeyu

Rank: 4

帖子
161 
积分
470 
技术
3  
捐助
0  
注册时间
2010-8-11 
1楼 跳转到 » 倒序看帖
打印
tT
发表于 2012-7-26 11:04 | 只看该作者

批处理脚本实现C语言趣味编程百例015：捕鱼和分鱼

要求用BAT脚本实现

加分：1个技术分

A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。日上三杆，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。C、D、E依次醒来，也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？

*问题分析与算法设计
根据题意，总计将所有的鱼进行了五次平均分配，每次分配时的策略是相同的，即扔掉一条鱼后剩下的鱼正好分成五份，然后拿走自己的一份，余下其它的四份。
假定鱼的总数为X，则X可以按照题目的要求进行五次分配：X-1后可被5整除，余下的鱼为4*(X-1)、5。若X满足上述要求，则X就是题目的解。
*程序说明与注释
  1. #include<stdio.h>

  2. int main()

  3. {

  4. int n,i,x,flag=1; /*flag：控制标记*/

  5. for(n=6;flag;n++) /*采用试探的方法。令试探值n逐步加大*/

  6. {

  7. for(x=n,i=1&&flag;i<=5;i++)

  8. if((x-1)%5==0) x=4*(x-1)/5;

  9. else flag=0; /*若不能分配则置标记falg=0退出分配过程*/

  10. if(flag) break; /*若分配过程正常结束则找到结果退出试探的过程*/

  11. else flag=1; /*否则继续试探下一个数*/

  12. }

  13. printf("Total number of fish catched=%d\n",n); /*输出结果*/

  14. }
复制代码
*运行结果
Total number of fish catched = 3121

*问题的进一步讨论
程序采用试探法，试探的初值为6，每次试探的步长为1。这是过分保守的做法。可以在进一步分析题目的基础上修改此值，增大试探的步长值，以减少试探次数。
思考题
请使用其它的方法求解本题。
收藏 分享

neorobin

Rank: 7Rank: 7Rank: 7

帖子
675 
积分
4018 
技术
114  
捐助
0  
注册时间
2009-11-25 
2楼
发表于 2012-8-9 16:50 | 只看该作者
设捕鱼总数为 R_0, 第 i 个人分鱼后的剩余数为 R_i, 则有:
R_i = R_(i+1) * 5 / 4 + 1
R_1, R_2, R_3, R_4, R_5 皆为 4 的倍数.

将 R_5 从 0 开始测试, 如计算得出 R_1, R_2, R_3, R_4 皆为 4 的倍数, 则得最小解;
否则, 将 R_5 增长步长 4, 再次测试...
  1. @echo off

  2. setlocal enableDelayedExpansion

  3. set /a R_5 = 0

  4. :loop

  5. set /a check = 0

  6. for /l %%i in (4 -1 0) do (

  7.   set /a j = %%i + 1

  8.   for %%j in (!j!) do set /a "R_%%i = R_%%j * 5 / 4 + 1"

  9.   if %%i gtr 0 set /a "check |= R_%%i & 3"

  10. )

  11. if !check! neq 0 (

  12.   set /a R_5 += 4

  13.   goto :loop

  14. )

  15. set R_

  16. pause
复制代码

TOP

返回列表