问题描述 有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;}  

评论