算法 – 第8页

1007. 素数对猜想 (20)-PAT乙级真题

让我们定义 dn 为：dn = pn+1 – pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

输入格式：
每个测试输入包含1个测试用例，给出正整数N。

输出格式：
每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：
20

输出样例：
4

分析：判断素数的函数isprime这样写：对于数字a，i从2到根号a，如果a能够被其中一个i整除，说明i不是素数，return false，否则说明a是素数return true；对于输入数据N，for循环中的i从5到N依次判断i-2和i是否是素数，如果都是素数，则统计个数的cnt++，最后输出cnt即可～

#include <iostream>
using namespace std;
bool isprime(int a) {
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0) return false;
    return true;
}
int main() {
    int N, cnt = 0;
    cin >> N;
    for (int i = 5; i <= N; i++)
        if (isprime(i-2) && isprime(i)) cnt++;
    cout << cnt;
    return 0;
}

#include <iostream>

using namespace std;

bool isprime(int a) {

for (int i = 2; i * i <= a; i++)

if (a % i == 0) return false;

return true;

}

int main() {

int N, cnt = 0;

cin >> N;

for (int i = 5; i <= N; i++)

if (isprime(i-2) && isprime(i)) cnt++;

cout << cnt;

return 0;

}

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;

}