电影票有关问题

电影票问题

一、题目

有一个人站在电影院门口卖票，票价50，一开始手上没有找零的钱，现在有两种人来买票，A拿着100元的钱，人数为m(m<20)，B拿着50元的钱，人数为n(n<20)。卖票的人必须用从B类人中那里得来钱找给A，所以卖票的顺序是有限制的。

要求写一个程序打印出所有的买票序列：
例如：m =2 ,n = 3;
BABAB
BBAAB
BBBAA
BBABA

二、解法→递归法

1、思想

金句：涉及“状态转换和记录”的都可以用递归的方法求解

模拟所有人买票的全过程，

变量假设

假设拿着100元钱的人A的人数有m 人，拿着50元钱的B的人数有n 人，

某一时刻已经买票的A有a 人，B有b 人

子问题

如果进来的一个人是A，需要判断条件 ①a<m且②a<b

如果进来的一个人是B，需要判断条件 b<n

终止条件

所有的人都已经买票完毕，即有a+b==m+n

   1. #include <stdio.h>
   2. char str[500];
   3. int n, m;
   4. void oper(int a, int b,int m, int n)
   5. {
   6.         if (a + b == m + n)
   7.                 printf("%s/n", str);
   8.         else {
   9.                 if (a < m && a < b) {
10.                         str[a + b] = 'A';
11.                         oper(a + 1, b, m, n);
12.                 }
13.                 if (b < n) {
14.                         str[a + b] = 'B';
15.                         oper(a, b + 1, m, n);
16.                 }
17.         }
18. }
19. int main()
20. {
21.         while (scanf("%d%d", &m, &n) == 2)
22.         {
23.                 if (n < 0 || m < 0 || m > n)
24.                         printf("No result!/n");
25.                 else {
26.                         str[m + n] = 0;
27.                         oper(0, 0, m, n);
28.                 }
29.         }
30.         return 0;
31. }

电影票有关问题

相关推荐