Numbers and Numerical Operations【数字与数值运算】

Divisibility【可约分性】

Greatest Common Divisor & Least Common Multiple【最大公约数与最小公倍数】

Modular Arithmetic【模运算】

Euclidean Algorithm【欧里几德算法】



# 数字与数值计算

## Notation for Numbers

- 自然数（Natural Numbers）：
    - $N = \{0,1,2,...\}$
- 整数（Integers）：
    - $Z=\{...,-1,0,1,2,...\}$
- 正整数（Positive Integers）：
    - $N_{>0}=Z_{>0}=\{1,2,...\}$
- 有理数/分数（Rational Numbers / Fractions）：
    - $Q=\{\frac{m}{n}:m,n \in Z,n \ne 0\}$
- 实数（Real Numbers）：
    - $R=a_1 a_2...a_k b_1 b_2 ...$

在$N$和$Z$中，不同的数字代表不同的数值：

$$
1 \ne 2 \ne 3
$$

在$Q$和$R$中，不同的数字可以代表相同的数值：

$$
\frac{1}{2} = \frac{2}{4} = \frac{3}{6}
$$


## 实数与整数之间的转换

使用最大整数(ceiling)与最小整数（floor）概念。

- 最大整数 $⌈x⌉$：$the\ greatest\ integer \le x$
- 最小整数 $⌊x⌋$：$the\ least\ integer \ge x$

$$
⌊\pi⌋ = 3 = ⌈e⌉
$$

以下是一些关于最大整数与最小整数的简单理论：

:::info{title="1"}

因为有 $⌊-x⌋ = -⌈x⌉$，所以有$⌊x⌋ = -⌈-x⌉$。
:::


:::info{title="2"}

对于所有的 $t \in Z$，均有：
- $⌊x + t⌋ = ⌊x⌋ + t$
- $⌈x + t⌉ = ⌈x⌉ + t$

:::

:::info{title="3"}
令 $k,m,n \in Z$，并且 $k>1, m \ge n$，则 $k$ 在区间 $[n,\ m]$ 的整数倍数的数量为：
$$
⌊\frac{m}{k}⌋ - ⌊\frac{n-1}{k}⌋
$$
:::


# 可约分性

## 定义

对于 $m,n \in Z$，如果$n = k * m, k \in Z$，我们可以称$m$可约$n$（$m$ divides $n$），记作：

$$
m|n
$$

同时也可以说：
- $n$对$m$是可约的。（$n$ is divisible by $m$）
- $m$是$n$的约数。（$m$ is a divisor of $n$）
- $n$是$m$的倍数。（$n$ is a multiple of $m$）



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

最大公约数：Greatest common divisor，GCD


:::info{title="Definition of GCD"}
$$
gcd(m,\ n) = largest\ d \in Z_{>0}\ such \ that \\

d|m \ and\ d|n.
$$
:::

最小公倍数：Least common multiple，LCM

:::info{title="Definition of LCM"}
$$
lcm(m,\ n) = smallest\ k \in Z_{>0}\ such \ that \\

m|k \ and\ n|k.
$$
:::

最大公约数和最小公倍数是非负的，不管 $m$ $n$的正负性。

并且有事实：

$$
gcd(m,n)\ * \ lcm(m,n) = |m|\ * \ |n|
$$

由此可得，当 $m, n > 0$ 时，如果有：

$$
lcm(m,n)=m\ * \ n
$$

则有：

$$
gcd(m,n)=1
$$

即：$m,n$ 是互质数。


:::info{title="互质数（Relatively Prime）"}
如果$gcd(m,n)=1$，我们就认为 $m$ 和 $n$ 是互质数，也说他们两个是互质的。
:::

# 模运算

已知：对于任意的整数 $m$，均有：

$$
m = n * q + r，r \in [0, m)
$$

可以用模运算符 $\% $ 或 $mod$ 对 $r$ 进行表示：

$$
r = m \% n \\
r = m\ \ mod\ \   n
$$

此外，模运算还存在同余概念：

$$
m = _{(n)}p \ \ if\ \  n|(m-p)
$$

这表示，$m$ 与 $p$ 在模 $n$ 的意义下同余（即在相同的除数的情况下具有相同的余数）。

需要注意的是，$m = _{(n)}p $ 并不是一个标准的数学符号，更常见的表示方法是：

$$
m = p\ \ (mod \ n)
$$

以下是一些基本事实：


![COMP9020 - Lecture 2: Number Theory pp.55](/static/img/e8dc1ec76cc1f9c96840bc21e62803b7.image.webp)

# 欧里几德算法

最基本的欧里几德算法没有涉及到模运算，它使用了递归的思路，经过大量重复之后回归到模运算的结果。

$gcd(m,n)=$

$$
m,\ \ \ (m=n) \\
gcd(m-n,n),\ \ \ (m > n) \\
gcd(m,n-m),\ \ \ (m < n) 
$$

以下是当 $m>n$ 时，公式的证明方法：

![COMP9020 - Lecture 2: Number Theory pp.44](https://rin977.com/static/img/40ff4c68a4aa12d5de5440dfaf20f6cd.image.webp)

然而，在掌握了模运算后，该公式可以简化为：

$gcd(m,n)=$

$$
m,\ \ \ (m=n\ or\ n=0) \\
n,\ \ \ (m=0) \\
gcd(m\%n,n)\ \ \ (m>n>0) \\
gcd(m,n\%m)\ \ \ (0<m<n)
$$

COMP9020 1.2 离散数学概念

> Annoyingly, sometimes the English in the question is the hardest part, not the maths.



---
# 直接证明（Direct Proof）

分析条件，从条件出发，根据要求推导结论。

| Proposition Form | You Need to Do | Comment |
| --- | --- | --- |
| $ A⇒B $| assume A and prove B | 给出条件A，证明命题B |
| $ A ⇔ B $ | prove "if A then B" and "if B then A" | “当且仅当”，要有双向证明 |
| $ ∀x.A $ | show A holds for every possible value of x | 对任意x，命题A均成立 |
| $ ∃x.A $ | find a value of x that makes A true | 存在x，使得命题A成立 |

# 反证法（Contradiction）

To prove A is true, assume A is false and derive a contradiction.
That is, start from the negation of the proposition and derive false.

通过假设某个命题的否定为真，然后通过逻辑推理导出矛盾（contradiction），从而证明该命题实际上为真的证明方法。


:::tip{title="TIPS"}
Proof by contradiction only apples when your statement is for "IF A THEN B".

你只能在“$ A ⇒ B $”这种命题方式中使用反证法。以下表格中只是对逻辑条件中的取反的一种说明。
:::

以下为命题的否定的表示方法：


| Proposition Form | Negation | Comment |
| --- | --- | --- |
| $ A\ and\ B $ | $ not\ A\ or\ not\ B $ | 任一个条件取反 |
| $ A\ or\ B $ | $ not\ A\ and\ not\ B $ | 所有条件均取反 |
| $ A ⇒ B $ | $ A\ and\ not\ B $ | 条件A推导出非B即取反 |
| $ A ⇔ B $ | $ A\ and\ not\ B,\ or\ B\ and\ not\ A $ | 一个方向不成立即可取反 |
| $ ∀x.A $ | $ ∃x.\ not\ A $ | 假设一个反例 |
| $ ∃x.A $ | $ ∀x.\ not\ A $ | 假设没有能够成立的例子 |

COMP9020 1.1 基本逻辑推导策略

COMP6991 Solving Modern Programming Problems with Rust

记录RUST相关基本语法。



# 变量声明

## 普通变量

```RUST
//不可变变量
let s = 100;

//可变变量（mutable）
let mut s = 100;

//类型变量
let mut s = String::new();
```

## 重影（Shadowing）

重影是指变量的名称可以被重新使用的机制（多次重复使用`let`）：

```RUST
fn main() {
    let x = 5;
    let x = x + 1;
    let x = x * 2;
    println!("The value of x is: {}", x);
}
```

重影与可变变量的赋值不是一个概念，重影是指用同一个名字重新代表另一个变量实体。

*重影变量的类型、可变属性和值都可以变化。*

*可变变量赋值仅能发生值变化。*

在同一范围内多次声明同名变量，后声明的变量会隐藏（遮蔽）前面的同名变量。这意味着在同一作用域内，后声明的变量会覆盖前面的同名变量，而前面的同名变量则不再可见。

需要注意的是，在不同的作用域中，不同的`x`在事实上是同时存在的，而不是后者取代前者的关系。

```RUST
let x = 42;

{
    let x = 123;
    println!("The value is: {x:?}");
}

println!("{x}");
```

输出的结果是：

```
The value is: 123
42
```

## 数组

数组创建时声明类型与长度。也可以不写，编译器会自动处理。

```RUST
fn main() {
    let my_array: [i32; 5] = [
        1,
        2,
        3,
        4,
        5,
    ]
}
```

## VEC

使用`vec!`创建VEC，并且能够使用`push`添加变量。

```RUST
let mut my_vec = vec![1, 2, 3];
my_vec.push(42);
```

## 复合类型tuple

可以直接将一个变量内部声明多个变量。

```RUST
let my_tuple: (bool, i32, char) = (true, 42, 'z');
let my_tuple: (i32) = (7);

let unit_tuple = ();
```

注意：空tuple一般不能作为bool变量的判断。

```RUST
let unit_tuple = ();

//非法，不可编译通过
if unit_tuple {

}

//合法
if unit_tuple == () {

}
```

## 枚举类型enum

首先枚举不同种类的选项，之后可以自由使用。

```RUST
enum CarBrand {
    Toyota,
    Nissan,
    Subaru,
}

fn main() {
    let brand: CarBrand = CarBrand::Toyota;
    
    //注意，以下写法是不合法的
    let brand = CarBrand::Toyota;
}
```

同时，这些类型一样可以声明成不同的变量类型，之后直接赋值（变量类型请见下文）。

```RUST
enum CarBrand {
    Toyota(i32),
    Nissan(String),
    Subaru,
}

fn main() {
    let brand: CarBrand = CarBrand::Toyota(42);
    let brand: CarBrand = CarBrand::Nissan(String::form("HelloWorld"));
}
```

### Option枚举

`Option`是一个枚举类型，用于表示一个值可能存在也可能不存在的情况。这个类型被广泛用于处理可能为空的情况，类似于其他语言中的可选类型或者空安全类型。`Option`枚举有两个可能的值：

- `Some(T)`: 表示值存在，并且包含了类型为 T 的具体值。
- `None`: 表示值不存在，没有具体的值。

这个模式允许程序员在可能返回空值的情况下更好地处理代码，以避免空指针异常或者其他类似的错误。

例如，一个简单的函数可能会返回一个`Option`类型，表明它可能返回一个值，也可能返回空值：

```RUST
fn main() {
    let some_value: Option<i32> = Some(5); // 创建一个包含整数值的 Some
    let no_value: Option<i32> = None;      // 创建一个空的 Option

    match some_value {
        Some(value) => println!("Value is: {}", value), // 如果存在值，则打印值
        None => println!("No value!"),                   // 如果不存在值，则打印"无值"
    }

    match no_value {
        Some(value) => println!("Value is: {}", value), // 如果存在值，则打印值
        None => println!("No value!"),                   // 如果不存在值，则打印"无值"
    }
}
```

在这个简短的示例中，我们定义了两个 `Option<i32>` 类型的变量：`some_value`和`no_value`。

`some_value`包含了一个具体的整数值`5`，而`no_value`则是一个空的`Option`。然后，我们使用`match`来检查这些变量，如果存在值，则打印该值，否则打印 "无值"。

# 变量类型

经典的变量有以下几种：

```
char, short, int, long, long long
i8, i16, i32, i64, i128
u8, u16, u32, u64, u128

float, double
f32, f64
```

由于RUST的运行环境的位数不同，例如在32位和64位的机器上，变量的位数可能会发生变化，因此规定变量的位数是很有必要的。

规定位数的方式：

```RUST
let x: u8 = 42;
```

变量之间也可以进行强制类型转换，但是存在风险（dirty way）。

```RUST
let x: u8 = 42;
let y: i32 = x as i32;
```

推荐的方法是使用`into`来进行风险预警。

```RUST
let x: i32 = 1231231123;
let y: u8 = x.into();
```

如果可能会出现丢失数据的情况发生，它会报错并发出预警。

发出自定义预警的方法：

```RUST
let x: i32 = 1231231123;
let y: u8 = x.into().expect("Number was too big");
```

这样在触发报警的时候会抛出“Number was too big”。


# 大括号的返回值

大括号的返回值只取决于最后一行。

```RUST
let judge = {
    let mut a = 4;
    a = a * a;
    a += 12;
    //最终给judge赋的值
    a/4
};
```

# 循环 (需要补充)

## For循环

标准形式：

```RUST
fn main() { 
let my_array = [10, 20, 30, 40, 50]; 
    for i in 0..5 { 
        println!("my_array[{}] = {}", i, my_array[i]); 
    } 
}
```

但RUST也支持数组元素直接访问。

```RUST
let my_array = [
    1,
    2,
    3,
    4,
    5,
]

for elem in my_array {
    println!("{elem}");
}
```

## While循环

## Loop循环


# 所有权规则

```RUST
let my_string = String::form("HelloWorld");
let output_string = my_string;

//能够正常输出
println!("{output_string}");
//会报错
println!("{my_string}");
```

String 类型是可变的、拥有所有权的类型，而在你的代码中，你把 my_string 绑定到了一个新的 String 实例上，然后尝试再次使用 my_string 来打印其值，**这违反了所有权规则**。

在 Rust 中，所有权规则保证了内存安全和避免了数据竞争。当你把 my_string 赋值给 output_string 后，所有权被转移了，output_string 拥有了 my_string 的所有权，而 my_string 不再有效。因此，尝试打印 my_string 的值会导致编译错误，因为它已经无效。

要修复这个问题，你可以通过使用 clone() 方法来克隆 my_string，以保留原始值并创建一个新的 String 实例，而不是直接将所有权转移给另一个变量。例如：

```RUST
let my_string = String::from("HelloWorld");
let output_string = my_string.clone();

println!("{output_string}");
println!("{my_string}");
```

因此，在RUST中，进行复制（Copy）操作时一定要考虑所有权的问题。