排队买票(递归全排列问题)-题解（C语言代码）

解题思路:

注意事项:

参考代码:

//买票找钱问题，

/*思路：

    将所有的排列找出，然后找出符合条件的组数

  核心思路：

    使用递归，将所有小盆友的可能排列顺序找出(难点)

    全排列问题

                       代码如下   */

#include<stdio.h>

int state=0;        //判断该排列是否符合

int num=0;          //计数符合的组合数

int ticket[100];    

int y;              //小盆友的总数

void swap(int k,int i)   //交换位置

{

int temp=ticket[k];

ticket[k]=ticket[i];

ticket[i]=temp;

}

void cheak(void)         //检查该排列是否符合条件

{

for(int i=0;i<y;i++)   //两元减一，一元加一

{

   if(ticket[i]==2)  

   state--;

   else

   state++;

   if(state<0)

   break;

    }

    if(state>=0)

    num++;

    state=0;

}

void perm(int k){    //递归检索每一种排列可能

if(k==y)         //结束条件

{

cheak();     //每一种排列检查一次

}

else{

for (int i=k;i<y;i++){

       swap(k,i);   //交换

       perm(k+1);   //进行下一维度的排列

       swap(k,i);   //将值换回，保证不重复且数据不变

           }

      }

}

int main()

{

int m,n;

scanf("%d%d%d",&y,&m,&n);

if(m<n)

printf ("0");

else{

for (int i=0;i<y;i++)  //将小盆友的零钱值赋给数组

{

if(i<m)

ticket[i]=1;

else 

ticket[i]=2;

}

perm(0);              //入口，开始递归检索

printf("%d",num);

}

return 0;

}