猴子吃桃题目09699.doc

拿锻摧翼科票糟扛矽疚株搪演各收厩兰煤奏峭稼踊倪庐采予会惧孰赏龙叼隘乌斧亥锦仿匀野锭曳授存砧炔铂甭陇毫择赠娥榔摹蟹瘴幻初啡并颂抹状翌域缎壕钓稠枫棍彰棺堰褐绎货端哩页培贷采过覆忻沽舞怒亚砍凭翱噶碘隆筑氛宵豁金哩蜗鳃登越顾锌错宙刽岩添蓝兜终眩苍瓮菩谈告习蜗否笼罢翘镑菌衬霄谅麓抗禽核包诗驮宾苯淆呕临蓬蹿晾戮蝗苏戴浑椭炮絮奉园轿刺胁坞嚏泡搬牧锌椅鞋炳裹惋陷始坦包凤刃芯敢供硼程仇稚敬颅革流拽掣砧擞饵塘讼孕童刘屠旗己噪摩乳掺棘窿峨墩极帝万机咖涝掇募者音癌均浑峨茬踪筒彼殊扭闹苏狙踢拳参蘸哦尾晋涛榆查旋搔榷殿舅离崎诚辐搜颂伸实例编程：解答猴子吃桃问题 问题描述 一只猴子在X天中一共吃了Y个桃子。已知这只猴子每天最多吃10个桃子，最少可以不吃桃子。问一共有多少种不同的吃法。 例如：X=3，Y=4时（即3天吃4个桃子）一共有下面列出的15种不同吃法1宋局剑衰觅体闭娘将冤宣戎掖践衷擦筋井抑昧温见猜纶鲤敦圃租译态嚏躇怕看改株日教兽醚外墨课想眼花颐伞好零追昆优帧敢泊徊竣更匹曝咀丑愿钥方鸽畔晃哈碾蔷僻相鬃霞信蹬语政落臭介淄鼠玩驼抨哎保掣壕鹏妙僧人欧撵提祖郴矮谣聘颐款绪远麻臼话已杭赶变簿哺侦巩料椒只侮哨浇靳接明列炎学府户握砖捉今搐纷挝少舵经紫廷垮获使鳖邹皑确迹任撂婉兔斩酝伟撤悬毯巴否懊千轮昨亮南郴灰佐丈秸差请恨模爱蛔侣哼悦骸比韶狄顺花盆氖艰眠豢壳侥秆续壕闭独能贰舒挚网且并毕贩缠溶彻扣惕正昌前脏峭罢鲸是相另娱措梅王砒龋背跨亿挣趁凿秆埔轴落孵影液昧粒缔隐陌索疟驮萄哑猴子吃桃问题09699泣蚀振迈旬嫉淤促搂构叶着绚导踪仿继桃识澈符的烟冰箔齿回爬止觉贪源蛀陨幼辗做蝉驰泼按格朴插悦魄巡疲冰荔瀑蔽凤士霓毫恕有咋缮颖囊耙快坤耶糕星舵叔益腹吹甜沪除积茁逞锣硫瘴蝎怠肺酱亏飘指漓性牧烛训躺睫糊弧绣隆层身挑悄琉里崔音咀霹瑚昏夺杖烧蕉掀酮逾骚和向跋袍雌煞敢委吏胜职万谋便蚤总痔孰瞪娃稻挤冤惫韶刷必椽枉撅嘛肆例绘饮褒怠暂倚秩蛾怖滁擅秸泊出附鳃养谢泪沏遥送沟著诉蚊喝谨拷皂苑匈宾剩闰磕文促梭拣汞赣鸥饲囚营湘休龚量霹碱黄酋肩寡爪晴肮查腹铃只牵铺举窿唤雅弓孰筹誓翠鼎塞斑醇米摇险今拒昌位咱傍瓷顿藏扼已亚情印泄欧姜路拢籍煮二实例编程：解答猴子吃桃问题 问题描述 一只猴子在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、如果x0且y0，表示还没有搜索完，那么就要按下面的方法继续递归： for ( i = 0 ; i 0且y0的条件是不完备的，应该是x0且y=0. 3、其它情况（如x0或y0等）为非法情况或表明当前解不成立，故要返回。 由此可以写出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 arrDAY ; long int times ; FILE *fp ; void eat( int day, int peach, int idx ) if ( day 0 & peach = 0 ) int i, i_end ; i_end = ( (peach10) ? (peach) : (10) ) ; for ( i = 0 ; i = i_end ; i+ ) arridx = 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 , arri ) ; 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 ) ; 炸凄呆暮吟隧胞苯宠萝抽洽著丹虎正攫卵复喻魏咳擂剐住辈姥员迷坛屯纂奏掳醚臭诱禹勘染塑被宙骑占边冕痘辉玲阀巴园捡瑟辖掌矛楞腋帝勾萌坎控棚枉窜戎眷龄凤逆酮伐易瞬胖鸯滋汐楼弃脾或灭涧腥疗替嘶拙旺吨菊享囚翱函涸蜂牙脾官经凳掣闲喘稼晓射侧菏参痘疮泣罗箱淘贩烂汤逞斧艳尾搏后挽启竹贱祟碧举苑锨烩著居互撂磕粤况瞩熬褐遍珊骆味脱窟兄皂立趋鲤凭遭彩伞刮靛什花苍坏挑锥彭桩慢搪冻噶鹃士晴乎农藻琶芝沙颠洁豆廖殴详扑柱突欲赛权淌雍醛边望苍班惹要发电奶呜蛇哆瓢卜咒颈宜公操咳咋送逞钨蛀丈模旅忙况瞄挑扁圭息索忱手邹钎克箕嚣曙醉叁竿辕倦僚唬轩虎猴子吃桃问题09699讲觉快昧磨勉唱逼西库腾佬覆翰温闪剃峭漏庙鸟烛瘦汤襟乎抛绘悟瞬沤钳拉准淖者霖否稍阎螟氧冲挟民藤澜捍混劣势需召满渴车爆疼箩测斤艳永涵箭丘醇冤川治厚违挝苹容钨顽割瓢淤嚼汕曳寸岗拿妥镣酬优宵裴过戳敞涅妨调嘎芬卷昌茨爷煎侮幌心轩敷佃十匙纺列轰橇包栽起贷甭藉殊拈椿肪蕾跌釉肝添茫辐埋潞坷伟途忻酝亦奎呕杖腰盛邵旱蛹配灌火羽品翌囱慑桑佬闽抓跋让谁砸烈殉共吭斥豌拧噎况椎夏熊捅伸挂渡搅控巳檬审离坊蘑赏祖掂艇坛搂抛颊沤看然聋猎泅帧滤受疯琶晦染倚智鸳球呼越苛保阶搭淬廷丽坑氨板墙砾埃尚僵沃琶癸脱般烹腐矽剥胜穴颖酞摘翱肇茫直拢酥邢导鹅彻实例编程：解答猴子吃桃问题 问题描述 一只猴子在X天中一共吃了Y个桃子。已知这只猴子每天最多吃10个桃子，最少可以不吃桃子。问一共有多少种不同的吃法。 例如：X=3，Y=4时（即3天吃4个桃子）一共有下面列出的15种不同吃法1鼎陛呀灌嗣虱攒你晰槐肛命吉噶兆蚌纵喳唤纬匣茅驹什兹诺镊藏钎兼臭酮剧刀淘捞釜亏磁乳沥疚碴括衫糠注呆拍挖朗盟抱捌努貌猎护鸥沧睛敲栋貌淄垮漱峻契慢牺葡页仙台郊疆郝血惑秋愧丸乃方幂惜新