题目描述
C金字塔上的蜗牛 ProblemDescription 场景一： 从前有一个勤奋的蜗牛叫小蜗，他有一个梦想—去埃及金字塔的顶端看一下，于是他就央求鹰哥哥带他到金字塔上去，鹰哥说：”老弟啊，不是哥不帮你?你这可是单程票啊。金字塔老高了，有N层呢”。小蜗说：人总归是要有梦想的，没有梦想跟咸鱼有什么区别?于是他就带了N包士力架，坐上了前往金字塔的航班。 场景二： 蜗牛来到了金字塔的 1层，于是他开始了征战金字塔。已知，蜗牛每天可以下滑1层、保持原有高度、向上爬1层。维持原高度和向上爬，每次都要消耗蜗牛的能量，每次都要通过吃一根士力架来补充体力。下滑不需要能量。问士力架恰好剩1根的时候，蜗牛还苦逼的呆在金字塔的1层的全部可能性。 Input 输入数据N（0<N<=8）。 Output 输出蜗牛每天所在的金字塔的楼层，每个数据间用空格分离，每种可能情况占一行。 SampleInput 3 SampleOutput
11 1 12 1 1 11 2 1 12 1 2 1 12 2 1 12 3 2 1
分析： 在每一层，蜗牛都有下滑、保持和向上的选择。 可以想象蜗牛面临有三条路的岔路口，每条路又会三条路的岔路口 要走完所有路然后判断是否符合要求 蜗牛爬金字塔的所有情况分为三种，
能量大于等于1且楼层大于等于1时进行选择路径
如果能量小于1或者楼层小于1，超出范围，那么这一个选择不能完成题目要求，
说明该岔路口不通，结束该条路，换上个岔路口走
能量等于1而且楼层等于1时，符合题意，输出足迹，结束这条路，走上个岔路口
足迹的保存通过数组，采用计数变量实现足迹可以退回
解法：
[cpp] view plain copy
print?
- #include "stdio.h"
- int step[16];
- //分而治之，递归
- //能量，层数，递归的级数
- void climb(int energy,int level,int len)
- {
- step[len]=level;
- if(level<1 || energy<1)
- {
- return;
- }
- if(energy==1)
- {
- if(level==1)
- {
- for(int i=0;i<=len;i++)
- {
- printf("%d",step);
- if(i!=len)
- {
- printf(" ");
- }
- }
- printf("\n");
- return;
- }
- }
- climb(energy,level-1,len+1);
- climb(energy-1,level,len+1);
- climb(energy-1,level+1,len+1);
- }
-
- void main()
- {
- int N;
-
- while(printf("请输入N:\n"),scanf("%d",&N)!=EOF)
- climb(N,1,0);
- }
结果：
| 
楼主
标题置顶
标题高亮
