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

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

 

排列数(输出0~9的全排列)-蓝桥杯算法提高

问题描述
  0、1、2三个数字的全排列有六种,按照字母序排列如下:
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个(第1个为0123456789)。
输入格式
  一行,包含一个整数n
输出格式
  一行,包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
  0 < n <= 10!
分析:啊我才发现有一个超好用的库函数……完全不用自己实现全排列。。竟然自己还那么笨的用下面的深度优先搜索的办法……next_permutation函数。。在algorithm里面,代码如下:

下面是那个笨方法。。。
假设有10个位置,需要在10个位置上依次放置0~9这十个数字。
1.先走到第一个位置,此时放置一个当前可以放置的数字当中最小的那个数字。
2.在走到第二个位置,放置一个当前可以放置的数字当中最小的那个数字。

3.到第10个位置时候,所有的数字已经放置完毕,属于第一个全排列。
4.收回第10个位置上的数字,此时还是只可以放置9,那么再到第9个位置面前,收回位置上的数字。
5.在第9个位置处,我们此时可以放置的数字有9,那么第10个位置放8.属于第二个全排列。
6.收回第10、9、8位置的数字,此时可以在第8个位置放置8.

用一个数组标记当前的数字是否已经被使用过了。
int book[10]; //一开始的时候没有被使用,初始化值为0.使用过了之后标记为1.
int a[10]; // 表示这10个需要放置数字的位置。
深度优先搜索:

 

 

 

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

问题描述
编写一个程序,读入一组整数,这组整数是按照从小到大的顺序排列的,它们的个数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)