Code – 第265页

1006. 换个格式输出整数 (15)-PAT乙级真题

让我们用字母B来表示“百”、字母S表示“十”，用“12…n”来表示个位数字n（<10），换个格式来输出任一个不超过3位的正整数。例如234应该被输出为BBSSS1234，因为它有2个“百”、3个“十”、以及个位的4。

输入格式：
每个测试输入包含1个测试用例，给出正整数n（<1000）。

输出格式：
每个测试用例的输出占一行，用规定的格式输出n。

输入样例1：
234

输出样例1：
BBSSS1234

输入样例2：
23

输出样例2：
SS123

分析：因为n小于1000，所以数字不会超过百位～输入数据首先保存在a中，然后将a的每一个数字保存在int b[3]中，然后将b[2]、b[1]、b[0]中存储的数字看作输出次数依次输出B、S和12..b[0]～

#include <iostream>
using namespace std;
int main() {
    int a, i = 0;
    cin >> a;
    int b[3] = {0};
    while (a != 0) {
        b[i++] = a % 10;
        a = a / 10;
    }
    for (int k = 0; k < b[2]; k++)
        cout << "B";
    for (int k = 0; k < b[1]; k++)
        cout << "S";
    for (int k = 0; k < b[0]; k++)
        cout << k + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, i = 0;

cin >> a;

int b[3] = {0};

while (a != 0) {

b[i++] = a % 10;

a = a / 10;

}

for (int k = 0; k < b[2]; k++)

cout << "B";

for (int k = 0; k < b[1]; k++)

cout << "S";

for (int k = 0; k < b[0]; k++)

cout << k + 1;

return 0;

}

1004. 成绩排名 (20)-PAT乙级真题

读入n名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

输入格式：

每个测试输入包含1个测试用例，格式为
第1行：正整数n
第2行：第1个学生的姓名学号成绩
第3行：第2个学生的姓名学号成绩
… … …
第n+1行：第n个学生的姓名学号成绩
其中姓名和学号均为不超过10个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。

输出格式：

对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。

输入样例：
3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

输出样例：
Mike CS991301
Joe Math990112

分析：maxname和maxnum保存成绩最高的学生的姓名和学号，minname和minnum保存成绩最低的学生的姓名和学号，max和min保存当前的最高分和最低分，因为成绩区间为0-100，所以初始化时先令max = -1，min = 101。遍历所有数据，如果当前学生数据的分数比最大值大，那么更新max的值，并将他的姓名学号保存在maxname和maxnum中；如果当前学生数据的分数比最小值小，那么更新min的值，并将他的姓名学号保存在minname和minnum中。最后输出maxname、maxnum、minname和minnum～

#include <iostream>
using namespace std;
int main() {
    int n, max = -1, min = 101, score;
    cin >> n;
    string maxname, minname, maxnum, minnum, name, num;
    for (int i = 0; i < n; i++) {
        cin >> name >> num >> score;
        if (max < score) {
            max = score;
            maxname = name;
            maxnum = num;
        }
        if (min > score) {
            min = score;
            minname = name;
            minnum = num;
        }
    }
    cout << maxname << " " << maxnum << endl << minname << " " << minnum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, max = -1, min = 101, score;

cin >> n;

string maxname, minname, maxnum, minnum, name, num;

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

cin >> name >> num >> score;

if (max < score) {

max = score;

maxname = name;

maxnum = num;

}

if (min > score) {

min = score;

minname = name;

minnum = num;

}

cout << maxname << " " << maxnum << endl << minname << " " << minnum;

return 0;

}

1002. 写出这个数 (20)-PAT乙级真题

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。
输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10100。

输出格式：
在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：
1234567890987654321123456789

输出样例：
yi san wu

分析：用string接收输入，string的每一位数字累加到sum里面，再将sum转化为string类型的num，对num的每一位输出对应中文拼音～

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int sum = 0;
    string str[10] =  {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    for (int i = 0; i < s.length(); i++)
        sum += (s[i] - '0');
    string num = to_string(sum);
    for (int i = 0; i < num.length(); i++) {
        if (i != 0) cout << " ";
        cout << str[num[i] - '0'];
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int sum = 0;

string str[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

for (int i = 0; i < s.length(); i++)

sum += (s[i] - '0');

string num = to_string(sum);

for (int i = 0; i < num.length(); i++) {

if (i != 0) cout << " ";

cout << str[num[i] - '0'];

}

return 0;

}

1001. 害死人不偿命的(3n+1)猜想 (15)-PAT乙级真题

卡拉兹(Callatz)猜想：
对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？

输入格式：

每个测试输入包含1个测试用例，即给出自然数n的值。

输出格式：

输出从n计算到1需要的步数。

输入样例：
3

输出样例：
5

分析：count从0开始统计需要的步数，(n % 2 != 0) 表示n为奇数，当n为奇数，就令n = 3*n+1；之后将其砍掉一半，步数count+1，直到n == 1为止，最后输出count～

#include <iostream>
using namespace std;
int main() {
    int n, count = 0;
    cin >> n;
    while (n != 1) {
        if (n % 2 != 0) n = 3 * n + 1;
        n = n / 2;
        count++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0;

cin >> n;

while (n != 1) {

if (n % 2 != 0) n = 3 * n + 1;

n = n / 2;

count++;

}

cout << count;

return 0;

}

1045. 快速排序(25)-PAT乙级真题

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定N = 5, 排列是1、3、2、4、5。则：
1的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元；
尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元；
类似原因，4和5都可能是主元。
因此，有3个元素可能是主元。
输入格式：
输入在第1行中给出一个正整数N（<= 105）；第2行是空格分隔的N个不同的正整数，每个数不超过109。
输出格式：
在第1行中输出有可能是主元的元素个数；在第2行中按递增顺序输出这些元素，其间以1个空格分隔，行末不得有多余空格。
输入样例：
5
1 3 2 4 5
输出样例：
3
1 4 5

分析：对原序列sort排序，逐个比较，当当前元素没有变化并且它左边的所有值的最大值都比它小的时候就可以认为它一定是主元（很容易证明正确性的，毕竟无论如何当前这个数要满足左边都比他小右边都比他大，那它的排名【当前数在序列中处在第几个】一定不会变）～
如果硬编码就直接运行超时了…后来才想到这种方法～
一开始有一个测试点段错误，后来才想到因为输出时候v[0]是非法内存，改正后发现格式错误（好像可以说明那个第2个测试点是0个主元？…）然后加了最后一句printf(“\n”);才正确（难道是当没有主元的时候必须要输出空行吗…）

#include <iostream>
#include <algorithm>
#include <vector>
int v[100000];
using namespace std;
int main() {
    int n, max = 0, cnt = 0;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if(a[i] == b[i] && b[i] > max)
            v[cnt++] = b[i];
        if (b[i] > max)
            max = b[i];
    }
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) {
        if (i != 0) printf(" ");
        printf("%d", v[i]);
    }
    printf("\n");
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

int v[100000];

using namespace std;

int main() {

int n, max = 0, cnt = 0;

scanf("%d", &n);

vector<int> a(n), b(n);

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

scanf("%d", &a[i]);

b[i] = a[i];

}

sort(a.begin(), a.end());

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

if(a[i] == b[i] && b[i] > max)

v[cnt++] = b[i];

if (b[i] > max)

max = b[i];

}

printf("%d\n", cnt);

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

if (i != 0) printf(" ");

printf("%d", v[i]);

}

printf("\n");

return 0;

}

1035. 插入与归并(25)-PAT乙级真题

根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数N (<=100)；随后一行给出原始序列的N个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式：
首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行末不得有多余空格。
输入样例1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
输出样例1：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
输入样例2：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
输出样例2：
Merge Sort
1 2 3 8 4 5 7 9 0 6

分析：先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标，再将j指向从i+1开始，第一个不满足a[j] == b[j]的下标，如果j顺利到达了下标n，说明是插入排序，再下一次的序列是sort(a, a+i+2);否则说明是归并排序。归并排序就别考虑中间序列了，直接对原来的序列进行模拟归并时候的归并过程，i从0到n/k，每次一段段得sort(a + i * k, a + (i + 1) * k);最后别忘记还有最后剩余部分的sort(a + n / k * k, a + n);这样是一次归并的过程。直到有一次发现a的顺序和b的顺序相同，则再归并一次，然后退出循环～

注意：一开始第三个测试点一直不过，天真的我以为可以模拟一遍归并的过程然后在过程中判断下一步是什么。。然而真正的归并算法它是一个递归过程。。也就是先排左边一半，把左边的完全排列成正确的顺序之后，再排右边一半的。。而不是左右两边一起排列的。。后来改了自己的归并部分判断的代码就过了。。。｡◕‿◕｡

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, a[100], b[100], i, j;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);
    for (j = i + 1; a[j] == b[j] && j < n; j++);
    if (j == n) {
        cout << "Insertion Sort" << endl;
        sort(a, a + i + 2);
    } else {
        cout << "Merge Sort" << endl;
        int k = 1, flag = 1;
        while(flag) {
            flag = 0;
            for (i = 0; i < n; i++) {
                if (a[i] != b[i])
                    flag = 1;
            }
            k = k * 2;
            for (i = 0; i < n / k; i++)
                sort(a + i * k, a + (i + 1) * k);
            sort(a + n / k * k, a + n);
        }
    }
    for (j = 0; j < n; j++) {
        if (j != 0) printf(" ");
        printf("%d", a[j]);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, a[100], b[100], i, j;

cin >> n;

for (int i = 0; i < n; i++)

cin >> a[i];

for (int i = 0; i < n; i++)

cin >> b[i];

for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);

for (j = i + 1; a[j] == b[j] && j < n; j++);

if (j == n) {

cout << "Insertion Sort" << endl;

sort(a, a + i + 2);

} else {

cout << "Merge Sort" << endl;

int k = 1, flag = 1;

while(flag) {

flag = 0;

for (i = 0; i < n; i++) {

if (a[i] != b[i])

flag = 1;

}

k = k * 2;

for (i = 0; i < n / k; i++)

sort(a + i * k, a + (i + 1) * k);

sort(a + n / k * k, a + n);

}

for (j = 0; j < n; j++) {

if (j != 0) printf(" ");

printf("%d", a[j]);

}

return 0;

}