哔哩大学计算机学院-C语言编程2023-P41-P43练习

https://www.bilibili.com/video/BV1cq4y1U7sg

求最大公约数

给定两个数，求这两个数的最大公约数，例如：输入20、40，输出20。

首先有一个思路，求最大公约数可以怎么样呢？

因为是最大的公约数，我们是不是可以从上往下求，比方说设置一个中间变量tmp，令tmp的值为输入的两个数中的最大的那个数值，当tmp不能被两个数整除的时候，就往下减1，直至tmp可以同时被两个数整除，即%后余0，即为最大公约数。

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

int main()
{
	int m = 0;
	int n = 0;
	int tmp = 0;
	scanf("%d%d", &m, &n);
	tmp = m > n ? m : n; // 三目运算符，如果m>n则m赋值给tmp，否之赋值n给tmp
	while (1)
	{
		if (m % tmp == 0 && n % tmp == 0)
			break;
		tmp--;
	}
	printf("最大公约数：%d\n", tmp);

	return 0;
}

三目运算符

三目运算符也叫条件运算符，结合方向是从右至左。

基本形式: <表达式1> ? <表达式2> : <表达式3>

比较原理：表达式1是否为真，如果为真，执行表达式2，否则执行表达式3.

例如：tmp = m > n ? m : n; // 如果m>n则m赋值给tmp，否之赋值n给tmp

如果在表达式中含有其他运算符，得考虑符号的优先等级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//用三目运算符比较三个数的大小
#include<stdio.h>
 
int main()
{
    int a = 3,b = 4,c = 5,max1,max2,max3;//max用来存储最大的数字
 
//有三种不同的写法：
//max1的原理：先求A和B的最大值，再去和c比较
//max2的原理：先让A和B比较，A大就让A和C比较，反之B和C比较
//max3的原理：先让A和B比较，<表达式1>为真（A大）就让A和C比较，反之B和C比较
    max1 = (a > b ? a : b) > c ? (a > b ? a : b) : c ;
    max2 = a > b ? (a > c ? a : c) :(b > c ? b : c);
    max3 = (a > b ? a : b) ? (a > c ? a : c) : (b > c ? b : c);
    
    printf("max1:%d\n",max1);
    printf("max2:%d\n",max2);
    printf("max3:%d\n",max3);
    
    }

好，让我们继续回到这一题，除了上述的方法还有没有其他的方法呢，其实有一种更高效的方法：辗转相除法。

原理：输入m，n两个数字，当m%n时，余下的数字如果不是0，则将n的值赋值给m，余数赋值给n，这样一直辗转相除最后余0的时候，n变量存储的值就是他的最大公约数。

1
2
3
4
5
6
7
// 例：输入18,24

18%24=0……18

24%18=1……6

18%6=3……0

故而，最大公约数即6。代码如下：

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

int main()
{
	int m = 0;
	int n = 0;
	int tmp = 0;
	scanf("%d%d", &m, &n);
	while (m % n)
	{
		tmp = m % n;
		m = n;
		n = tmp;
	}
	printf("最大公约数：%d\n", n);
	return 0;
}

打印闰年

打印1000年到2000年之间的闰年

闰年数（英文名称：leap year ），定义：阳历或阴历中有闰日的年，或阴阳历中有闰月的年。闰年一般是每四年一次，也可以说一般每四年中有一年是闰年。

那么如何判断他是不是闰年呢？有以下判定方法：

判定公历闰年应遵循的一般规律为:四年一闰，百年不闰，四百年再闰.

即：

  1. 能不能被4整除，但不能被100整除，即闰年
  2. 能被400整除的也是闰年

很快就能写出以下代码逻辑：

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

int main()
{
	int year = 0; // 用于存放年份
	for (year = 1000; year <= 2000; year++)
	{
		if (year % 4 == 0) // 能被4整除，即余数为0
		{
			if (year % 100 != 0) // 不能被100整除，即余数不为0
			{
				printf("%d ", year);
			}
		}
		if (year % 400 == 0) // 能被400整除的也是闰年
		{
			printf("%d ", year);
		}
	}
	return 0;
}

此时此刻，可不可以将多个if合并成一个if，从而降低空间复杂度呢？

由此，上面的代码可以简化如下：

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

int main()
{
	int year = 0; // 用于存放年份
	for (year = 1000; year <= 2000; year++)
	{
		if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
		{
			printf("%d ", year);
		}
	}
	return 0;
}

将三个判断条件合并，其中第一个条件“能被4整除，但不能被100整除”使用“&&”运算符，再用“||”或第二个条件“能被400整除”，由此优化代码。可以在循环前定义一个变量count用于计数，测试两种方法打印的数量是否一致，都为243.

打印素数

写一个代码，打印100-200之间的素数

什么是素数？

质数是指在大于1的自然数中，即除了1和它本身以外不再有其他因数的自然数。

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

那么怎么判断他是不是素数呢？

对正整数n，如果用2到n-1之间的所有整数去除，均无法整除，则n为质数。

那么很快我们就可以通过逻辑写出代码：

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

int main()
{
	int num = 0;
	for (num = 100; num <= 200; num++) // 定义100-200之间的数字
	{
		int j = 0; // 用于嵌套循环，存放2到n-1之间的所有整数
		for (j = 2; j < num; j++)
		{
			if (num % j == 0)
			{
				break;
			}
		}
		if (j == num)
		{
			printf("%d ", num);
		}
	}
}

代码逻辑非常简单，首先第一个for循环，进行循环测试100-200之间的数字，第二个for循环用于判断，这个数字能否被2~他本身-1的数字整除，如果可以则直接跳出循环，进行下一次循环。

如果一直不能被2和他本身-1的数值整除，那么此时此刻的 j 就是等于num，加一个判断，如果 j == num ，则该数字就是素数，打印该数字。

image-20240126110639124

当然，如果没有2~n-1的数字整除，那么循环都会执行n-1-2次，那么我们有没有可以继续优化一下，降低时间复杂度呢？通过百度对于素数编程判断的基本思路可以发现，他用的是2到√n之间的所有整数。

基本判断思路

在一般领域，对正整数n，如果用2到√n之间的所有整数去除，均无法整除，则n为质数。

那么，为什么可以呢？通过研究我们可以发现规律，当一个数可以分解为a*b的时候，他分解出的a和b一定有一个数是小于或等于他开跟号，如：

16 = 2 * 8、4 * 4，可以发现，√16 = 4，那么2和4都小于或等于4，由此可以推断出，我们只需要√n之前的数进行判断他是否能被整除即可判断是否是素数，降低时间复杂度。

代码优化如下：

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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int main()
{
	int num = 0;
	for (num = 100; num <= 200; num++) // 定义100-200之间的数字
	{
		int j = 0; // 用于嵌套循环，存放2到n-1之间的所有整数
		int flag = 0;
		for (j = 2; j <= sqrt(num); j++)
		{
			if (num % j == 0)
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			printf("%d ", num);
		}
	}
}

还能不能再优化呢？可以，我们可以发现，偶数一定不是素数，那么在循环中就可以从101开始，每次+=2，这样又降低了时间复杂度，所以说一千个人就有一千个代码，一道题有很多种解法，成功优化算法的感觉真是令人感到酣畅淋漓。