开发工具:
文件大小: 3kb
下载次数: 0
上传时间: 2009-06-30
详细说明： 【问题描述】 一只猴子在X天中一共吃了Y个桃子。已知这只猴子每天最多吃10个桃子，最少可以不吃桃子。问一共有多少种不同的吃法。 例如：X=3，Y=4时（即3天吃4个桃子）一共有下面列出的15种不同吃法 1 :0 0 4 2 :0 1 3 3 :0 2 2 4 :0 3 1 5 :0 4 0 6 :1 0 3 7 :1 1 2 8 :1 2 1 9 :1 3 0 10 :2 0 2 11 :2 1 1 12 :2 2 0 13 :3 0 1 14 :3 1 0 15 :4 0 0 【问题分析】 这个题目比较好的解决方法是用递归。 我们定义一个递归函数eat( x, y )表示在x天之内吃y个桃子。那么具体定义为： 1、如果x=0且y=0，表示当前已经搜索到的是一种可行的解法，需要把该解法输出。 2、如果x>0且y>0，表示还没有搜索完，那么就要按下面的方法继续递归： for ( i = 0 ; i <= 10 ; i++ ) eat( x-1, y-i ) ; 这里的i相当于是该天吃桃子数量的探索值。但是由于可以在后面的几天里面一个桃子也不吃（见上面的5、9、12、14、15这几种情况），也就是说只要没有到最后一天（x=0），就需要继续向下搜索，所以x>0且y>0的条件是不完备的，应该是x>0且y>=0。 3、其它情况（如x<0或y<0，x=0且y>0等）为非法情况或表明当前解不成立，故要返回。 由此可以写出eat函数的伪代码： void eat( int x, int y ) { if ( x > 0 && y >= 0 ) for ( i = 0 ; i <= 10 ; i++ ) eat( x-1, y-i ) ; else if ( x == 0 && y == 0 ) 输出当前解; return ; } 【程序代码】 根据上述思路，我们可以比较容易地写出下面的程序。不过，这里有几个地方经过了修改： 1、为了便于结果的输出，所以使用了一个全局整型数组arr来存放当前解。 2、为了便于对arr数组的下标进行管理，给eat函数增加一个参数idx，标识出当前的空余位置（把探索的解i放在该位置）。 3、虽然每天最多吃10个桃子，但是如果当前情况下不够10个桃子，那么在进行for( i = 0 ; i <= 10 ; i++ )这个循环时，有些i值就是不必要的。所以程序设立了一个i_end变量，如果当前情况下剩余的桃子总数y多于10个，那么i_end取10；如果少于10个，那么就让i_end等于y。这样可以减少不必要的循环与递归。 #include #define DAY 3 #define PEACH 4 int arr[DAY] ; long int times ; FILE *fp ; void eat( int day, int peach, int idx ) { if ( day > 0 && peach >= 0 ) { int i, i_end ; i_end = ( (peach<10) ? (peach) : (10) ) ; for ( i = 0 ; i <= i_end ; i++ ) { arr[idx] = i ; eat( day-1, peach-i, idx+1 ) ; } return ; } else if ( day == 0 && peach == 0 ) { int i ; times++ ; fprintf( fp, "%-10ld:", times ) ; for ( i = 0 ; i < DAY ; i++ ) fprintf( fp, "%-3d ", arr[i] ) ; fprintf( fp, "\n" ) ; return ; } else return ; } int main( void ) { int day, peach ; day = DAY ; peach = PEACH ; times = 0 ; fp = fopen( "monkey.txt", "w" ) ; /* 打开用于保存结果的文件 */ eat( day, peach, 0 ) ; fclose( fp ) ; /* 关闭文件 */ return( 0 ) ; } ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
