南京大学软件学院2021级课程 C语言程序设计 非官方题解.zip

# 3-for-a-while > Last Update: 2021/11/2 0:10 ## 写在前面 本仓库仅作为参考，请不要照抄代码，也请带着思考来阅读这些代码和readme。适合阅读本题解的人有： 1. 思考很长时间没有思路的同学 2. 解法始终无法拿到满分的同学 3. 想要优化自己代码的同学 ## A Josephus谜题(josephus.c) 本题是十分著名的**约瑟夫问题**。软院的小朋友在大二的数据结构课上可能会再一次的遇到这个问题。该问题的思路是**模拟**：我们使用数组来存放这 $n$ 个人，并通过 $n - 1$ 次循环来剔除掉 $n - 1$ 个人。 ### 思路 1. 初始化数组的索引`index = -1`，这里用 $-1$ 是因为第一个人我们是当做 $1$ 来数的，如果用 $index = 0$ 的话其实第一个人我们是当做 $0$ 来数的（why？ 2. `index = (index + k) % size`，这里的`size`是数组的长度，可以知道每经过一次循环，数组长度都减一 3. 我们找到索引之后就将处于该索引的人删去，通过将数组后面的元素不断前移即可实现“删去”这一操作。 4. 删去之后我们需要将 `index--, size--`. 1. `index--`的用途与前面将`index = -1`的用途是一样的，请自己思考 2. `size--`是因为我们删去了一个人，需要将数组的范围缩小 $1$。 通过以上的**提醒**，可能你会稍微有点思路，但这其实不是最优解，或许你可以考虑一下降低**时间复杂度**和**空间复杂度**的解法是什么？ ### 如何优化 > 提示一：这里的删除操作耗费的时间太久，必须要将该位置以后的数组全部遍历一遍 > > 提示二：这是个数学问题，或许我们可以有公式推导出来？ ## B 二进制转换(binary.c) 这题应该是这次作业中比较简单的一道题了。学过**计算系统基础**的大家都知道，计算机中的所有数据都是由二进制来表示的，整数也是如此，本题所做的就是将一串二进制数表示成整数。 本题思路也是**模拟**：对某个二进制数 $s_ns_{n-1}...s_1$，其十进制数表示为 $s_n \times 2^{n-1} + s_{n-1} \times x^{n-2} + \dots + s_1 \times 2^0$ ，因此我们只需要模拟这个过程即可。 ### 注意！！！ 本题的二进制数长度最多可能达到**30位**，即使我们使用了`long long`也会面临着溢出的风险，因此我们**应该用一个`char`数组来存储二进制数字**，避免溢出，与此同时，答案其实并不需要和我源代码写的一样用`long long`，因为`C`的`int`型是4个字节也就是32位，所以用`int`完全能够放得下30位的一个长度~ ### 思路 1. 通过定义`product`表示 $2$ 的阶乘。 2. **从尾到头**遍历`char`数组，每次循环将`product *= 2`，这么做是为了省去每次都要计算 $2$ 的阶乘（实际上是多余的操作），节省了一重循环，优化了时间复杂度。 > **从尾到头**遍历数组是因为我们读取数字的时候，二进制数的高位实际上是在`char`数组的低位的，所以我们要从`char`数组的最高位开始遍历（实际上是二进制数的最低位 3. 如果`char`数组的第 $i$ 位是 $1$，那么答案就加上 `product`，否则就跳过。 4. 循环结束，输出答案 ### 思考 细心的你可能会发现，本题其实用的是**无符号数**的二进制数表示，即我们转换二进制数实际上只能够得到正数。我们知道，整数在计算机中是以补码的方式存储的，而补码是有符号位的，补码的负数是通过对其相对应的整数“**取反加一**”得到的，这样就可以表示正负数啦~ > 思考一：如果要将二进制**补码**转换成十进制，该怎么实现呢？ > > 思考二：十进制转成补码又该怎么实现呢？ ## C 级数求和(series.c) 这道题也是这次作业中比较简单的一道题了，也是除了**二进制转换**之外目前通过人数最多的一道题（截止至2021/11/2 10:09），这道题我们也采用的是**模拟**的思想，即根据题意来模拟<span style = 'color: red'>**得出级数的过程**</span>。思路如下： ### 思路 1. 与**[二进制转换](#B 二进制转换(binary.c))**相同，我们也用了一个`product`来记录阶乘，当然这里要注意的是在`i == 0`和`i == 1`的情况下，**阶乘都是1** 2. 之后我们就通过**循环累加**，模拟求级数的过程就可以啦~ ### 优化 在**源代码中**有一句`double temp = pow(x, i)`，其实这一句并不是必要的，我们可以通过得出阶乘的方式来获得 $x$ 的 $n$ 次方，感兴趣的同学可以自己去尝试~ ### 思考 我们知道，真正的级数其实是一直累加到 $\infin$ 的，在计算机内部实现的过程中，我们并不能够让其一直**加到无穷**（不然就是**死循环**啦！），那我们应该怎么做到将**无穷级数**真正计算到趋近于它真实的值呢？ > 方法一：将循环次数变的极大，如果一个级数是收敛的那么$\lim_{n \rightarrow \infin} \sum = 0$，此时我们增大循环次数对级数值的影响会逐渐变小，也就是我们已经十分接近级数的值了~ > > 方法二：通过设立**阈值**，即设立最小误差，比如要与真正级数相差 $10^{-9}$ 才能够推出循环，这种方法需要我们已经知道了这个级数计算出来的真正值。 ## D 数独(sudoku.c) 这道题可能是**稍微比较复杂**的一道题了，其复杂在于你明白该怎么去做，但是要实现出来需要经过一番的思考，相信大家的思路都和我一样：分别检查**行**、**列**、**3x3的九宫格**，如果都符合题意就输出`YES`，否则就输出`NO`。但是在具体的检查方面我们又该如何实现呢？我的思路如下： ### 思路 1. 创建了一个一维数组`check`用来检查每个数字出现的次数，其大小为9，每个位置代表每个数字出现的次数。 > 举例：如果数独中的某一行为`1 1 5 4 7 8 9 6 3`，则`check`数组中从0 - 8位置的元素分别是`2 0 1 1 1 1 1 1 1`，即代表1出现了2次，2出现了0次，其余元素出现了1次 2. 使用了一个函数`clearCheck`，用来清空`check`数组中记录的信息。 3. 用到了三个`int`型变量`isCorrectRow, isCorrectColumn, isCorrectBlock`，分别用来记录**行、列、块**是否正确，只有当三个都不为0时才会输出`YES`。 > 这里其实是用`int`型变量来代替`bool`，`C`语言中并没有`bool`变量，编译器认为`0`是`false`，除了`0`之外的都是`true`，其他语言的`bool`变量具体实现也是如此，因此此处用`int`变量来起到一个记录的作用。 4. 检查行、列、块（具体该怎么做呢？请阅读源码 5. 如果有一个不符合的我们可以直接`break`，且不需要做后续的检查 6. 只有当三个都符合的时候输出`YES` ### 思考 本题因为数据量比较小且确定，所以我们如果使用了多重循环或许也没有关系，但是对于数据量较大的时候，我们有方法能够优化这种**遍历检查**的方式吗？ ## E 插入排序(insertion-sort.c) [插入排序](https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F)是一种理解起来**最为简单**的排序，也是我们实际生活中最为常用的一种排序，即对每一个位置上的元素，我们都认为其**之前的元素是排序好的**。 > 比如：现在有`5 4 9 7`四个元素，排序流程如下： > > 1. 遍历这四个元素 > 2. 遇到第一个数字`5`，我们认为其前面的数字已经排序好了，所以将`5`插到这堆已经排序好的数字中的正确位置，因为其前面为空，所以不用动 > 3. 遇到第二个数字`4`，因为其比`5`小，所以`swap(4, 5)` > 4. 遇到第三个数字`9`，此时前两个数字是排序好的，我们要将`9`插入到前面这个已经排序