VMware 猫和老鼠玩象棋 java 实现
猫和老鼠玩象棋，玩了M+N局，猫赢了M局 老鼠赢了N局 N>M，而且在整个过程中，猫的得分从来没有超过过老鼠，问共有多少种可能的比赛得分过程？
算法大致就是：看成N个数入栈，出栈M次，求入栈出栈总共有多少种可能（这是我在CSDN看到一位GG的思路，觉得挺好就实现了一下）
import java.util.Stack;
/**
*猫和老鼠做游戏，其中猫赢了M次，老鼠赢了N次(N>M)
*且中间过程中没有一次猫赢的次数超过老鼠
*
*可以把问题看成是N次入栈操作，M次出栈操作，总共有多少种方式,递归调用
*/
public class CatAndMouse {
static final int M = 2;
static final int N = 4;
static int count = 0;//记录总数
public static void main(String[] args) {
nextStep(0,0,true,0);
System.out.println("最多可能比赛得分过程："+count);
}
/*递归调用函数，下一步的操作，判断下一次可能的操作，判断是否执行到完毕
* next ? true 入栈，false 出栈
* stackSize 表示栈的大小
*/
public static void nextStep(int countN,int countM,boolean next,int stackSize){
if(next){
stackSize++;//入栈
countN++;
}
else{
stackSize--;//出栈
countM++;
}
if(countN<N){//接着入栈
nextStep(countN,countM,true,stackSize);
}
if(countM<M && stackSize>0){//接着出栈
nextStep(countN,countM,false,stackSize);
}
if(countN==N && countM==M){//找到一种可能
count++;
}
}
}
#include<iostream>
using namespace std;
int main()
{
int i,j,m,n;
cout<<"m=? n=?"<<endl;
cin>>m>>n;
int **fun=new int *[m+1];
for(i=0;i<=m;i++)
fun[i]=new int[n+1];
fun[0][0]=0;
for(j=1;j<=n;j++)
fun[0][j]=1;
for(i=1;i<=m;i++)
for(j=i;j<=n;j++)
{
if(j==i)
fun[i][j]=fun[i-1][j];
else
fun[i][j]=fun[i-1][j]+fun[i][j-1];
}
cout<<"count="<<fun[m][n]<<endl;
system("pause");
}
