# Vận dụng phép tính modulo (phép lấy số dư)

## Tầm quan trọng của Toán

Cổ nhân đã từng nói:

>Toán học là tình nhân muôn thuở của loài người. Toán đầy rẫy bí hiểm và con đường tìm đến nó có nhiều chông gai, nhưng con người lại không thể sống mà không có Toán.

Thật vậy, trong sự phát triển không ngừng của xã hội hiện đại, đi cùng với sự ra đời của các quy luật cùng những phương pháp ứng dụng công phu các thành tựu khoa học vào đời sống là sự đồng hành và phát triển không ngừng của môn Toán: từ những phép cộng, trừ đầu tiên của con người thuở sơ khai, chúng ta đã đi đến những lý thuyết trừu tượng và đặc sắc hơn như Giải tích, Tô pô học, những ứng dụng của Toán học đã đi đến giá trị biến thiên của vạn vật trên các đơn vị nhỏ nhất của không gian và thời gian. Tầm quan trọng của môn Toán đối với lịch sử phát triển của nhân loại, vì những lý lẽ trên, là không thể bàn cãi.

Đối với lập trình cũng vậy. Ngôn ngữ lập trình vốn được ra đời trên cơ sở vận dụng các khái niệm toán học về đại số, logic nhằm giải quyết các vấn đề cần tới tính toán và xây dựng trình tự. Vì vậy, bản thân việc lập trình đòi hỏi ở người viết mã cho chương trình có khả năng ứng dụng tốt các kiến thức toán học căn bản của mình, sao cho chương trình chạy hiệu quả và tối ưu nhất. Với kinh nghiệm của bản thân, một người hiểu đôi chút về toán có thể rút ngắn bài lập trình của mình được kha khá.

Lấy một ví dụ đơn giản, chúng ta viết một chương trình để xác định xem một số tự nhiên $n\geq2$ bất kì có phải là số nguyên tố hay không. (Nhắc lại khái niệm, số nguyên tố là số tự nhiên chỉ nhận duy nhất hai ước số nguyên dương: số 1 và chính nó).

Thông thường, chúng ta một cách nghĩ đơn giản nhất cho phương pháp giải quyết vấn đề trên: chúng ta thử hết các số từ $2$ đến $n-1$, nếu không tồn tại số nào trong đấy là ước số của $n$ thì $n$ là một số nguyên tố. Phương pháp này có độ phức tạp $O(n)$.

Tuy nhiên, khi chúng ta đã biết đến khái niệm về căn bậc hai, trong các phép nhân hai số để ra kết quả $n$, tạm gọi là khi $n=xy$, ta có một phép tính tương đương $(\sqrt n)^2=xy$. Bởi lẽ, nếu $x\leq\sqrt n$ thì $y\geq\sqrt n$ và ngược lại.

Vậy nên, chúng ta hoàn toàn có thể rút ngắn bài lập trình trên: chúng ta chỉ cần tạo đủ số vòng lặp các số tự nhiên nhỏ hơn hoặc bằng $\sqrt n$, nếu không tồn tại số nào trong khoảng đấy là ước số của $n$, chương trình hoàn toàn có thể kết luận $n$ là một số nguyên tố. Độ phức tạp của nó vì vậy rút gọn xuống còn $O(\sqrt n)\subseteq O(n)$.

Ví dụ ngắn gọn bên trên chính là sự kì diệu của việc ứng dụng kiến thức toán học vào toán học: chỉ cần chút mẹo nhỏ trong đấy, chúng ta đã rút gọn quy trình của bài toán.

Trong bài blog này, tôi sẽ trình bày một số kinh nghiệm của bản thân mình trong việc ứng dụng phép lấy số dư ($a\mod b$) vào những bài tập lập trình, hoặc xa hơn nữa là trong đời sống. Có lẽ, không phải là nói quá về sự kì diệu của phép tính này khi áp dụng vào giải quyết các vấn đề, một phép tính thật không may là không có tên gọi đủ ngắn gọn để được xếp bên cạnh "cộng trừ nhân chia" trong lời ăn tiếng nói của người Việt.

## Oẳn tù tì

Chúng ta sẽ mở đầu bằng một trò chơi hết sức thân thuộc: hai người chơi phân định thắng thua với nhau bằng các kí hiệu tay hình đầu búa (hoặc hòn đá), cây kéo hoặc cái bao (hoặc tớ giấy). Kết quả chung cuộc được xác định dựa trên các hình dung rất đỗi bình dân về tương quan giữa các sự vật: kéo cắt nát bao, bao bọc kín búa, và búa đập vỡ kéo.

Thông thường, đây chính là bài tập nhập môn của dạy ngôn ngữ lập trình, với việc nhận hai tham số đầu vào (có thể là tham số được lấy ngẫu nhiên) và sử dụng các mệnh đề điều kiện trong một cấu trúc rẽ nhánh để phân định thắng thua.

Thuật toán cơ bản như sau:
:::info
**Đầu vào**: Kí hiệu tay của người chơi 1 và kí hiệu tay của người chơi 2 (có thể thay bằng người đấu với máy).
**Đầu ra**: Kết quả thắng thua.
- **Nếu** hai bên có kí hiệu giống nhau **thì**:
- Kết quả hòa.
- **Nếu không**:
- **Nếu** một bên ra kéo và một bên ra bao **thì**:
- Kết quả: Kéo thắng bao.
- **Còn nếu** một bên ra búa và một bên ra kéo **thì**:
- Kết quả: Búa thắng kéo.
- **Còn nếu** một bên ra bao và một bên ra búa **thì**:
- Kết quả: Bao thắng búa.
- **Kết thúc điều kiện**
- **Kết thúc điều kiện**
:::

Về cách thực hiện nó trên ngôn ngữ lập trình cụ thể, xin được giới thiệu video của youtuber Dũng Lại Lập Trình, một trong những idol của mình cũng như các anh em khác theo đuổi ngành học máy tính:

{%youtube HyovJpkPSfY%}

Thuật toán trên, không bàn cãi, hoạt động hiệu quả, khi bản thân nó là tổ hợp của các mệnh đề điều kiện, vốn cũng là cách lập luận logic thuần túy xoay quanh trò chơi này. Tuy vậy, chúng ta có thể rút gọn được nó hay không?

Chúng ta gán các số như sau vào các kí hiệu tay của người chơi: 0 - :punch:, 1 - :v:, 2 - :hand:

Để đơn giản hóa cách lập luận của bài toán, chúng ta sẽ sử dụng các con số trên.

Gọi $a_1$ là kết quả của người chơi 1, $a_2$ là kết quả của người chơi 2.

Chúng ta có bảng kết quả như sau, trong trường hợp người chơi 1 **không thua** người chơi 2:

|$a_1$|$a_2$|Kết quả|
|-|-|-|
|0|0|hòa|
|1|1|hòa|
|2|2|hòa|
|0|1|thắng|
|1|2|thắng|
|2|0|thắng|

Sử dụng toán học để mô hình hóa kết quả, ta thấy:
1. Người chơi 1 hòa người chơi 2 nếu $a_1=a_2$
2. Người chơi 1 thắng người chơi 2 khi nào? ==**Khi $(a_1+1)\mod 3=a_2$!**==

Thật bất ngờ phải không?

Trong đại số trừu tượng, đây là một cách áp dụng cơ bản lý thuyết nhóm tuần hoàn $G=(\Bbb Z_3,+)$. Tuy nhiên, do Toán học không phải là chuyên ngành của tôi, cũng như việc viết sâu vào lý thuyết nhóm sẽ làm bài blog dài ra không cần thiết, nên xin hẹn các bạn nếu có duyên sẽ trở lại vấn đề này một cách sâu sắc và chỉn chu hơn trong bài viết khác.

Nhờ vào áp dụng phép lấy số dư, chúng ta đã rút ngắn bài toán như sau.

:::info
**Đầu vào**: $a_1$, $a_2$ tương ứng với kí hiệu của mỗi người chơi.
**Đầu ra**: Kết quả thắng thua.
- **Nếu** $a_1=a_2$ **thì**:
- Kết quả hòa.
- **Còn nếu** $(a_1+1)\mod 3=a_2$ **thì**:
- Người chơi 1 thắng người chơi 2.
- **Nếu không**:
- Người chơi 1 thua người chơi 2.
- **Kết thúc điều kiện**
:::

Trong ngôn ngữ Python, đoạn mã được viết như sau:

def paper_scissor_stone(player:int, opponent:int)->str:
    if player == opponent:
        return "Draw"
    elif (player + 1) % 3 == opponent:
        return "Win"
    return "Lose"

### Tính hiệu quả

Để so sánh sự tối ưu về mặt thuật toán giữa hai phương pháp, chúng ta sẽ sử dụng số mệnh điều kiện trong cấu trúc rẽ nhánh để phân tích và đối chiếu.

Nếu phương pháp so sánh nguyên thủy được áp dụng, chúng ta sẽ xem xét các trường hợp độc lập và riêng lẻ giữa hai tham số người chơi. Vậy tổng số mệnh đề so sánh cần đến sẽ là $3^2=9$.

Nếu ta tổng hợp lại các mệnh đề hòa lại làm một, chúng ta giảm đi hai mệnh đề dư thừa nữa ("nếu kí hiệu như nhau" thay vì liệt kê là "kéo-kéo", "búa-búa", "bao-bao"). Số mệnh đề thực sẽ còn lại $9-2=7$.

Tuy nhiên, với một mệnh đề được triển khai phép tính lấy số dư để thay thế gần hết các mớ suy luận logic dài dòng, số mệnh đề chỉ còn lại $3$.

$3<7<9$, phương pháp cuối cùng hiệu quả gấp 3 lần phương pháp nguyên thủy, và gấp xấp xỉ 2 lần so với phương pháp rút ngắn mệnh đề hòa nhau.

## Tín hiệu DTMF

Ấy là nội dung đồ án Cử nhân Điện tử của tôi, khi khoa yêu cầu sinh viên chúng tôi, trong một nhóm từ 6-7 người, chế tạo một hệ thống robot vận chuyển hàng hóa trên lộ trình được định vị bằng tín hiệu Morse trong từ trường, và giữa robot với trạm trung chuyển có sự liên hệ với nhau bằng tín hiệu DTMF.

Trước khi bước vào lý giải phương pháp ứng dụng, tôi xin phép trình bày sơ qua về tín hiệu âm thanh DTMF, một loại tín hiệu rất gần gũi với các bạn đọc 10X đổ về trước, gắn liền với các điện thoại bàn phím cơ.

:::info
DTMF (Dual Tone Multi Frequency - âm kép đa tần) là phương pháp được sử dụng để quay số điện thoại hoặc ra lệnh cho các hệ thống chuyển mạch. DTMF được sử dụng rộng rãi để truyền tín hiệu viễn thông giữa các thiết bị cầm tay và trung tâm chuyển mạch qua các đường dây điện thoại tương tự trong các dải tần số giọng nói.

Tính chất của tín hiệu DTMF: DTMF là tín hiệu tổng của hai tín hiệu hình sin cao tần $F_h(t)=\frac V2\sin(2\pi\nu_ht)+\frac V2(V)$ ($\nu_h\in\{1209,1336,1477,1633\}(Hz)$) và hạ tần $F_l(t)=\frac V2\sin(2\pi\nu_lt)+\frac V2(V)$ ($\nu_l\in\{697,770,852,941\}(Hz)$). Mỗi cặp cao tần - hạ tần khác nhau tương ứng với các kí tự khác nhau:

|Tần số|$1209Hz$|$1336Hz$|$1477Hz$|$1633Hz$|
|-|-|-|-|-|
|$697Hz$|`1`|`2`|`3`|`A`|
|$770Hz$|`4`|`5`|`6`|`B`|
|$852Hz$|`7`|`8`|`9`|`C`|
|$941Hz$|`*`|`0`|`#`|`D`|

Tín hiệu DTMF có độ lớn được tính theo công thức:

$$
\begin{array}{l}F(t)&=\frac12(F_h(t)+F_l(t))\\&=\frac V4\left(\sin(2\pi\nu_ht)+\sin(2\pi\nu_lt)\right)+\frac V2\\&=\frac V2\sin(\pi(\nu_h+\nu_l)t)\cos(\pi(\nu_h-\nu_l)t)+\frac V2\end{array}
$$
:::


Nhiệm vụ của chúng tôi lúc ấy, trên nền một mạch nhúng Intel LPC1769 có cấy chip DAC (Digital-Analog Converter - Bộ chuyển đổi từ tín hiệu số sang tín hiệu tương tự), thông qua việc tách một tín hiệu hình sin thành các mẫu, và sử dụng bộ đếm thời gian (timer) của mạch để phát tín hiệu theo đúng chu kỳ và độ lớn.

Ở đây, chúng ta tạm không đề cập đến quá trình lấy các mẫu tín hiệu từ tín hiệu hình sin để tính toán độ lớn, mà chỉ nói đến việc làm sao để lấy cặp cao tần - hạ tần tương ứng với kí tự muốn lấy.

Gọi $\mathcal L_h=(1209,1336,1477,1633)$ là chuỗi danh sách các tần số cao tần, gọi $\mathcal L_l=(697,770,852,941)$ là chuỗi danh sách các tần số hạ tần. Chuỗi danh sách được định vị từ trái sang phải bằng các chỉ mục bắt đầu từ con số $0$.

Quan sát bảng đối chiếu ký tự bên trên, chúng ta thấy ma trận 3x3 gồm các chữ số từ 1 đến 9 nằm chếch về góc trái cùng của bảng. Điều này cho ta gợi ý gì về sự liên quan giữa kí tự số và các chỉ mục?

:::info
Gọi $i_h:\Bbb N^*\to\Bbb N$ là hàm số trả ra chỉ mục tương ứng của ký tự trong chuỗi danh sách các tần số cao tần. Chúng ta có:
$$
\forall k(k\in\{i\}_{i=1}^9\implies i_h(k)=(k-1)\mod 3)
$$
Gọi $i_l:\Bbb N^*\to\Bbb N$ là hàm số trả ra chỉ mục tương ứng của ký tự trong chuỗi danh sách các tần số hạ tần. Chúng ta có:
$$
\forall k\left(k\in\{i\}_{i=1}^9\implies i_l(k)=\left\lfloor\frac{(k-1)}3\right\rfloor\right)
$$
:::

:::success
Như vậy, cho kí tự `k` trong khoảng từ `1` đến `9`, tần số tín hiệu cao tần và hạ tần sẽ lần lượt là $\nu_h=\mathcal L_h[i_h(k)]$ và $\nu_l=\mathcal L_l[i_l(k)]$
:::

## Bài toán sắp xếp bộ bài

Trong tiết tiếng Anh chuyên ngành, giảng viên có cho chúng tôi chơi boardgame sử dụng các lá bài được đánh số. Sau khi trò chơi kết thúc, thầy yêu cầu chúng tôi sắp xếp lại lá bài sao cho không bị lẫn lộn các số vào nhau, thuận lợi cho những người chơi sau đó có thể chơi mà không phải cất công tìm lá bài mong muốn.

Vấn đề được khái quát lại như sau: Cho $n$ lá bài được để rải rác và ngẫu nhiên trên bàn, hãy sắp xếp các lá bài theo thứ tự đánh số từ trên xuống dưới (hoặc ngược lại) theo cách hiệu quả nhất.

Trước khi đi đến giải pháp mà chúng tôi đã sử dụng cho bài toán trên, chúng ta hãy đi đến hai bổ đề là các thuật toán sau.

### Bổ đề: Thuật toán Radix Sort

Cho một chuỗi danh sách $L$ chứa $n$ số, mỗi số gồm $m$ chữ số. Hãy sắp xếp chuỗi danh sách sao cho các số được sắp xếp theo đúng thứ tự từ trên xuống dưới.

:::info
- Khởi tạo biến $k\gets 1$.
- **Với mọi** $k\in\{i\}_{i=1}^m$ **tiến hành**:
- Tạo chuỗi tạm $l$ là ánh xạ của chuỗi $L$ qua phép lấy số dư $10^k$:
$$
\forall j(j\in\{i\}_{i=1}^n\implies l[j]=L[j]\mod 10^k)
$$
- Sắp xếp chuỗi $l$ theo giá trị của chữ số bên trái cùng của các số.
- Cập nhật chuỗi $L$ theo sự biến đổi của chuỗi $l$.
- **Kết thúc vòng lặp**
:::

**Độ phức tạp**: $O(mn)\xrightarrow{m\ll n}O(n)$.

### Bổ đề: Thuật toán Bucket Sort

Cho một chuỗi danh sách $L$ chứa $n$ số, cho $B$ chuỗi danh sách chứa $m$ "giỏ".

:::info
- Khởi tạo biến $M\gets\max(L)+1$.
- **Với mọi** $i\in L$ **tiến hành**:
- Thêm $i$ vào giỏ $B\left[\left\lfloor\frac{m.i}M\right\rfloor\right]$
- **Kết thúc vòng lặp**
- **Với mọi** $b\in B$ **tiến hành**:
- Sắp xếp lại các phần tử trong $b$ theo thứ tự.
- **Kết thúc vòng lặp**
- Ghép các giỏ lại với nhau theo thứ tự.
:::

**Tính chất**: Thuật toán Bucket Sort là thuật toán họ hàng của Radix Sort.

**Độ phức tạp**: $O(n^2)$.

### Giải pháp cho vấn đề xếp bài

Một bộ bài được đánh số từ 1 đến 100. Chúng tôi, có hai người, cùng thực hiện sắp xếp lại bộ bài. Vì trên bàn có các lá bài nằm rải rác, nếu sắp xếp theo hướng lượm từng lá bài một theo thứ tự để xếp bộ bài, thì rất mất thời gian.

Tôi mới đề xuất ra một giải pháp cho hai đứa: xác định 10 ô tương ứng với các chữ số bên trái cùng của các số trên bộ bài. sau đó ở mỗi ô sẽ tiến hành sắp xếp lại theo thứ tự. Mọi việc diễn ra rất suôn sẻ, nhưng lúc đó, tôi vẫn loay hoay chưa hiểu mấy về độ hiệu quả của nó. Ấy đơn thuần là một giải pháp đưa ra từ sự phản xạ.

Tôi về hỏi một người bạn học về Kĩ thuật Phần mềm, và sau đó mới được giải đấp về kiểu thuật toán Radix Sort. Đến hôm nay, sự giải đáp của ChatGPT đã đưa tôi đến kiểu thuật toán Bucket Sort cùng họ hàng.

Vì vậy, giải pháp trên chính là một sự vận dụng khéo léo các thuật toán Radix Sort và Bucket Sort vào đời sống.

## Tham khảo

1. ChatGPT
2. Wikipedia