问题描述

有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。售票员没有零钱，问

这些小孩共有多少种排队方法，使得售票员总能找得开零钱。注意：两个拿一元零钱的小孩，他们的位置

互换，也算是一种新的排法。（M<=10）

输入

输入一行，M,N,K(其中M=N+K,M<=10).

输出

输出一行，总的排队方案。

输入样例

4 2 2

输出样例

8

/***********************************************
 题目可能不是很难，和排列组合有关，我的数学不是
 很好但这题能想到解法，不过却想了很久不知道怎么
 表达这个解法，开始用想用普通数组通过递归求解。
 没解决，最后终于想到了二叉树，呵呵，总算解决了
 不过遗憾，开始没考虑特殊数据 1 1 0 ，WA了一次
 题目 M<=10,以下程序不受此限制。
   --- 2007--6--5 ---
 ***********************************************/

#include <stdio.h>
#include <malloc.h>

typedef struct tree{
 int i,dibs;
 struct tree *left,*right,*parent;
}TREE;

TREE* GetTreeNode(void){
 TREE *temp;
 temp = (TREE*)malloc(sizeof(TREE));
 temp->dibs = temp->i = 0;
 temp->left = temp->right = temp->parent = NULL;
 return temp;
}

void CreateTree(int n, int k, TREE **p){
 TREE *temp;
 if(n==0 && k==0)
  return ;
 if(n >= 1){
  temp = GetTreeNode();
  temp->dibs = ((*p)->dibs)+1;
  temp->i = n;
  temp->parent = *p;
  (*p)->left = temp;
  CreateTree(n-1,k,&temp);
 }  
 if(k >= 1 && (*p)->dibs >= 1){
  temp = GetTreeNode();
  temp->dibs = ((*p)->dibs)-1;
  temp->i = k;
  temp->parent = *p;
  (*p)->right = temp;
  CreateTree(n,k-1,&temp);
 }
}

int main(){
 int   m,n,k,sum,t,flag;
 TREE  *head,*temp;
 scanf("%d%d%d",&m, &n, &k);
 head = GetTreeNode();
 head->dibs = 1;
 head->i = n;
 CreateTree(n-1, k, &head);
 if(m == 1 && n==1){
  printf("1\n");
  return 0;
 }
 for(sum=0, flag=t=1; head->parent!=NULL||head->left||head->right;){
  head->i = t * head->i;
  t = head->i;
  if(head->left){
   flag++;
   temp = head->left;
   head->left = NULL;
   head = temp;
  }
  else if(head->right){
   flag++;
   temp = head->right;
   head->right = NULL;
   head = temp;
  }
  else {
   temp = head;
   head = head->parent;
   free(temp);
   if(flag == m)
    sum += t;
   t = 1;
   flag--;
  }
 }
 printf("%d\n",sum);
 return 0;
}

评论