蓝桥杯 – 第36页 – 柳婼の blog

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

问题描述

　　0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入格式

　　一行，包含一个整数n

输出格式

　　一行，包含一组10个数字的全排列

样例输入

样例输出

0123456789

数据规模和约定

　　0 < n <= 10!
分析：啊我才发现有一个超好用的库函数……完全不用自己实现全排列。。竟然自己还那么笨的用下面的深度优先搜索的办法……next_permutation函数。。在algorithm里面，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s = "0123456789";
    int n;
    cin >> n;
    int cnt = 1;
    do {
        if(cnt == n) {
            cout << s;
            break;
        }
        cnt++;
    }while(next_permutation(s.begin(), s.end()));
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string s = "0123456789";

int n;

cin >> n;

int cnt = 1;

do {

if(cnt == n) {

cout << s;

break;

}

cnt++;

}while(next_permutation(s.begin(), s.end()));

return 0;

}

下面是那个笨方法。。。
假设有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个需要放置数字的位置。
深度优先搜索：

void dfs(int step) {
    for (int i = 0; i <= 9; i++) {
        if (book[i] == 0) { //如果当前数字i没有被使用过
            a[step] = i; //就把当前位置放上这个数字i
            book[i] = 1; //同时不要忘记把book[i]标记为1
            dfs(step + 1); //深度优先搜索下一步
            book[i] = 0; //表示收回当前的数字
        }
    }
}


还有一个循环出口没有写。从step = 0开始执行，当当前的步骤已经step == 10的时候，
因为我们需要考虑的是0~9位置的摆放数字情况，当step时候不用执行，可以return作为出口了。
因为题目要求我们输出第n个全排列的组合是什么，那么
int cou = 0;
每当 step == 10 一组全排列完成的时候，
cou++;
直到 cou == n 的时候输出a数组中所有的数字。
所以代码描述为：


if (step == 10) {
    cou++;
    if (cou == n) {
        for (int i = 0; i <= 9; i++) {
            cout << a[i];
        }
    }
    return;
}


该题的解答完整代码如下：


#include <iostream>
using namespace std;
int n;
int book[10];
int a[10];
int cou = 0;
void dfs(int step) {
    if (step == 10) {
        cou++;
        if (cou == n) {
            for (int i = 0; i <= 9; i++) {
                cout << a[i];
            }
        }
        return;
    }
    
    for (int i = 0; i <= 9; i++) {
                if (book[i] == 0) {
                        a[step] = i;
                        book[i] = 1;
                        dfs(step + 1);
                        book[i] = 0;
                    }
            }
}

int main() {
        cin >> n;
        dfs(0);
      return 0;
}

void dfs(int step) {

for (int i = 0; i <= 9; i++) {

if (book[i] == 0) { //如果当前数字i没有被使用过

a[step] = i; //就把当前位置放上这个数字i

book[i] = 1; //同时不要忘记把book[i]标记为1

dfs(step + 1); //深度优先搜索下一步

book[i] = 0; //表示收回当前的数字

}

还有一个循环出口没有写。从step = 0开始执行，当当前的步骤已经step == 10的时候，

因为我们需要考虑的是0~9位置的摆放数字情况，当step时候不用执行，可以return作为出口了。

因为题目要求我们输出第n个全排列的组合是什么，那么

int cou = 0;

每当 step == 10 一组全排列完成的时候，

cou++;

直到 cou == n 的时候输出a数组中所有的数字。

所以代码描述为：

if (step == 10) {

cou++;

if (cou == n) {

for (int i = 0; i <= 9; i++) {

cout << a[i];

}

return;

}

该题的解答完整代码如下：

#include <iostream>

using namespace std;

int n;

int book[10];

int a[10];

int cou = 0;

void dfs(int step) {

if (step == 10) {

cou++;

if (cou == n) {

for (int i = 0; i <= 9; i++) {

cout << a[i];

}

return;

}

for (int i = 0; i <= 9; i++) {

if (book[i] == 0) {

a[step] = i;

book[i] = 1;

dfs(step + 1);

book[i] = 0;

}

int main() {

cin >> n;

dfs(0);

return 0;

}

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

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

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n > 0) {
        int *a = new int [n];
        int b;
        int count = 1;
        int temp = 1;
        cin >> a[0];
        b = a[0];
        for(int i = 1; i < n; i++) { cin >> a[i];
            if (a[i] == a[i - 1]) {
                temp++;
                if (temp > count) {
                    count = temp;
                    b = a[i];
                }
            } else {
                temp = 1;
            }
        }
        cout << b;
        delete [] a;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if (n > 0) {

int *a = new int [n];

int b;

int count = 1;

int temp = 1;

cin >> a[0];

b = a[0];

for(int i = 1; i < n; i++) { cin >> a[i];

if (a[i] == a[i - 1]) {

temp++;

if (temp > count) {

count = temp;

b = a[i];

}

} else {

temp = 1;

}

cout << b;

delete [] a;

}

return 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)

#include <iostream>
using namespace std;
int f(int m, int n) {
    if (m < n) return 0;
    if(n == 0) return 1;
    return f(m - 1, n) + f(m, n - 1);
}
int main() {
    int m, n;
    cin >> m >> n;
    cout << f(m, n);
    return 0;
}

#include <iostream>

using namespace std;

int f(int m, int n) {

if (m < n) return 0;

if(n == 0) return 1;

return f(m - 1, n) + f(m, n - 1);

}

int main() {

int m, n;

cin >> m >> n;

cout << f(m, n);

return 0;

}