学习

中国矿业大学-数据结构实验(第一次)

Lab1

Q-A

关键在于代码实现欧拉函数
在数论，对正整数n，欧拉函数φ(N)是小于n的正整数中与n互质的数的数目。如：φ(1)=1 此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。
例如φ(8)=4，因为1,3,5,7均和8互质。
设 ：N = P1 ^ q1 * P2 ^ q2 *… * Pn ^ qn.
则：φ(N) = N * (1-1/P1) * (1-1/P2) *… * (1-1/Pn)
只和底数有关，和指数无关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int euler(int n)
{
    int res = n; // res代表最终结果(result)
    for (int i = 2; i * i <= n; ++i) // 从2开始遍历所有可能的质因数
    {
        if (n % i == 0) // 若i是n的因数
        {
            // 欧拉函数的计算公式：φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)
            // 上式通分，等价于 res = res / i * (i - 1)
            res = res / i * (i - 1);
            // 因为与指数无关，所以通过循环除掉所有的i因子
            while (n % i == 0)
                n /= i;
        }
    }
     // 如果最后剩下的n大于1，说明n本身是一个质数，即上面的for循环不起作用
     // 应用欧拉函数的公式处理最后一个质因数
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}

Q-B

直接用Q-A的欧拉函数即可

Q-C

约瑟夫问题:
n个人围成一圈，按1到n的顺序编号。从第一个人开始报数（从1到m报数），凡报到m的人退出圈子，问最后留下的是原来的第几号。

递推法

1
2
3
4
5
6
7
8
9
int josephus(int n, int m) {
    int res = 0; // 0是n=1的情况，因为只有一个人的时候那个人必然是幸存者
    for (int i = 2; i <= n; i++) {
         // 约瑟夫问题的递推关系式：
         // J(n,m) = (J(n-1,m) + m) % n
        res = (res + m) % i;
    }
    return res + 1;//加一是因为从1开始记录
}

关键步骤：J(n,m) = (J(n-1,m) + m) % n
这里假设第一个人从0开始计数，那么第一轮淘汰的是m-1号，即(m-1) mod n
剩余(n-1)个人重新编号，被淘汰者的下一位（即 m % n 号）成为新编号 0，被淘汰者的下一位（即 m % n 号）成为新编号 0。
在 n-1 个人的新问题中，幸存者的编号是J(n-1,m).
那我们将它映射回n个人的原始编号：
新编号 0 对应原始编号 m % n。
新编号 1 对应原始编号 (m+1) % n。
…
新编号 k 对应原始编号 (m + k) % n。
因此，幸存者在 n 个人时的原始编号为：J(n,m) = (J(n-1,m) + m) % n (这里的J(n-1,m)即上一行中的k)。
在程序中就表示为res = (res + m) % i;

模拟法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <vector>
using namespace std;

int josephus(int n, int k) {
    vector<int> people(n);
    for (int i = 0; i < n; i++) people[i] = i; // 编号 0 到 n-1

    int pos = 0; // 当前位置
    while (people.size() > 1) { //当人数大于1，就进行循环
        pos = (pos + k - 1) % people.size(); // 计算淘汰位置
        people.erase(people.begin() + pos);   // 淘汰该人
    }
    return people[0]+1; // 返回幸存者编号（加一是由于从1开始计数）
}

关键步骤：pos = (pos + k - 1) % people.size();，作用是计算下一个要淘汰的人的位置。
假设从pos开始数k个人，第一个是people[pos],那么可知第k个是people[pos+k-1]。
那么当我们淘汰该人之后，下一个人又要从1开始计数，即 % people.size()，让计算回到环的开头。
people.erase(people.begin() + pos);:erase() 会删除 people[pos]，后面的元素自动前移。
直到最后就只剩下一个，也就是pos[0]。
例如：
当前 people = [0,1,2,3,4]，pos = 2（淘汰 2）。
删除后 people = [0,1,3,4]，pos 仍然指向 2（现在是 3 的位置）。

Q-D

将十进制整数转化成R进制

基本思路：设十进制数为n，则将n不断除R取余，将得到的余数再倒序即为十进制数n的R进制形式。
例如将十进制数30转化为二进制形式：

1
2
3
4
5
6
以下的除表示数学意义上保留余数的除法
30 / 2 = 15 ... 0
15 / 2 = 7  ... 1
7 / 2 = 3   ... 1
3 / 2 = 1   ... 1
1 / 2 = 0   ... 1

那么我们将余数倒序得到11110即为30的二进制形式。
恰好栈的出入方式是先进后出，那我们就可以将余数按顺序储存到栈中，再按顺序输出，就能得到想要的结果。

代码实现：

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
string decimalToR(int N, int R)
{
    if (N == 0)
        return "0"; // 特判0，因为若N=0，则函数不会执行

    stack<char> digits; // 用栈存储余数，便于逆序输出
   
    // 不断取余，入栈
    while (N > 0)
    {
        int remainder = N % R;
        digits.push(getChar(remainder));
        N /= R;
    }

    string result;// 初始化result为空字符串
    
    // 出栈得到最终结果
    while (!digits.empty())
    {
        result += digits.top(); // 将栈接到字符串后边
        digits.pop(); // pop使元素出栈，一个个接到字符串后面，就实现了余数的倒序排列
    }

    return result;
}

注意：超出10的数字用A、B、C这类字母表示。
可以用如下函数：

1
2
3
4
5
6
7
8
char getChar(int num)
{
    if (num < 10)
        return num + '0'; // 0~9
    else
        return num - 10 + 'A'; // 10~19 -> A~J
} 
 //返回值是字符(char)类型

Q-E

巧妙利用C语言的输入和输出:
scanf("%d+%d=", &n, &m)即表示输入时需要输入“n+m=”的形式，符合题意。

Q-F

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。

思路：对于波兰表达式，我们可以通过从右到左遍历+栈的方式解决。
具体来说就是，从右到左遍历输入值，遇到数字便入栈，遇到符号，便将栈顶两个元素出栈进行运算，再将运算结果重新入栈，最后剩下唯一的数字就是结果。

代码实现：
先通过getline(cin,line)读入带空格的字符串line
再用istringstream iss(line)储存分割后的每个符号或数字，因为输入的符号或数字是用空格分开的，这句就相当于把一个个不含空格的字符串存在iss里
再将这些元素存入字符数组，以便后续入栈

1
2
while (iss >> token)
        tokens.push_back(token);

之后从右到左遍历这个数组，是数字就入栈，是符号就把栈顶两个元素拿出来进行计算，再将计算结果入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = tokens.size() - 1; i >= 0; --i)
    {
        if (!isOperator(tokens[i]))
        {
            st.push(stod(tokens[i])); // 如果是数字，转为double后入栈
        }
        else
        {
            double a = st.top();
            st.pop(); // 弹出第一个操作数
            double b = st.top();
            st.pop();                           // 弹出第二个操作数
            double res = calc(a, b, tokens[i]); // 计算结果
            st.push(res);                       // 结果重新入栈
        }
    }

注：
stod是字符串转为浮点数(string to double)
isOperator()判断字符串是否为运算符
calc()计算两个数运算结果

Q-G

基本的二路归并
两个数组都是从小到大排序，要做的就是分别从头遍历两个数组，并进行比较，小的插入新数组，再移动到下一个继续比较，直到有一方结束遍历，就将剩下的全部插到新数组末尾。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> q1(n), q2(n);
    for (int i = 0; i < n; i++) cin >> q1[i];
    for (int i = 0; i < n; i++) cin >> q2[i];
    
    vector<int> merged;
    int i = 0, j = 0;
    
    while (i < n && j < n) {
        if (q1[i] < q2[j]) {
            merged.push_back(q1[i++]);
        } else {
            merged.push_back(q2[j++]);
        }
    }
    
    // 处理剩余元素
    while (i < n) merged.push_back(q1[i++]);
    while (j < n) merged.push_back(q2[j++]);