问题详述:一个机器人每步随机走1米或2米,求机器人走n米的方法数MethodNum(n),并列出所有的走法。
个人思考:
1.实际上MethodNum(n)=fibonacci(n+1),用数学归纳法也可证明,或者可以考虑机器人走的第一步:若是第一步走1米,走完剩下n-1米的方法数为Method(n-1);若是第一步走2米,走完剩下n-2米的方法数为Method(n-2)当然,前提是n>=3;那么Method(n)=Method(n-1)+Method(n-2),再考虑初值,Method(1)=1;Method(2)=2——可补充定义Method(0)=1;那么Method(n)对应的数列为fibonacci数列是显然的。
2.现在考虑罗列出所有的走法
想了很久最后还是决定用栈:机器人所有的走法,都可以从1,1,1,...,1这n个1组成的栈开始输出。假设栈的每个元素只能取1或者2,栈从下至上的元素排列对应机器人的一个走法。现在让栈顶元素出栈,往下加1(如果能加的话)只要产生了2,那么这个排列就一定会是新的走法(可自行验证)。如果不能加的话,要么是结束了,要么就是遇到2,那么2继续出栈。那么现在的关键是:什么情况下输出栈中所有元素?输出栈中所有元素的条件就是栈中所有元素之和为n.
#include "stdafx.h" #include <iostream> using namespace std; #define MAXSIZE 100 void RobotWalkingSteps(int n); int _tmain(int argc, _TCHAR* argv[]) { RobotWalkingSteps( 7 ); return 0; } void RobotWalkingSteps(int n) { int stack[MAXSIZE]; //初始化栈 for(int i = 0; i < n; ++i) { stack[i] = 1; } int top = n-1; int sum = n; while(1) { if(sum == n) { for(int i = 0; i <= top; ++i) { cout<<stack[i]<<"\t"; } cout<<endl; //栈顶元素出栈 sum -= stack[top]; --top; //出栈后我们想要往下加1,那么得判断后面的元素,如果是2,那么继续出栈 while(1) { if (top == -1) { //程序结束了 cout<<"输出完毕"<<endl; return; } if (stack[top] == 1) { //沉到这里就得到了一个不同走法的前面几步 ++stack[top]; ++sum; break;//不用再往下沉了,准备把后面的几步初始为1 } else { //否则的话,说明栈顶元素是2,出栈,继续往下搜索 --top; sum -= 2; } } } else { //此时因为sum != n 说明我们出栈了一些元素,并且使得一个1变成2了 for(int i = top + 1; sum < n; ++i) { stack[i] = 1; ++top; ++sum; } } } }
推广)
如果机器人一步可以走3米的话,那么若假设走n米的方法数为Method(n),那么Method(n)=Method(n-1)+Method(n-2)+Method(n-3).
那如何罗列出所有的走法,之前的方法同样可行吗?答案是可行的。
#include "stdafx.h" #include <iostream> using namespace std; #define MAXSIZE 100 void RobotWalkingSteps(int n); int _tmain(int argc, _TCHAR* argv[]) { RobotWalkingSteps( 7 ); return 0; } void RobotWalkingSteps(int n) { int stack[MAXSIZE]; //初始化栈 for(int i = 0; i < n; ++i) { stack[i] = 1; } int top = n-1; int sum = n; int countMethod = 0; while(1) { if(sum == n) { for(int i = 0; i <= top; ++i) { cout<<stack[i]<<"\t"; } cout<<endl; ++countMethod; //栈顶元素出栈 sum -= stack[top]; --top; //出栈后我们想要往下加1,那么得判断后面的元素,如果是3,那么继续出栈 while(1) { if (top == -1) { //程序结束了 cout<<"输出完毕"<<endl; cout<<countMethod<<endl; return; } if (stack[top] == 1) { //沉到这里就得到了一个不同走法的前面几步 ++stack[top]; ++sum; break;//不用再往下沉了,准备把后面的几步初始为1 } else if (stack[top] == 2) { //沉到这里也得到了一个不同走法的前面几步 ++stack[top]; ++sum; break;//不用往下沉了,准备把后面的几步初始为1 } else { //否则的话,说明栈顶元素是3,出栈,继续往下搜索 sum -= stack[top]; --top; } } } else { //此时因为sum != n 说明我们出栈了一些元素,并且使得一些元素发生改变了 for(int i = top + 1; sum < n; ++i) { stack[i] = 1; ++top; ++sum; } } } }
事实上,走步问题对应着一个逢K进位的表达序列,其和为n,那么其中的判断语句可以用下面的形式表示:
void RobotWalkingSteps(int n) { int stack[MAXSIZE]; //初始化栈 for(int i = 0; i < n; ++i) { stack[i] = 1; } int top = n-1; int sum = n; int countMethod = 0; while(1) { if(sum == n) { for(int i = 0; i <= top; ++i) { cout<<stack[i]<<"\t"; } cout<<endl; ++countMethod; //栈顶元素出栈 sum -= stack[top]; --top; //出栈后我们想要往下加1,那么得判断后面的元素,如果是K,那么继续出栈 while(1) { if (top == -1) { //程序结束了 cout<<"输出完毕"<<endl; cout<<countMethod<<endl; return; } if (stack[top] == K) { //出栈,继续往下搜索 sum -= stack[top]; --top; } else { //说明栈顶元素可以+1,得到了一个不同走法的前面几步 ++stack[top]; ++sum; break;//不用往下沉了,准备把后面的几步初始为1 } } } else { //此时因为sum != n 说明我们出栈了一些元素,并且使得一些元素发生改变了 for(int i = top + 1; sum < n; ++i) { stack[i] = 1; ++top; ++sum; } } } }