算法笔记 入门模拟

本文将介绍一些比较简单的模拟题。

一、简单模拟

模拟题是一类 “题目怎么说，你就怎么做” 的题目，如果实现起来不太麻烦，就可以称之为 “简单模拟”。这类题目不涉及算法，完全只是根据题目描述来进行代码的编写，考察代码能力。

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

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>

int main(){
    int i, n;
    scanf("%d", &n);
    for (i = 0; n > 1; i++){
        if (n % 2 == 0)  n /= 2;
        else if(n % 2 != 0)  n = (3 * n + 1) / 2;
    }
    printf("%d", i);
    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>

int main(){
    int i, n;
    int tempschool, tempscore;
    int maxschool, maxscore;
    maxschool = 1;
    maxscore = 0;
    scanf("%d", &n);
    int *school = (int*)calloc(sizeof(int), n + 1);
    for (i = 0; i <= n; i++)  school[i] = 0;
    for (i = 0; i < n; i++){
        scanf("%d %d", &tempschool, &tempscore);
        school[tempschool] += tempscore;
        if (school[tempschool] > maxscore){
            maxschool = tempschool;
            maxscore = school[tempschool];
        }
    }
    printf("%d %d\n", maxschool, maxscore);
}

​

二、查找元素

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

一般来说，如果需要在一个比较小范围的数据集里进行查找，直接遍历；

如果需要查找的范围比较大，可以用二分查找等算法来更快地查找。

【Codeup】问题 B: 找x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

int main(){
    int i,n, target;
    int *num = (int*)calloc(sizeof(int), 300);
    while (scanf("%d", &n) != EOF){
        for (i = 0; i < n; i++)  scanf("%d", &num[i]);
        scanf("%d", &target);
        for (i = 0; i < n; i++)
            if (num[i] == target){
                printf("%d\n", i);
                break;
            }
        if (i == n)  printf("%d\n", -1);
    }
}

​

三、图形输出

题目会定一些规则，需要学生根据规则来进行画图。这种题目一般有两种做法：

①通过规律，直接进行输出。

②定义一个二维字符数组，通过规律填充之，然后输出整个二维数组。

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

通过判断数字能否被 2 整除，进而判断数字的奇偶，从而确定打印的行数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int main(){
    int i, j;
    int n, n2;
    char c;
    scanf("%d %c", &n, &c);
    for (i = 0; i < n; i++)  printf("%c", c);
    printf("\n");
    n2 = n % 2 == 0 ? n / 2 : n / 2 + 1;
    for (i = 2; i < n2; i++){
        printf("%c", c);
        for (j = 0; j < n - 2; j++)  printf(" ");
        printf("%c\n", c);
    }
    for (i = 0; i < n; i++)  printf("%c", c);
}

​

四、日期处理

此类题目往往需要处理平年和闰年、大月和小月等问题，因此细节比较繁杂。

【Codeup】问题 A: 日期差值

  1. 定义一个数组，用于存储平年和闰年下每月的天数

  2. 假设第二个日期更大（如果不是就交换它们）

  3. 分别求得每个日期的年月日

  4. 设置累加器(即日期差值)，累加器累加后更小时间的年月日对应增加，直至两日期相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>

int isLeap(int year){  // 判断是否是闰年 是则输出1 不是则输出0
    if (year % 400 == 0)  return 1;  // 能被400整除
    else if (year % 4 == 0 && year % 100 != 0)  return 1;  //能被4整除且不能被100整除
    else return 0;
}

int main(){
    int Dvalue;
    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}};
    int time1, year1, month1, day1;
    int time2, year2, month2, day2;
    while(scanf("%d %d",&time1,&time2)!=EOF){
        if (time1 > time2){
            int temp = time2;
            time2 = time1;
            time1 = temp;
        }
        year1 = time1 /10000;  month1 = (time1 % 10000) / 100;  day1 = (time1 % 100);
        year2 = time2 /10000;  month2 = (time2 % 10000) / 100;  day2 = (time2 % 100);
    
        Dvalue = 1;
        while (year1 < year2 - 1){
            year1++;
            Dvalue += isLeap(year1) ? 366 : 365;
        }
        while (year1 != year2 || month1 != month2 || day1 != day2){
            day1++;
            if (day1 == (month[month1][isLeap(year1)] + 1)){
                month1++;
                day1 = 1;
            }
            if (month1 == 13){
                year1++;
                month1 = 1;
            }
            Dvalue++;
        }
        printf("%d\n", Dvalue);
        }
    
    return 0;
}

​

五、进制转换

对两个不同进制，应该如何进行相互转换？

将一个 P 进制的数，转换为 Q 进制，需要分为两步：

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

对一个十进制数 y = d1d2······dn ，它可以写成这样的形式：

y = d1 * 10 n - 1 + d2 * 10 n - 2 + ······+ dn - 1 * 10 + dn

同样的，一个 P 进制数 x= a1a2······an ，它可以通过以下形式转换成十进制数：

x = a1 * P n - 1 + a2 * P n - 2 + ······+ an - 1 * P + an

此公式可以很容易通过循环实现：

1
2
3
4
5
6
7
8
9
10
11
/* 
x：需要转换的数字
y：转换后的十进制数
product：P的n次方
*/

for (y = 0, product = 1; x != 0; ){
	y = y + (x % 10) * product;  // x % 10 以便获得 x 的个位数
	x = x / 10;  // 去除已经被转换的个位
	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；

因此，十进制数 11 的二进制表示为 1011。

除基取余法的代码实现：

1
2
3
4
5
6
7
8
9
10
11
/*
y：被转换的十进制数
转换为Q进制数
转换结果存放于数组z中，num为数组下标
*/
int z[40];
int num = 0;
while(y != 0){
	z[num++] = y % Q;
	y = y / Q;
}

【PAT B1022】D进制的A+B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main(){
    int a, b, c, d;
    scanf("%d %d %d", &a, &b, &d);
    c = a + b;
    int z[40] = {0};
    int num = 0;
    while (c != 0){
        z[num++] = c % d;
        c /= d;
    }
    for (num > 0 ? num-- : 1; num >= 0; num--)  printf("%d", z[num]);  
    // 当 a+b==0 时，应输出一个0，而不是什么都不输出
}

​

六、字符串处理

字符串处理在考试中十分常见，也是能很好体现代码能力的一种题型。对于这种题型，一般需要仔细分析清楚题目中的输入和输出格式才能顺利解决题目。部分题目还需要考虑实现逻辑和细节及边界情况。

【Codeup】问题 I: 【字符串】回文串

  • 假设字符串下表从0开始

  • “回文串”正读反读都一样，用双指针判断两半边是否相等

  • 通过 strlen() 获得字符串长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <string.h>
int main(){
    char str[256];
    gets(str);
    int i;
    int len = strlen(str);  // 字符串长度
    for (i = 0; i < (len / 2); i++){
        if(str[i] != str[len - 1 - i]){
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}

【PAT B1009】说反话

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

注意点：

最后一个单词之后输出空格会导致 OJ 系统判断“格式错误”

法1：

由于 PAT 是单点测试，因此产生了下面更简洁的方法，即使用 EOF 来判断单词是否已经输入完毕

在编译器中测试时，系统并不知道什么时候输入结束，因此需要用 Ctrl + Z + Enter 告诉系统已经到达 EOF ，循环才会结束。

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main(){
	int i;
	int num = 0;  // 单词的个数
	char ans[90][90];
	while (scanf("%s", ans[num]) != EOF)  num++;
	for (i = num - 1; i >= 0; i--){
		printf("%s", ans[i]);
		if(i > 0)  printf(" ");  // 输出单词之间的间隔
	}
}

法2：

普通方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h>
int main(){
	
	char str[90];
	gets(str);
	int i, len, r, h;  // len为字符串长 r为行 h为列
	len = strlen(str);
	r = h = 0;
	char ans[90][90];
	for (i = 0; i < len; i++){
		if (str[i] != ' ')  ans[r][h++] = str[i];
		else{  // 如果是空格，说明一个单词已经结束，行++，列置零
			ans[r][h] = '\0';
			r++;
			h = 0;
		}
	}
	for (i = r; i >= 0; i--){
		printf("%s", ans[i]);
		if (i > 0)  printf(" ");
	}
}

​

参考

  • 算法笔记