学霸的迷宫-蓝桥杯算法提高-广搜 bfs 经典问题

用广度优先搜索解决。bfs。100分。

 

出现次数最多的整数-蓝桥杯算法训练

问题描述
编写一个程序,读入一组整数,这组整数是按照从小到大的顺序排列的,它们的个数N也是由用户输入的,最多不会超过20。
然后程序将对这个数组进行统计,把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同,即并列第一,
那么只打印比较小的那个值。
输入格式:第一行是一个整数N,N不超过20;接下来有N行,每一行表示一个整数,并且按照从小到大的顺序排列。
输出格式:输出只有一行,即出现次数最多的那个元素值。
输入输出样例
样例输入
5
100
150
150
200
250
样例输出
150

之前一直是80分。。后来才知道其中有两组数据是n < 0。。。//你说n不大于20,但是可以小于0呀。。你说的很对。。我无言以对。。 所以加了一个if(n > 0)的判断。。。就通过了。。

 

 

未名湖边的烦恼-蓝桥杯算法训练题-递推/递归

问题描述
每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)

输入格式
两个整数,表示m和n
输出格式
一个整数,表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈[0,18]
问题分析

分析:f(m, n)表示m人还鞋,n人租鞋的情况下排序种数
1、如果 m < n 还鞋的如果比租鞋的少,那肯定无解 return 0;
2、如果 n == 0 鞋没人租 那肯定就一个解 全是还鞋的 return 1;
排除了 m < n 和 n == 0 的情况,递推过程如下: f(m, n) -> f(m – 1, n) + f(m, n – 1) -> …- > f(5, 1) + f(4, 2) + f(3, 3) -> f(4, 1) + f(3, 2) -> f(3, 1) + f (2, 2) -> f(2, 1) -> f (1, 1)