解题思路:
由题目可知,1元小孩通过,售票员手里的零钱+1,2元的小孩通过,售票员的零钱-1,初始的零钱数目是0。
不妨把1元的小孩设成1,把2元的小孩设成-1,建立一个由n个1和k个-1组成的m元动态数组,将数组全排列,将每种情况的数组从头累加,累加过程中结果若和<0,则此种排列方式不成立,如果累加到最后和一直非负,则排列方法有效。计算有效排列方式个数并输出。
注意事项:如果2元小孩数量比1元小孩多,那么不可能成立
参考代码:
#include <stdio.h>
#include <stdlib.h>
int route = 0;
int main()
{
int* a;
int m, n, k;/*n个小孩1,k个小孩2*/
scanf("%d%d%d", &m, &n, &k);
a = (int*)calloc(m, sizeof(int));
for (int i = 0; i < m; i++)
{
a[i] = -1;
}
for (int i2 = 0; i2 < n; i2++)
{
a[i2] = 1;
}
perm(a, 0, m - 1);
printf("%d", route);
}
int perm(int a[], int begin, int n)/*n是数组最后一个数的角标*/
{
if (begin == n)
{
int sum = 0;
int count = 0;
for (int i = 0; i <= n; i++)
{
sum = sum + a[i];
if (sum < 0)
{
break;
}
else
{
count++;
}
}
if (count == n + 1)
{
route++;
}
}
else
{
for (int k = begin; k <= n; k++)
{
swap(a, begin, k);
perm(a, begin + 1, n);
swap(a, begin, k);
}
}
}
int swap(int arr[], int a, int b)/*数组中arr[a]和arr[b]交换顺序*/
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
0.0分
1 人评分
C语言训练-自守数问题 (C语言代码) long long浏览:1067 |
C语言训练-素数问题 (C语言代码)浏览:998 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:1450 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:1007 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |
1118(求助_已解决)浏览:329 |
大神老白 (C语言代码)浏览:601 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:508 |
简单的a+b (C语言代码)浏览:641 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:1220 |