票价问题 —— 两种递归处理

本文主要是介绍票价问题 —— 两种递归处理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

公园票价为5角。假设每位游客只持有两种币值的货币：5角、1元。
再假设持有5角的有m人，持有1元的有n人。
由于特殊情况，开始的时候，售票员没有零钱可找。
我们想知道这m+n名游客以什么样的顺序购票则可以顺利完成购票过程。
显然，m < n的时候，无论如何都不能完成；
m>=n的时候，有些情况也不行。比如，第一个购票的乘客就持有1元。
请计算出这m+n名游客所有可能顺利完成购票的不同情况的组合数目。

注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名游客交换位置并不算做一种新的情况来计数。

第一种递归：从后向前递归

递归式分析：

当最后一个人（第m+n个）持有1元，则他前面有m个人持有5角，有n-1个人持有1元，此时的情况可以缩小为f(m,n-1)

当最后一个人（第m+n个）持有5角，则他前面有m-1个人持有5角，有n人持有1元，此时的情况可以缩小为f(m-1,n)

import java.util.Scanner;public class Main {public static int f1(int m, int n) {if (m < n)return 0;if (n == 0)return 1;return f1(m - 1, n) + f1(m, n - 1);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();System.out.println(f1(m, n));}
}

第二种递归：从前向后递归

import java.util.Scanner;public class Main {static int count = 0;static int have = 0;public static void f2(int begin, int end, int m, int n) {if (begin > end) {count++;} else {if (m >= 1) {have += 5;f2(begin + 1, end, m - 1, n);have -= 5; }if (n >= 1 && have >= 5){have -= 5;f2(begin + 1, end, m, n - 1);have += 5; }}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int total = m + n;f2(1, total, m, n);System.out.println(count);}
}

这篇关于票价问题 —— 两种递归处理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---