《算法笔记》学习记录-第三章 入门篇（1）——入门模拟

《算法笔记》学习记录-第三章 入门篇（1）——入门模拟

• 3.1 简单模拟
• • 【PAT B1001】害死人不偿命的（3n+1）猜想
  • 【PAT B1032】挖掘机技术哪家强
• 3.2 查找元素
• • 【codeup 1934】找x
• 3.3 图形输出
• • 【PAT B1036】跟奥巴马一起编程
• 3.4 日期处理
• • 【codeup 1928】日期差值
• 3.5 进制转换
• • 【PAT B1022】D进制的A+B
• 3.6 字符串处理
• • 【codeup 5901】回文串
  • 【PAT B1009】说反话

3.1 简单模拟

“题目怎么说，你就怎么做”；不涉及算法

【PAT B1001】害死人不偿命的（3n+1）猜想

题目描述：

卡拉兹(Callatz)猜想：

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

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？

输入格式：

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

输出格式：

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

输入样例：

3

输出样例：

5

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
栈限制 8192 KB

思路：

用循环语句反复判断n是否为1，为1时退出循环；

n不为1时，判断奇偶数：

• 如果为偶数，n为 $n/2$
• 如果为奇数，n为 $(3n+1)/2$

每次判断完计算完n后要计算步数加1；

参考代码：

#include <cstdio>
int main(){
int n, step = 0;
scanf("%d", &n); // 输入题目给出的n
while(n != 1){ // 循环判断n是否为1
if(n % 2 == 0) n = n / 2; // 如果是偶数
else n = (3 * n + 1) / 2; // 如果是奇数
step++; // 计数器加1
}
printf("%d\\n", step);
return 0;
}

【PAT B1032】挖掘机技术哪家强

题目描述：

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：

输入在第 1 行给出不超过

10

5

10^5

105的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

6
3 65
2 80
1 100
2 70
3 40
3 0

输出样例：

2 150

代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
栈限制 8192 KB

思路： 用数组 school[maxn] 记录每个学校的总分，初值为0。对每个读入的学校 schID 与其对应的分数 score，令 school[schID] += score。

令变量 k 记录最高总分的学校编号，变量 MAX记录最高总分，初值为 -1。由于学校是连续编号的，因此枚举编号 1~N，不断更新 k 和 MAX 即可。

参考代码：

#include <cstdio>
const int maxn = 100010;
int school[maxn] = {0}; // 记录每个学校的总分
int main(){
int n, schID, score;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &schID, &score); // 学校ID、分数
school[schID] += score; // 学校schID的总分增加score
}
int k = 1, MAX = –1; // 最高总分的学校ID以及其总分
for(int i = 1; i <= n; i++){ // 从所有学校中选出总分最高的一个
if(school[i] > MAX){
MAX = school[i];
k = i;
}
}
printf("%d %d\\n", k, MAX); // 输出最高总分的学校ID及其总分
return 0;
}

3.2 查找元素

给定一些元素，然后查找某个满足某条件的元素。

一般来说，如果需要在一个比较小范围的数据集里进行查找，那么直接遍历每一个数据即可；如果需要查找的范围比较大，那么可以用二分查找等算法来进行快速的查找。

【codeup 1934】找x

题目描述：

输入一个数n(

1

≤

n

≤

200

1≤n≤200

1≤n≤200)，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

输入:

测试数据有多组，输入n(

1

≤

n

≤

200

1≤n≤200

1≤n≤200)，接着输入n个数，然后输入x。

输出:

对于每组输入,请输出结果。

样例输入:

4
1 2 3 4
3

样例输出:

2

思路：

设定一个数组a，存放n个数。遍历数组a，寻找某个下标k，使得a[k]==x成立。

如果找到，则输出k，并退出查询；如果当k遍历完之后还没有找到x，那么输出-1。

参考代码：

#include <cstdio>
const int maxn = 210;
int a[maxn]; // 存放n个数
int main(){
int n, x;
while(scanf("%d", &n) != EOF){
for(int i = 0; i < n; i++){
scanf("%d", &a[i]); // 输入n个数
}
scanf("%d", &x); // 输入预查询的数
int k; // 下标
for(k = 0; k < n; k++){ // 遍历数组
if(a[k] == x){ // 如果找到了x
printf("%d\\n", k); // 输出对应的下标
break; // 退出查找
}
}
if(k == n){ // 如果没有找到
printf("-1\\n"); // 输出-1
}
}
return 0;
}

3.3 图形输出

图形，是由若干字符组成的，因此只需要弄清楚规则就能编写代码。 两种做法：

• 通过规律，直接进行输出；
• 定义一个二维字符数组，通过规律填充之，然后输出整个二维数组。

【PAT B1036】跟奥巴马一起编程

题目描述：

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长 N（3≤N≤20）和组成正方形边的某种字符 C，间隔一个空格。

输出格式：

输出由给定字符 C 画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的 50%（四舍五入取整）。

输入样例：

10 a

输出样例：

aaaaaaaaaa
a a
a a
a a
aaaaaaaaaa

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
栈限制 8192 KB

思路：

行数是列数的一半（四舍五入），因此：

• 当列数 col 为奇数时，行数 row = col / 2 + 1;
• 当列数 col 为偶数时，行数 row = col / 2。

分为三部分：

• 第1行：n个a，使用一个for循环
• 第2 ~ row-1行：先输出一个a，然后输出 col-2 个空格，最后再输出一个a
• 第 row 行：n个a，使用一个for循环

注意点： 整数除以2进行四舍五入的操作可以通过判断它是否是奇数来解决，以避免浮点数的介入。

参考代码：

#include <cstdio>
int main(){
int row, col; // 行、列
char c;
scanf("%d %c", &col, &c); // 输入列数、欲使用的字符
if(col % 2 == 1) row = col / 2 + 1; // col为奇数，向上取整
else row = col / 2; // col为偶数
// 第1行
for(int i = 0; i < col; i++){
printf("%c", c); // col个字符
}
printf("\\n");
// 第2 ~ row-1 行
for(int i = 2; i < row; i++){
printf("%c", c); // 每行的第一个a
for(int j = 0; j < col – 2; j++){
printf(" "); // col-2 个空格
}
printf("%c\\n", c); // 每行的最后一个a
}
// 第 row 行
for(int i = 0; i < col; i++){
printf("%c", c); // col 个字符
}
return 0;
}

3.4 日期处理

需要处理平年和闰年（由此产生的二月的天数区别）、大月和小月的问题。

【codeup 1928】日期差值

题目描述：

有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天。

输入：

有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD

输出：

每组数据输出一行，即日期差值

样例输入：

20130101
20130105

样例输出：

5

思路： 不妨假设第一个日期早于第二个日期（否则交换即可）。

求日期之间相差天数的题目思路：令日期不断加1天，直到第一个日期等于第二个日期为止，即可统计出答案。

具体处理时，如果当加了一天之后天数d等于当前月份m所拥有的天数加1，那么就令月份m加1、同时置天数d为1号（即把日期变为下一个月的1号）；如果此时月份m变为了13，那么就令年份y加1、同时置月份m为1月（即把日期变为下一年的1月）。

为了方便直接取出每个月的天数，给定一个二维数组int month[13][2]，用来存放每个月的天数，其中第二维为0时表示平年，为1时表示闰年。

注意：如果想要加快速度，只需要先把第一个日期的年份不断加1，直到与第二个日期的年份相差1为止，期间根据平年或闰年来累加365天或者366天即可。之后再进行不断令天数加1的操作。

参考代码：

#include <cstdio>
int month[13][2] = { // 平年和闰年的每个月的天数
{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30},
{31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
};
bool isLeap(int year){ // 判断是否是闰年
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
int main(){
int time1, y1, m1, d1;
int time2, y2, m2, d2;
while(scanf("%d%d", &time1, &time2) != EOF){
if(time1 > time2){ // 第一个日期晚于第二个日期，则交换
int temp = time1;
time1 = time2;
time2 = temp;
}
y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
int ans = 1; // 记录结果
// 第一个日期没有达到第二个日期时进行循环
// 即 !((y1 == y2) && (m1 == m2) && (d1 == d2))
while(y1 < y2 || m1 < m2 || d1 < d2){
d1++; // 天数加1
if(d1 == month[m1][isLeap(y1)] + 1){ // 满当月天数
m1++; // 日期变为下个月的1号
d1 = 1;
}
if(m1 == 13){ // 月份满12个月
y1++; // 日期变为下一年的1月
m1 = 1;
}
ans++; // 累计
}
printf("%d\\n", ans); // 输出结果
}
return 0;
}

3.5 进制转换

对于一个 P 进制的数，如果要转换为 Q 进制，需要分为两步：

① 将 P 进制数 x 转换为十进制数 y 。

对一个十进制的数

y

=

d

1

d

2

.

.

.

d

n

y=d_1d_2…d_n

y=d1​d2​…dn​，它可以写成这个形式：

y

=

d

1

∗

10

n

−

1

+

d

2

∗

10

n

−

2

+

.

.

.

+

d

n

−

1

∗

10

+

d

n

y = d_1 * 10^{n-1} + d_2 * 10^{n-2} + … + d_{n-1} * 10 + d_n

y=d1​∗10n−1+d2​∗10n−2+…+dn−1​∗10+dn​

同样的，如果 P 进制数 x 为

a

1

a

2

.

.

.

a

n

a_1a_2…a_n

a1​a2​…an​，那么它写成下面这个形式之后使用十进制的加法和乘法，就可以转换为十进制数 y：

y

=

a

1

∗

P

n

−

1

+

a

2

∗

P

n

−

2

+

.

.

.

+

a

n

−

1

∗

P

+

a

n

y = a_1 * P^{n-1} + a_2 * P{n-2} + … + a_{n-1} * P + a_n

y=a1​∗Pn−1+a2​∗Pn−2+…+an−1​∗P+an​

用循环实现这个公式：

int y = 0, product = 1; // product在循环中会不断乘P，得到1、P、P^2、P^3…
while(x != 0){
y = y + (x % 10) * product; // x % 10 是为了每次获取x的个数
x = x / 10; // 去掉x的个数
product = product * P;
}

② 将十进制数 y 转换为 Q 进制数 z。

采用“除基取余法”。“基”指将要转换成的进制 Q，因此除基取余的意思就是每次将待转化数除以 Q，然后将得到的余数作为低位存储，而商则继续除以 Q 并进行上面的操作，最后当商为 0 时，将所有位从高到低输出就可以得到 z。

举例，将十进制数11转换为二进制数：

11除以2，得商为5， 余数为1；
5除以2，得商为2，余数为1；
2除以2，得商为1，余数为0；
1除以2，得商为0，余数为1，算法终止。
将余数从后往前输出，得1011即为11的二进制数。

实现的代码（将十进制数 y 转换为 Q 进制，结果存放于数组 z）：

int z[40], num = 0; // 数组z存放Q进制数y的每一位，num为位数
do{
z[num++] = y % Q; // 除基取余
y = y / Q;
} while(y != 0); // 当商不为0时进行循环

z 数组从高位 z[num-1] 到低位 z[0] 即为 Q 进制 z，进制转换完成。

注意：使用 do…while 语句而不是 while 语句的原因是：如果十进制数 y 恰好等于 0，那么使用 while 语句将使循环直接跳出，导致结果出错（正确结果应当是数组 z 中存放了 z[0] = 0）。

【PAT B1022】D进制的A+B

题目描述：

输入两个非负 10 进制整数 A 和 B (

≤

2

30

−

1

≤2^{30} −1

≤230−1)，输出 A+B 的 D (

1

<

D

≤

10

1<D≤10

1<D≤10) 进制数。

输入格式：

输入在一行中依次给出 3 个整数 A、B 和 D。

输出格式：

输出 A+B 的 D 进制数。

输入样例：

123 456 8

输出样例：

1103

代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
栈限制 8192 KB

思路： 先计算 A+B（此时为十进制），然后把结果转换为 D 进制，而十进制转换为 D 进制的过程可以直接进行“除基取余法”。

参考代码：

#include <cstdio>
int main(){
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
int num = a + b;
int ans[31], num = 0; // ans存放 D 进制的每一位
do{ // 进制转换
ans[num++] = sum % d;
sum /= d;
} while(sum != 0);
for(int i = num – 1; i >= 0; i—){ // 从高位到低位进行输出
printf("%d", ans[i]);
}
return 0;
}

3.6 字符串处理

一般需要仔细分析清楚题目中的输入和输出格式才能顺利解决题目。

【codeup 5901】回文串

题目描述：

读入一串字符，判断是否是回文串。“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

输入：

一行字符串，长度不超过255。

输出：

如果是回文串，输出“YES”，否则输出“NO”。

样例输入：

12321

样例输出：

YES

思路：

假设字符串 str 的下标从0开始，由于“回文串”是正读和反读都一样的字符串，因此只需要遍历字符串的前一半（注意：不需要取到 i == len/2），如果出现字符 str[i] 不等于其对称位置 str[len – l – i]，就说明这个字符串不是“回文串”；如果前一半的所有字符 str[i] 都等于对应的对称位置 str[len – l – i]，那么说明这个字符串是“回文串”。

参考代码：

#include <cstdio>
#include <cstring>
const int maxn = 256;
// 判断字符串 str 是否是“回文串”
bool judge(char str[]){
int len = strlen(str); // 字符串长度
for(int i = 0; i < len / 2; i++){ // i 枚举字符串的前一半
if(str[i] != str[len – l – i]){ // 如果对称位置不同
return false; // 不是“回文串”
}
}
return true; // 是“回文串”
}
int main(){
char str[maxn];
while(gets(str)){ // 输入字符串
bool flag = judge(str); // 判断字符串str是否是“回文串”
if(flag == true){ // “回文串”
printf("YES\\n"); // 输出YES
} else{ // 不是“回文串”
printf("NO\\n"); // 输出NO
}
}
return 0;
}

【PAT B1009】说反话

题目描述：

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子。

输入样例：

Hello World Here I Come

输出样例：

Come I Here World Hello

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
栈限制 8192 KB

思路：

使用 gets 函数读入一整行，从左至右枚举每一个字符，以空格为分隔符对单词进行划分并按顺序存放到二维字符数组中，最后按单词输入顺序的逆序来输出所有单词。

注意点：

① 最后一个单词之后输出空格会导致“格式错误”。 ② 由于 PAT 是单点测试，因此产生了下面这种更简洁的方法，即使用 EOF 来判断单词是否已经输入完毕。

#include <cstdio>
int main(){
int num = 0; // 单词的个数
char ans[90][90];
while(scanf("%s", ans[num]) != EOF){ // 一直输入直到文件末尾
num++; // 单词个数加1
}
for(int i = num – 1; i >= 0; i—){ // 倒着输出单词
printf("%s", ans[i]);
if(i > 0) printf(" ");
}
return 0;
}

要注意，在黑框中手动输入时，系统并不知道什么时候到达了所谓的“文件末尾”，因此需要用<Ctrl + Z>组合键然后按键的方式来告诉系统已经到了EOF，这样系统才会结束 while。

参考代码：

#include <cstdio>
#include <cstring>
int main(){
char str[90];
gets(str);
int len = strlen(str), r = 0, h = 0; // r为行，h为列
char ans[90][90]; // ans[0]~ans[r]存放单词
for(int i = 0; i < len; i++){
if(str[i] != ' '){ // 如果不是空格，则存放至ans[r][h]，并令h++
ans[r][h++] = str[i];
} else{ // 如果是空格，说明一个单词结束，行r增加1，列h恢复至0
ans[r][h] = '\\0'; // 末尾是结束符\\0
r++;
h = 0;
}
}
for(int i = r; i >= 0; i—){ // 倒着输出单词即可
printf("%s", ans[i]);
if(i > 0) printf(" ");
}
return 0;
}