3.11笔记3

时间：2024-03-15 11:06:52

3.11知识点3

  • 1. break 语句和 continue 语句有什么区别？
  • 2. 使用 goto 计算 1-2+3-4+......+99-100 的值。
  • 3. 输入一个整数，判断这个数是不是素数。
  • 4. 写程序生成前 100 个素数。
  • 5
  • 6. (a) 对于一个大小为N的数组，它的下标范围是多少？
  • 7. 如何计算`arr[i]`的地址？
  • 8. 为什么程序员会有这样一个刻板印象：数组的效率比链表高?
  • 9. 写一个能计算数组大小的宏函数。
  • 10. 写一个随机发牌的小程序：用户指定发几张牌，程序打印手牌。
  • 11. 为什么传递数组时，除了要传入数组名，还要传入长度？
  • 12. 二维数组`arr[M][N]`的本质是一个一维数组，这个一维数组有多少个元素，每个元素的类型是什么？`arr[i][j]`的地址是多少？为什么二维数组传递的时候，不能省略第二个维度？
  • 13. 什么是局部变量，什么是外部变量，它们的作用域分别是什么？
  • 14. 存储期限有哪些？局部变量默认的存储期限是什么？怎么改变局部变量的存储期限？
  • 15. 德州扑克：写一个程序循环读取 5 张手牌 (输入 0 结束程序)，然后把手中的牌分为下面某一类：1.同花顺 2.四张 3.葫芦 (3 + 2) 4. 同花 5. 顺子 6.三张 7.两对 8. 一对 9.高牌。程序对话如下：
  • 16. 约瑟夫环：n 个人站成一圈，每个 m 个人处决一个人。假设这 n 个人的编号为 1, 2, ..., n，并且从 1 开始数，问最终活下来的人编号是多少？
  • 17. 约瑟夫排列：我们可以在此基础上定义约瑟夫排列，编号为 1, 2, ..., n 的 n 个人围成一个圈，每 m 个人移出一个人，直到移出所有的人。移出的顺序我们称为 (n, m)-约瑟夫排列。比如 (7, 3)-约瑟夫排列为 。请写一个程序，打印 (n, m)-约瑟夫排列。
  • 18. 什么是指针，什么是指针变量？
  • 19. 什么是野指针，对野指针进行解引用运算会发生什么现象？
  • 20. 指针可以进行哪些算术运算？
  • 21. 矩阵乘法。写一个函数实现两个矩阵相乘。
  • 22. 请总结一下指针和数组之间的关系。
  • 23. 删除有序数组中的连续重复元素 (保留一个)。
  • 24. 回型填充数组: 输入一个整数 n (n
  • 25. (a) 字符串变量的初始化和字符指针的初始化有何不同？请举例说明。
  • 26. 利用 getchar() 实现类似 gets_s 的功能。
  • 27. 将包含字符数字的字符串分开，使得分开后的字符串前一部分是数字，后一部分是字母。
  • 28 .将字符串中的空格替换成`"%020"` 。
  • 29. 删除字符串中指定的字符。

1. break 语句和 continue 语句有什么区别？

break语句和continue语句都是控制流语句，用于改变循环的执行顺序，但它们有不同的作用：

  1. break语句用于立即退出循环，无论循环条件是否满足。当程序执行到break语句时，循环会立即终止，并且程序将继续执行循环后面的代码。break语句通常用于在达到某个条件时提前结束循环。

  2. continue语句用于跳过当前循环中剩余的代码，立即进入下一次循环的迭代。当程序执行到continue语句时，会立即停止本次循环的执行，并开始下一次循环。continue语句通常用于在某些特定条件下跳过本次循环的执行。

2. 使用 goto 计算 1-2+3-4+…+99-100 的值。

int main(void) {
	int sum = 0, i = 1;
loop:
	if (i & 0x1) {
		sum += i;
	} else {
		sum -= i;
	}
	i++;
	if (i <= 100) {
		goto loop;
	}
	printf("sum = %d\n", sum);

	return 0;
}

3. 输入一个整数，判断这个数是不是素数。

bool is_prime(int n) {
	for (int i = 2; i * i < n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

4. 写程序生成前 100 个素数。

#include <stdio.h>
#include <stdbool.h>

int main(void) {
	int prime[100] = { 2 };
	int n = 1, candidate = 3;
	while (n < 100) {
		bool isPrime = true;
		for (int i = 0; i < n; i++) {
			if (candidate % prime[i] == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime) {
			prime[n++] = candidate;
		}
		candidate++;
	}

	for (int i = 0; i < 100; i++) {
		printf("%d ", prime[i]);
	}
	printf("\n");

	return 0;
}

5

在密码学领域，对大整数进行素数测试是一个常见的问题。Fermat’s Test（费马测试）是一种基于费马小定理的素数测试算法，它可以用来快速判断一个数是否可能为素数。费马小定理表述如下：

如果 p p p 是一个素数，且 a a a 是不可被 p p p 整除的任意整数，则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod{p} ap−1≡1(modp)。

Fermat’s Test 利用了这一定理：对于一个给定的数 n n n，选择一个随机整数 a a a，然后检查是否满足 a n − 1 ≡ 1 ( m o d n ) a^{n-1} \equiv 1 \pmod{n} an−1≡1(modn)。如果不满足，则 n n n 肯定不是素数；如果满足，则有可能是素数。通过多次选择不同的 a a a 进行测试，可以提高判断的准确性。

需要注意的是，虽然 Fermat’s Test 能够快速判断一个数是否可能为素数，但并不是绝对准确的。存在一些伪素数（pseudoprime），它们能够通过 Fermat’s Test 的检验，但实际上并不是素数。因此，在实际应用中，为了提高安全性，通常会结合其他素数测试方法来进行判断。

6. (a) 对于一个大小为N的数组，它的下标范围是多少？

对于一个大小为N的数组，它的下标范围是从0到N-1。数组的下标从0开始，到N-1结束，共计N个元素。

7. 如何计算arr[i]的地址？

要计算arr[i]的地址，可以使用以下公式：

address_of_arr_i = address_of_arr + i * size_of_each_element

其中，address_of_arr是数组arr的起始地址，i是要访问的元素的下标，size_of_each_element是数组中每个元素的大小（以字节为单位）。

例如，如果要计算arr[3]的地址，假设arr的起始地址是0x1000，每个元素占4个字节（int类型），则计算公式为：

address_of_arr_3 = 0x1000 + 3 * 4 = 0x100C

因此，arr[3]的地址是0x100C。

8. 为什么程序员会有这样一个刻板印象：数组的效率比链表高?

程序员通常有这样一个刻板印象是因为数组和链表在访问和操作上有不同的性能特点，使得它们在不同的场景下具有不同的效率。

  1. 内存访问方式：数组在内存中是连续存储的，而链表的节点可以是分散存储的。在访问数组元素时，可以通过索引直接计算出元素的地址并进行访问，而在链表中，需要从头节点开始逐个遍历找到目标节点，因此数组的访问效率更高。

  2. 缓存友好性：现代计算机系统中，缓存起着非常重要的作用。由于数组元素在内存中是连续存储的，所以在访问数组时，可以更好地利用缓存预取机制，提高访问效率。而链表节点分散存储，可能会导致缓存未命中，降低访问效率。

  3. 插入和删除操作：在插入和删除操作上，链表比数组更高效。因为数组在插入和删除时需要移动大量元素，而链表只需要修改指针即可完成操作。

  4. 空间利用率：对于数组来说，需要预先分配一定大小的内存空间，而且大小固定。而链表可以动态分配内存，根据需要动态增长，因此在空间利用率上，链表更灵活。

综上所述，虽然数组和链表各有优势，但在大多数情况下，程序员更倾向于使用数组来实现一些数据结构，因为数组在访问上更高效，尤其是对于需要频繁访问元素的情况。

9. 写一个能计算数组大小的宏函数。

你可以使用以下宏函数来计算数组的大小：

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))

这个宏函数使用了 sizeof 运算符来计算整个数组的大小，然后除以单个元素的大小，从而得到数组的元素个数。注意，这个宏函数只能用于在同一作用域内定义的数组，因为它依赖于编译器对数组的大小计算。

10. 写一个随机发牌的小程序：用户指定发几张牌，程序打印手牌。

输入:
Enter number of cards in hand: 5
输出:
Your hand: 7c 2s 5d as 2h

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define NUM_SUITS 4
#define NUM_RANKS 13

int main(void) {
	bool inHand[NUM_SUITS][NUM_RANKS] = { false };
	const char suits[NUM_SUITS] = { 's', 'h', 'c', 'd' };
	const char ranks[NUM_RANKS] = { '2', '3', '4', '5', '6', '7', '8', '9', 't', 'j', 'q', 'k', 'a' };

	int n;
	printf("Enter number of cards in hand: ");
	scanf("%d", &n);

	srand((unsigned)time(NULL));
	while (n > 0) {
		int suit = rand() % NUM_SUITS;
		int rank = rand() % NUM_RANKS;
		if (!inHand[suit][rank]) {
			inHand[suit][rank] = true;
			n--;
			printf("%c%c ", ranks[rank], suits[suit]);
		}
	}
	printf("\n");

	return 0;
}

11. 为什么传递数组时，除了要传入数组名，还要传入长度？

在C语言中，数组作为函数参数传递时，只传递数组名是不够的，因为数组名本身并不包含数组的长度信息。数组在内存中是一段连续的存储空间，而数组名只是数组首元素的地址，无法确定数组的长度。

因此，为了在函数内部正确地处理数组，需要额外传递数组的长度信息。这样函数才能知道数组的实际长度，避免越界访问等问题。通常情况下，可以将数组长度作为函数参数传递，或者使用特殊的约定，比如约定数组的最后一个元素为特定的值（如NULL），以表示数组的结束。

12. 二维数组arr[M][N]的本质是一个一维数组，这个一维数组有多少个元素，每个元素的类型是什么？arr[i][j]的地址是多少？为什么二维数组传递的时候，不能省略第二个维度？

二维数组arr[M][N]本质上是一个包含了M个元素的一维数组，每个元素是一个包含了N个元素的子数组。因此，二维数组arr[M][N]一共有M * N个元素，每个元素的类型是数组arr的第二维的类型，即arr的第二维是一个包含了N个元素的数组，因此每个元素的类型是包含了N个元素的数组类型，可以表示为arr[N]。

对于arr[i][j]的地址，可以使用以下公式计算：

address_of_arr_ij = address_of_arr + i * N * size_of_each_element + j * size_of_each_element

其中，address_of_arr是数组arr的起始地址，size_of_each_element是每个元素的大小（以字节为单位），i和j分别是元素在第一维和第二维的下标。

关于为什么二维数组传递的时候不能省略第二个维度，原因是C语言中数组作为函数参数传递时，数组的第一维度可以省略，但第二维度必须指定。这是因为在函数参数中，数组名会被转换为指向数组首元素的指针，因此数组名本身并不包含数组的大小信息。为了在函数内部正确处理二维数组，需要知道第二维度的大小。

13. 什么是局部变量，什么是外部变量，它们的作用域分别是什么？

局部变量（local variable）是在函数或代码块内部定义的变量，它的作用域仅限于定义它的函数或代码块内部。局部变量在函数或代码块执行结束后会被销毁，不能在函数或代码块外部访问。

外部变量（external variable）是在函数或代码块外部定义的变量，它的作用域从定义处开始，直到文件结束或被另一个作用域覆盖为止。外部变量可以在文件中的任何地方被访问，但是如果在函数内部使用外部变量，则需要使用extern关键字进行声明。

总结一下：

  • 局部变量的作用域仅限于定义它的函数或代码块内部。
  • 外部变量的作用域从定义处开始，直到文件结束或被另一个作用域覆盖为止。
  • 外部变量可以在文件中的任何地方被访问，而局部变量只能在定义它的函数或代码块内部被访问。

14. 存储期限有哪些？局部变量默认的存储期限是什么？怎么改变局部变量的存储期限？

存储期限（storage duration）指的是变量在程序运行过程中所占用内存的持续时间，主要有以下几种：

  1. 静态存储期限（static storage duration）：变量在程序运行期间始终存在，直到程序结束才会被销毁。静态变量（包括全局变量和静态局部变量）具有静态存储期限。

  2. 自动存储期限（automatic storage duration）：变量在进入声明它的代码块时被创建，在离开代码块时被销毁。局部变量具有自动存储期限。

  3. 动态存储期限（dynamic storage duration）：变量在程序运行时显式地分配内存，并在不再需要时显式地释放内存。动态存储期限的变量通过调用malloc、calloc或new等函数来分配内存。

局部变量默认具有自动存储期限。如果要改变局部变量的存储期限，可以将其声明为static或extern：

  • 将局部变量声明为static，使其具有静态存储期限。静态局部变量在第一次进入声明它的代码块时初始化，且只初始化一次，在函数调用结束后不会被销毁，而是保留其值直到程序结束。
  • 将局部变量声明为extern，使其具有外部链接性，这样它的存储期限和作用域都会扩展到整个文件。

15. 德州扑克：写一个程序循环读取 5 张手牌 (输入 0 结束程序)，然后把手中的牌分为下面某一类：1.同花顺 2.四张 3.葫芦 (3 + 2) 4. 同花 5. 顺子 6.三张 7.两对 8. 一对 9.高牌。程序对话如下：

Enter a card: 2s
Enter a card: 5s
Enter a card: 4s
Enter a card: 3s
Enter a card: 6s
Straight flush

Enter a card: 8c
Enter a card: as
Enter a card: 8c
Duplicate card; ignored.
Enter a card: 7c
Enter a card: ad
Enter a card: 3h
Pair

Enter a card: 6s
Enter a card: d2
Bad card; ignored.
Enter a card: 2d
Enter a card: 9c
Enter a card: 4h
Enter a card: ts
High card

Enter a card: 0

#include <stdbool.h> 
#include <stdio.h>
#include <stdlib.h>

#define NUM_RANKS 13
#define NUM_SUITS 4
#define NUM_CARDS 5

int num_in_rank[NUM_RANKS];
int num_in_suit[NUM_SUITS];
bool straight, flush, four, three;
int pairs; /* can be 0, 1, or 2 */

void read_cards(void);
void analyze_hand(void);
void print_result(void);

int main(void)
{
	for (;;) {
		read_cards();
		analyze_hand();
		print_result();
	}
}

void read_cards(void)
{
	bool card_exists[NUM_RANKS][NUM_SUITS];
	char ch, rank_ch, suit_ch;
	int rank, suit;
	bool bad_card;
	int cards_read = 0;

	for (rank = 0; rank < NUM_RANKS; rank++) {
		num_in_rank[rank] = 0;
		for (suit = 0; suit < NUM_SUITS; suit++)
			card_exists[rank][suit] = false;
	}

	for (suit = 0; suit < NUM_SUITS; suit++)
		num_in_suit[suit] = 0;

	while (cards_read < NUM_CARDS) {
		bad_card = false;
		printf("Enter a card: ");
		rank_ch = getchar();
		switch (rank_ch) {
			case '0': exit(EXIT_SUCCESS);
			case '2': rank = 0; break;
			case '3': rank = 1; break;
			case '4': rank = 2; break;
			case '5': rank = 3; break;
			case '6': rank = 4; break;
			case '7': rank = 5; break;
			case '8': rank = 6; break;
			case '9': rank = 7; break;
			case 't': case 'T': rank = 8; break;
			case 'j': case 'J': rank = 9; break;
			case 'q': case 'Q': rank = 10; break;
			case 'k': case 'K': rank = 11; break;
			case 'a': case 'A': rank = 12; break;
			default: bad_card = true;
		}

		suit_ch = getchar();
		switch (suit_ch) {
			case 'c': case 'C': suit = 0; break;
			case 'd': case 'D': suit = 1; break;
			case 'h': case 'H': suit = 2; break;
			case 's': case 'S': suit = 3; break;
			default: bad_card = true;
		}

		// read remaining characters of this line
		while ((ch = getchar()) != '\n')
			if (ch != ' ') bad_card = true;

		if (bad_card)
			printf("Bad card; ignored.\n");
		else if (card_exists[rank][suit])
			printf("Duplicate card; ignored.\n");
		else {
			num_in_rank[rank]++;
			num_in_suit[suit]++;
			card_exists[rank][suit] = true;
			cards_read++;
		}
	}
}

void analyze_hand(void)
{
	int num_consec = 0;
	int rank, suit;
	straight = false;
	flush = false;
	four = false;
	three = false;
	pairs = 0;
	/* check for flush */
	for (suit = 0; suit < NUM_SUITS; suit++)
		if (num_in_suit[suit] == NUM_CARDS)
			flush = true;
	/* check for straight */
	rank = 0;
	while (num_in_rank[rank] == 0) rank++;
	for (; rank < NUM_RANKS && num_in_rank[rank] > 0; rank++)
		num_consec++;
	if (num_consec == NUM_CARDS) {
		straight = true;
		return;
	}
	/* check for 4-of-a-kind, 3-of-a-kind, and pairs */
	for (rank = 0; rank < NUM_RANKS; rank++) {
		if (num_in_rank[rank] == 4) four = true;
		if (num_in_rank[rank] == 3) three = true;
		if (num_in_rank[rank] == 2) pairs++;
	}
}

void print_result(void)
{
	if (straight && flush) printf("Straight flush");
	else if (four) printf("Four of a kind");
	else if (three && pairs == 1) printf("Full house");
	else if (flush) printf("Flush");
	else if (straight) printf("Straight");
	else if (three) printf("Three of a kind");
	else if (pairs == 2) printf("Two pairs");
	else if (pairs == 1) printf("Pair");
	else printf("High card");
	printf("\n\n");
}

16. 约瑟夫环：n 个人站成一圈，每个 m 个人处决一个人。假设这 n 个人的编号为 1, 2, …, n，并且从 1 开始数，问最终活下来的人编号是多少？

约瑟夫环（Josephus problem）是一个经典的数学问题，描述如下：n个人围成一圈，从第一个

相关文章