第七章 函数

7.1 最大公约数和最小公倍数

题目概述：

写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果。两个整数由键盘输入。

题目思路：

最大公约数：辗转相除法

• 欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

  扩展欧几里得算法可用于RSA加密等领域。

  假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

  1997 ÷ 615 = 3 (余 152)

  615 ÷ 152 = 4(余7)

  152 ÷ 7 = 21(余5)

  7 ÷ 5 = 1 (余2)

  5 ÷ 2 = 2 (余1)

  2 ÷ 1 = 2 (余0)

  至此，最大公约数为1

  以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

• 用C语言来表示就是
  

  • 用x表示被除数、y表示除数、z表示余数
    • z = x % y
  • 除数y变成被除数x，余数z变成除数y
    • x = y
    • y = z

• 最小公倍数

  • 两数相乘除以最大公约数

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int gcd(int x, int y)
{int z = -1;while (z != 0){z = x % y;x = y;y = z;}return x;
}int lcm(int x, int y)
{int z = x * y / gcd(x, y);
}int main()
{int a = 0;int b = 0;scanf("%d %d", &a, &b);printf("最大公约数：%d\n", gcd(a, b));printf("最小公倍数：%d\n", lcm(a, b));return 0;
}

运行结果如下：

7.2 函数判断素数

题目概述：

写一个判断素数的函数,在主函数输入一个整数,输出是否素数的信息

题目思路：

• 判断一个数是否是素数，首先要知道素数是什么
  • 素数：大于1的整数中，只能被1或者被自己整除的数
• 既然知道了怎么样的数是素数，我们就可以开始处理了
  • 用i是否为素数
    • 我们可以假设每个数都是素数，用flag来表示，1就是素数，0不是素数，最后返回flag
    • 如果有一个数不能被2到n-1之间的数字整除，那么这个数就是素数

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int Is_prime(int n)
{int i = 0;int flag = 1;for (i = 2; i < n; i++){if (n % i == 0){flag = 0;break;}}return flag;
}
int main()
{int n = 0;scanf("%d", &n);int ret = Is_prime(n);if (ret == 1){printf("是素数\n");}else{printf("不是素数\n");}return 0;
}

代码优化：

优化1：由于偶数都不是素数，我们可以只从奇数项开始，每个数加+2让下一个也是奇数
优化2：当一个数不是素数的时候，一定能下成下列的一个式子，且他是可以被一个因子整除的
例：m = a *b
16 = 4 * 4
16 = 2 * 8
a和b中一个数字是 <= sqrt(m) →[4]

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
int Is_prime(int n)
{int i = 0;int flag = 1;for (i = 3; i <= sqrt(n); i+=2){if (n % i == 0){flag = 0;break;}}return flag;
}
int main()
{int n = 0;scanf("%d", &n);int ret = Is_prime(n);if (ret == 1){printf("是素数\n");}else{printf("不是素数\n");}return 0;
}

运行结果如下：

7.3 行列互换

题目概述：

写一个函数，使给定的一个 3X3 的二维整型数组转置,即行列互换。

题目思路：

• 画一个对角线
  

对角线的值不变，然后让对角线外的对称值进行互换，既然是互换，那么就会要有一个中间变量temp进行互换

对应的下标如下：

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Swap(int arr[3][3])
{int i = 0;int j = 0;int temp = 0;for (i = 0; i < 3; i++){for (j = 0; j < i; j++){temp = arr[i][j];arr[i][j] = arr[j][i];arr[j][i] = temp;}}
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int i = 0;int j = 0;Swap(arr);for (i = 0; i < 3; i++){for (j = 0; j < 3; j++){printf("%d ", arr[i][j]);}printf("\n");}return 0;
}

运行结果如下：

7.4 反序存放字符串

题目概述：

写一个函数,使输入的一个字符串按反序存放,如输入"CANADA",输出"ADANAC"。在主函数中输入和输出字符串。

题目思路：

• 本题只需要知道数组的最后一个元素即可
  • 用最后的元素和最初的元素交换，如何访问到数组最后一个元素？可以用strlen函数
• 然后就好做了，但是char[sz]就是数组的最后一个元素吗？数组下标是从0开始的，所以ch[sz-1]才是真正的数组最后一个元素
• 由于循环完了一次i++，那么ch[1]就要跟ch[sz-1]的前一个元素交换顺序，但是我们应该如何交换呢？我们可以直接ch[sz-1-i]，那么当i=0的时候，ch[0]就跟ch[5-1-0]交换，也就是ch[0] 和 ch[4]，当i=1的时候，ch[1]和ch[5-1-1]交换，也就是ch[1]和ch[3]…以此类推
• 最后，由于是两两交换，所以我们不需要遍历整个数组，只要遍历半个就能完成交换，否则遍历完整个数组会把逆序的又逆回来，得到的还是CANADA

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
void reverse(char ch[100], int sz)
{int i = 0;int temp = 0;for (i = 0; i < sz /2; i++){temp = ch[i];ch[i] = ch[sz - 1 - i];ch[sz - 1 - i] = temp;}
}
int main()
{char ch[100] = { '0' };gets(ch);int sz = strlen(ch);reverse(ch, sz);printf("%s", ch);return 0;
}

运行结果如下：

7.5 函数连接字符串

题目概述：

写一个函数,将两个字符串连接,如字符串 1 是"BEI"，字符串 2 是"JING”,连接起来是"BEIJING"

题目思路：

• 我们要先找到s1字符串的末尾，用strlen计算字符串的长度，用sz保存，那么ch[sz]就是s1的’\0’位处
• 然后就可以把s2的字符串拷贝到s1处了，也就是一个一个字符的拷贝过去，知道遇到’\0’；
• 但是需要注意，s1拷贝完了之后后面是缺了一个’\0’的，所以我们要认为的加上去

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
void my_link(char s1[100], char s2[100], int sz)
{int i = sz;int j = 0;while (s2[j] != '\0'){s1[i] = s2[j];i++;j++;}s1[i] = '\0';
}
int main()
{char s1[100] = { '0' };char s2[100] = { '0' };gets(s1);gets(s2);int sz = strlen(s1);my_link(s1, s2, sz);printf("%s", s1);return 0;
}

运行结果如下：