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++]);
    

数据结构入门

什么是数据结构？（绪论）

定义

数据结构是指所涉及的数据元素的集合以及数据元素之间的关系。
数据结构包含三方面：数据逻辑结构、数据存储结构、数据运算。

数据的逻辑结构

数据结构的对象关系是一对一的、呈线性关系的就称作线性表。
数据结构的 对象关系是非线性的、一对多的关系 称作树。
操作对象之间呈现多对多的关系，称作图。

数据、数据项、数据元素

数据就是输入的东西，比方说各个学生的姓名成绩。
数据项是具有独立含义的数据最小单位。
就比方说一个表，里面有学生姓名学号什么的，然后“姓名”这玩意就叫数据项。
数据元素是组成数据的基本单位，就是比方说姓名+学号+成绩，这样一整个叫数据元素。

逻辑结构

数据元素的逻辑关系称作逻辑结构。
逻辑结构分为四类：集合、线性结构、树结构、图结构。

存储结构

数据元素及其关系在计算机存储器中的存储方式就是存储结构
（就是把逻辑结构映射到内存上）
要求：存储所有元素，存储元素间的关系。
分四种 ：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

模板

C++提供了两种模板机制，即函数模板和类模板。

函数模板

声明函数模板一般格式如下：

1
2
3
4
5

template 类型参数表
返回类型 函数名（形参表）
{
    函数体；
}

例如，以下是一个求绝对值的函数模板，其中T为参数类型：

1
2
3
4
5
6

template <typename T>
T abs(T x)
{
    if(x < 0) return -x;
    return x;
}

类模板

template 类型参数表
class 类模板名
{
类模板实现语句；
···
}；

线性表

概念

线性表是具有相同类型的n个数据元素组成的有限序列（相同类型表明每个数据元素所占的空间相同）
除了第一个元素，其他元素都有直接前驱。
除了最后一个元素，其他元素都有直接后继。

操作

初始化，销毁，插入元素，删除元素，按值查找，按位查找。
什么时候要传入参数的引用？
对参数修改的结果需要带回来。
就比方说我定义了一个函数test(int x)然后我调用了这个函数，实际上我是把main函数中的x复制了一份给test中的x，也就是说main中的x不变。
而我test(int & x)的话，就是直接对于main中的x的值进行修改，因此x的值会改变。
所以呀，我在使用线性表的插入或者删除函数的时候，要调用线性表的引用，因为是对线性表本身进行修改。

顺序表

顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

顺序表的实现——静态分配

通过静态数组来实现

1
2
3
4
5
6

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];//ElemType是指元素类型
    int length;
}Sqlist;//sq指的是sequence（顺序）

Function (函数)

基本结构

1
2
3

ReturnType Name(){
...
}

返回值＋函数名，括号里放参数，花括号里放代码。

每个Java程序都会有个main函数，main函数是程序的入口点。

1
2
3

void main(){
...
}

但是，函数不是独立存在的，它们总是属于一个类。

Class（类）

类是一个或多个函数的容器。
每个Java程序都有一个Main类

1
2
3
4
5

class Main{
	void main(){
	...
	}
}

花括号之间定义的函数属于这个类，更确切地说，这类函数称为Method（方法）。
因此说方法是类的一部分函数。（Method必须定义在类或对象中）
在Java中，每个类和方法都有访问修饰符（比如public或private），大多数时间我们用public，就像这样

1
2
3
4
5

public class Main{
	void main(){
	...
	}
}

这就是Java程序的主要结构

命名

类的命名：每个单词的首字母大写。
方法的命名：第一个单词首字母小写，后面的单词首字母大写。

HelloWorld

我们将用到System类，使用其中的out字段（打印流），使用其中方法的println。
整体就是

1
2
3
4
5

public class Main{
	public static void main(String[] args){
		System.out.println("Hello World");
	}
}

注意：文件名要和类名一致，这时候这个文件就要命名为Main.Java。

编译和运行

可以直接在VsCode里Run
也可以在Linux里面通过Javac Main.java进行编译，再通过Java Main运行。

变量

int age = 30;之类的，和cpp差不多。
赋值什么的用法也差不多。
同样的，变量名也是要第一个字母小写。

Primitive Type(原始类型)

就比如上面的int age = 30;，可以用byte age = 30;来节省内存。
当我有一个大数字时，我可以使用下划线增强数据的可读性，例如int viewsCount = 123_456_789;
当数字很大，超过了int的存储范围的时候，就要用到long，但是不能写long viewsCount = 3_123_456_789,因为Java会把后面的数字默认当成int型，所以要在数字后面加一个L，大小写不影响，但是小写l很像数字1，建议大写。
类似的，Java会把小数默认为double类型，所以在给float变量赋值的时候，我们要在数字后面加一个F，比如float price = 10.99F。
对于Char，使用单引号把字符包裹起来。比如char letter = 'A';。
而对于多个字符，使用双引号。
和cpp一样，关键词不可以用于变量的命名。

Reference Type（引用类型）

在处理引用类型的时候，我们需要使用new来分配内存，这点和原始类型不同。
例如：Date now = new Date();。
但是不用考虑内存释放，编译器会自己处理好。
并且在使用Date这个类型的时候，还要再头部声明import java.util.Date;，有的软件会在你写出Date时自动帮你补好这句，但是在我的Linux里要自己手动补充。😓
并且我们在下一行输入now.的时候，底下会自动跳出这个类的各个成员，像这样
而原始类型是不会有这些的。
这里的完整代码是这样的

1
2
3
4
5
6
7

import java.util.Date;
public class Main{
        public static void main(String[] args){
                Date now = new Date();
                System.out.println(now);
        }
}

就是使用Date来得到现在的时间，就是说，当你创建一个 Date 对象时，它会自动记录当前的日期和时间。
这里的Date是一个类，头部的import java.util.Date;是一个Package（包）。

Primitive VS Reference

在内存管理方面，这两种类型存在非常重要的区别。
比如说，当我们使用原始类型时，像这样

1
2
3
4
5
6
7
8
9

import java.util.Date;
public class Main{
        public static void main(String[] args){
                byte x = 1;
                byte y = x;
                x = 2;
                System.out.println(y);
        }
}

输出结果是 1。
X和Y起初内存是完全独立的，因此改变X也不会改变Y。
但是当我们使用引用类型的时候，就像这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import java.awt.*;

public class Main {

    public static void main(String[] args) {

        Point point1 = new Point(1, 2);

        Point point2 = point1;

        point1.x = 3;

        System.out.println(point2.x);

    }

}

输出结果是 3。
这是因为在引用类型中，首先环境先分配一点内存来存储这个Point对象，然后我们这里假设这个对象的地址是100，然后再分配一个内存位置，在该位置存储Point的地址。这和原始类型很不一样。
（有点像cpp的指针，但是Java不需要手动释放内存）

因此在这里Point1和Point2引用的是内存中的同一个Point对象，也就是说这两个变量彼此并不独立。也就意味着我随便改一个，另外一个也会一起变化。

String(字符串)

不需要import包，java自带了。
String类其实是引用类型，但是为了简便，可以这样初始化。
例子：

1
2
3
4

public class Main{
        public static void main(String[] args){
                String message = "Hello World";
                System.out.println(message);

我们可以用加号+将两个字符串连接起来，就像String message = “Hello，World” + “！！”；，就会输出Hello，World！！。
并且，String是一个类，同样可以用点访问成员。
比如message.endWith(),来判断字符串是否以一个字符或字符序列结尾。

1
2
3
4
5

public class Main{
        public static void main(String[] args){
                String message = "Hello World" + "!!";
                message.endWith("!!");
                System.out.println(message);

输出true。
同理，也有message.startWIth()。
message.length()，来查看字符串中有多少个字符。
message.indexOf(),来查看字符串中某个字符的索引，比如“Hello，World！！”中H的索引值为0。(有点类似数组) 如果查找的字符不在字符串中，会输出-1。
message.replace用于替换，比如message.replace("!","*")就是用星号(*)替换感叹号(!)
这段程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Main {

    public static void main(String[] args) {

        String message = "Hello, World!";

        System.out.println(message.replace("!", "*"));

        System.out.println(message);

  

    }

}

就会输出
Hello,World*
Hello,World!
因为在Java中字符串是不可改变（Immutable）的，一旦一个 String 对象被创建，它的值就不能被修改。任何看似“修改”字符串的操作（如拼接、替换、大小写转换等），实际上都会创建一个新的 String 对象，而原字符串保持不变。
message.toLowerCase将大写转成小写，
message.toUpperCase将小写转大写。
message.trim()，去掉字符串前后多余的空格，如果message = " Hello,World! "，用System.out.println(message.trim());,就会输出Hello,World!。

转义序列

如果我们想让字符串内容为Hello,"World",我们不能直接在双引号内部再放一对双引号，而是使用反斜杠，像这样String message = "Hello,\"World\"";
而当我们想输出反斜杠的时候，我们要在反斜杠前加一个反斜杠，表示转意字符。
比如\\会输出\。
\n用于换行。\t用于制表。

Arrays（数组）

定义一个含有5个元素的数组，int[] numbers = new int[5];
赋值的话和cpp差不多，numbers[0] = 1;，当索引值超过4，Java会报错。
当我们直接System.out.println(numbers)时，会输出一段奇怪的字符串，这是Java基于内存中此对象的地址计算出的字符串。这个字符串对每个数组来说都不同。
想要输出数组中的所有元素，我们可以调用Array类。
首先引用这个类import java.uti.Arrays，接着就可以用Array.toString()得到数组内容了,
最后输出System.out.println(Array.toString(numbers))
运行就可以得到数组内容。
整型数组的话默认为0，布尔型默认为false，字符串型默认为空字符串。
更便利的创建字符串的方式int[] numbers = {2,3,4,5,6};
我们可以通过numbers.length得到字符串长度
例如System.out.println(numbers.length),就会输出5.
我们还可以通过Array.sort(numbers)对数组进行从小到大排序

多维数组

比如说二维数组(两行三列)就是int [][] numbers = new int[2][3];
当我们要输出多维数组的时候，我们就要用到deepToStrign(numbers)
比如这样System.out.println(Arrays.deepToString(numbers));
同样的，花括号也适用。
例如int [][] = {{1,2,3},{4,5,6}}

Constant(常量)

当我们不想改变一个变量的值的时候，在变量种类奇前加上final，就可以保证它是一个常量，例如final float PI = 3.14F,就保证了PI是常量3.14，不会被改变。

Arithmetic Expressions(算数表达式)

加、减、乘、除、取模都是和cpp一样的。
注意：在计算10/3如果想要小数结果，得写成
double num = (double)10 / (double)3;
写成double num = 10 / 3;会输出3.0
（有点烦诶😓）
好吧这样写也可以输出小数double num = 1.0 * 10 / 3;
x++;这种自增和自减也是和cpp一样的。
还有x = x + 2; x += 2;，和cpp都一样。

Order of Operations (执行顺序)

符合基本的数学运算顺序。

Cast(转换)

隐式转换

例如:

1
2
3

short x = 1;
int y = 2 + x;
System.out.println(y);

就会输出3。
有这样的规律byte < short < int < long,存储空间小的可以转化为大的。
只要不丢失数据就可以发生隐式转换。（double转int这种就会丢失。）

显式转换

就比方说丢失数据问所谓了，就可以这样

1
2
3

double x = 1.1;
int y = 2 + (int)x;
System.out.println(y);

就是将x强转成1。
注意：这些都是发生在兼容类型之间的，就是数字只能转数字，不能说字符串转数字。
但是啊但是啊，在java.lang这个包里面，有这些东西可以用来转字符串。
Integer.parseInt()
Short.parseShort()
Float.parseFloat()
诸如此类。
来个例子看看

1
2
3

String x = "1";
int y = 2 + Integer.parseInt(x);
System.out.println(y);

这样输出 3。