ALGORITHM

COMPUTATION

CRYPTOGRAPHY

FRONTEND

GAME-THEORY

INVESTMENT

JS&TS

LINUX

MATHEMATICS

NODE

PROJECT-PRACTICE

REACT

THOUGHTS

古文整理

文史哲艺


Brief Introduction to the Implementation Approach in glibc:

For the logarithm of any base, we can utilize the change of base formula:

$$
\log_k{x} = \frac{\ln{x}}{\ln k} \tag{1}
$$

The term $\ln k$ in equation (1) is a constant, so for logarithms of any base, we only need to calculate $\ln x$.

### Computation of $\ln x$

In advanced calculus, we learned the following Taylor series:

$$
\ln(1+x) = x - \frac{1}{2}x^2 + \frac{1}{3}x^3 - \frac{1}{4}x^4 + \dots = \sum_{k=1}^{\infty}\frac{(-1)^k}{k}x^k \tag{2}
$$

Suppose we want to find $\ln x$; naturally, we can set $t=x-1$, then:

$$
\ln(x) = \ln(1+t) = \sum_{k=1}^{\infty}\frac{(-1)^k}{k}t^k \tag{2}
$$

However, expanding the series to infinity in practical calculations is often not feasible. If we expand it to the $n$th term, the Taylor series with the Peano remainder term can be expressed as:

$$
\ln(1+t) = t - \frac{1}{2}t^2 + \frac{1}{3}t^3 - \frac{1}{4}t^4 + \dots = \sum_{k=1}^{n}\frac{(-1)^k}{k}t^k + o(t^n) \tag{3}
$$

Note that the Peano remainder term here is $o(t^n)$, representing the error term. If $t>1$ (or $x > 2$), the error in the above formula may become significantly large with the increase of $t$ or $x$.

However, another formula is available:

$$
\ln x = 2\left(\frac{x-1}{x+1} + \frac{1}{3}\left(\frac{x-1}{x+1}\right)^3 + \frac{1}{5}\left(\frac{x-1}{x+1}\right)^5 + \dots\right) = 2\sum_{k=0}^{\infty}\frac{1}{2k+1}\left(\frac{x-1}{x+1}\right)^{2k+1} \tag{4}
$$

Here's an informal proof for equation $(4)$:

Replace $x$ in equation $(2)$ with $\frac{1}{x}$ and $-\frac{1}{x}$, respectively:

$\begin{aligned}
\ln\left(1+\frac{1}{x}\right) &= \ln\left(\frac{x+1}{x}\right) = \sum_{k=1}^{\infty}\frac{(-1)^k}{k}\frac{1}{x^k} \\
\ln\left(1-\frac{1}{x}\right) &= -\sum_{k=1}^{\infty}\frac{1}{kx^k}
\end{aligned}$

Note:

$\begin{aligned}
\ln\left(\frac{x-1}{x}\right) &= -\sum_{k=1}^{\infty}\frac{1}{kx^k} \\
\Longrightarrow -\ln\left(\frac{x-1}{x}\right) &= \sum_{k=1}^{\infty}\frac{1}{kx^k} \\
\Longrightarrow \ln\left(\frac{x}{x-1}\right) &= \sum_{k=1}^{\infty}\frac{1}{kx^k}
\end{aligned}$

Then:

$\begin{aligned}
&\ln\left(\frac{x+1}{x}\right) + \ln\left(\frac{x}{x-1}\right) = \ln\left(\frac{x+1}{x-1}\right) \\
&\sum_{k=1}^n\frac{(-1)^k}{kx^k} + \sum_{k=1}^n\frac{1}{kx^k} = 2\sum_{k=0}^n{\frac{1}{2k+1}\frac{1}{x^{2k+1}}}
\end{aligned}$

This yields:

$$
\ln\left(\frac{x+1}{x-1}\right) = 2\sum_{k=0}^n{\frac{1}{2k+1}\frac{1}{x^{2k+1}}}
$$

Let $z = \frac{(x+1)}{(x-1)}$, then $x = \frac{(z-1)}{(z+1)}$. Substituting this into the above formula gives equation (4).

The advantage of this formula is that if we expand it to the $n$th term:

$$
\ln x = 2\sum_{k=0}^{n}\frac{1}{2k+1}\left(\frac{x-1}{x+1}\right)^{2k+1} + o\left(\left(\frac{x-1}{x+1}\right)^{2k+1}\right) \tag{5}
$$

The remainder term is $o\left(\frac{(x-1)}{(x+1)^{2k+1}}\right)$, and as $\lim_{x\rightarrow+\infty}\left(\frac{x-1}{x+1}\right)^{2k+1} = 1$, the remainder term ensures that the error remains within the range of $1$.

However, this is still not sufficient, as the error of $1$ is still too large. According to the analysis of the remainder term above, the value of $x$ should be closer to $1$ for higher precision.

Considering the IEEE 754 floating-point standard, we know that any floating-point number is represented in the computer as:

$$
x = 1.xxx \times 2^{exp}
$$

This means that we can directly obtain the exponent ($\text{exp}$) and the fractional part ($1.xxx$) using bitwise operations.

Since the floating-point number is already in this form, we can directly use the fractional part $1.xxx$. If we calculate $\ln(1.xxx)$ using the earlier formula, it is equivalent to calculating $\ln\left(\frac{x}{2^{exp}}\right)$. According to the logarithmic formula:

$$
\ln\left(\frac{x}{2^{exp}}\right) = \ln x - \text{exp}\times \ln 2
$$

Therefore:

$$
\ln x = \ln\left(\frac{x}{2^{exp}}\right) + \text{exp} \times \ln 2
$$

This completes the calculation of $\ln x$, equivalent to computing the logarithm of any base.

However, this is a general overview, and glibc employs various precision improvement techniques in its implementation.


Take the Glibc's Mindset for Example

How Do Computer Calculate the Log-Function


## Finding the Majority Element

Moore's Voting Algorithm is an algorithm used to find the element that appears more than half the time in an array. The basic idea of the algorithm is to find the element with a count exceeding half through the cancellation of different elements.

The algorithm steps are as follows:

1. Initialize two variables `candidate` and `count`, representing the candidate element and the counter. Initially, set `candidate` to the first element of the array and `count` to 1.
2. Traverse the array, starting from the second element:
   - If the current element is the same as `candidate`, increment the `count` by 1.
   - If the current element is different from `candidate`, decrement the `count` by 1.
     - If `count` becomes 0, set the current element as the new `candidate` and reset `count` to 1.
3. The final `candidate` is the element that may appear more than half the time.
4. Traverse the array, count the occurrences of the `candidate`, and ensure its count indeed exceeds half.

Below is an example code demonstrating how to use Moore's Voting Algorithm to find the element that appears more than half the time:

```c
#include <stdio.h>

int findMajorityElement(int arr[], int size) {
    int candidate = arr[0];
    int count = 1;

    for (int i = 1; i < size; i++) {
        if (arr[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            }
        }
    }

    // Validate whether the candidate is the element appearing more than half the time
    int freq = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == candidate) {
            freq++;
        }
    }
    if (freq > size / 2) {
        return candidate;
    } else {
        return -1;  // No element found appearing more than half the time
    }
}

int main() {
    int arr[] = {2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8};
    int size = sizeof(arr) / sizeof(arr[0]);

    int majorityElement = findMajorityElement(arr, size);

    if (majorityElement != -1) {
        printf("The element appearing more than half the time is: %d\n", majorityElement);
    } else {
        printf("No element appearing more than half the time\n");
    }

    return 0;
}
```

In the above example, for the array `{2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8}`, the element `2` appears more than half the time, so the algorithm outputs `2`.

## Extension: Finding Elements Appearing more than n-th of the Total

Moore's Voting Algorithm can be modified to find elements that appear more than n-th of the total count. The key modification lies in determining the required counting threshold.

Assuming the array length is `size`, to find elements that appear more than n-th of the total count, set the counting threshold to `size / n`. This means that when the count of an element reaches this threshold, it can be considered a valid element.

When finding elements that appear more than n-th of the total count, the following modifications can be made to Moore's Voting Algorithm:

1. Initialize two arrays `candidate` and `count`, both with a length of n-1. The `candidate` array is used to store candidate elements, and the `count` array is used to store corresponding counters. Initially, set all elements of the `candidate` array to -1 and all elements of the `count` array to 0.
2. Traverse the array for each element:
   - Check if the same candidate element exists in the `candidate` array for the current element.
     - If found, increment the corresponding counter by 1.
     - If not found, find the first position in the `candidate` array where the counter is 0. Set the current element as a new candidate in that position and set the corresponding counter to 1.
       - If no position with a counter of 0 is found, it means the `candidate` array is full. In this case, decrement all counters by 1 to cancel out one element.
3. Traverse the `candidate` array and validate whether each candidate element appears more than `size / n` times. Count the occurrences of each candidate in the original array, and if it exceeds `size / n`, output that candidate.
4. If no candidate element appears more than n-th of the total count, there is no element satisfying the condition.

The modified algorithm steps above involve traversing the array, using candidate elements and counters to cancel out, and ultimately finding elements that appear more than n-th of the total count.

Below is the modified example code:

```c
#include <stdio.h>

int findMajorityElement(int arr[], int size, int n) {
    int candidate[n - 1];
    int count[n - 1];

    for (int i = 0; i < n - 1; i++) {
        candidate[i] = -1;
        count[i] = 0;
    }

    for (int i = 0; i < size; i++) {
        int j;
        for (j = 0; j < n - 1; j++) {
            if (arr[i] == candidate[j]) {
                count[j]++;
                break;
            }
        }
        if (j == n - 1) {
            int k;
            for (k = 0; k < n - 1; k++) {
                if (count[k] == 0) {
                    candidate[k] = arr[i];
                    count[k] = 1;
                    break;
                }
            }
            if (k == n - 1) {
                for (k = 0; k < n - 1; k++) {
                    count[k]--;
                }
            }
        }
    }

    // Validate whether each candidate appears more than size/n times
    int freq = 0;
    for (int i = 0; i < n - 1; i++) {
        int count = 0;
        for (int j = 0; j < size; j++) {
            if (arr[j] == candidate[i]) {
                count++;
            }
        }
        if (count > size / n) {
            freq++;
            printf("The element appearing more than %d-th of the total is: %d\n", n, candidate[i]);
        }
    }

    if (freq == 0) {
        printf("No element appearing more than %d-th of the total\n", n);
    }

    return 0;
}

int main() {
    int arr[] = {2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8, 3, 3, 3, 3};


 int size = sizeof(arr) / sizeof(arr[0]);
    int n = 4;

    findMajorityElement(arr, size, n);

    return 0;
}
```

In the above example, for the array `{2, 4, 2, 2, 5, 2, 2, 6, 2, 2, 8, 3, 3, 3, 3}`, both elements `2` and `3` appear more than 4-th of the total count, so the algorithm outputs:

```plaintext
The element appearing more than 4-th of the total is: 2
The element appearing more than 4-th of the total is: 3
```


Moore's Voting Algorithm is an algorithm used to find the element that appears more than half the time in an array.

Moore's Voting Algorithm for Finding Majority Element


A*search algorithm is a **path finding** algorithm that finds **the** **single-pair** **shortest path** between the **start node(source)** and the **target node(destination)** of a **weighted** graph. The algorithm not only considers the actual cost from the start node to the current node(g) but also tries to estimate the cost will take from the current node to the target node using **heuristics** (h). Then it selects the node that has the **lowest f-value**(**f=g+h**) to be the next node to move until it hits the target node. **Dijkstra's algorithm** is a special case of A* algorithm where **heuristic is 0** for all nodes.

![A Star Search](https://miro.medium.com/v2/resize:fit:875/1*QvF-25wEHhQiWowGeJ8JjQ.png)

## How A\* Algorithm Works?

The formula for A\* algorithm considers two functions, **g(n) and h(n)**. Imagine that we are currently at node n, **g(n)** tells us the **actual cost** we took from the start node to the current node. **h(n)** is a **heuristic function** that **estimates** **the cost** we will take to get to the target node from the current node. Therefore, h(n) is an **educated guess** and it is crucial to determine the performance of A* algorithm. Based on the sum of the g(n) and h(n), **f(n)**, the algorithm is able to estimate the **total cost** from the start node to the end node.

**f(n) = g(n) + h(n)** , f(n): the estimate of the total cost from start node to target node through node n  
g(n): actual cost from start node to node n  
h(n): estimated cost from node n to target node

The algorithm selects the **minimum f-value node** as the next current node to explore and continuously update g(n) and h(n) if a better path is found for nodes it encountered. This process continues until the algorithm reaches the target node.

### A\* algorithm vs. Dijkstra's algorithm

**A\* Algorithm** only finds the shortest path between **the start node and the target node**, whereas **Dijkstra's algorithm** finds the shortest path from the **start node to all other nodes** because every node in a graph is a target node for it.

**A\* algorithm** runs **faster** than Dijkstra's algorithm because it uses a **heuristic** to direct **in the correct direction** towards the target node. However, **Dijkstra's algorithm expands evenly** in **all of the different available directions** because it has no knowledge regarding the target node before hand, it always processes the node that is the closest to the start node based on the cost or distance it already took.

![A* algorithm vs. Dijkstra's algorithm](https://miro.medium.com/v2/resize:fit:875/1*FzCo76pN8UJt2kIeOFlCzA.png)

## Graphical Explanation

> Heuristic is crucial to the performance of A\* algorithm. The heuristic function we use here just for the demo purpose.

![graph example](https://miro.medium.com/v2/resize:fit:875/1*5UTGfoZLPUA9dXJ_v_CsWg.png)

- **_Step 1_**  
   - **_a_**: Set the distance to the **start node** itself to **0** and the distance to **all other nodes** to **infinity**.  
   - **_b_**: Calculate the **f value** for the start node and set the **previous node** to none/nil/null.  
   - **_c_**: Initialize an **open list** and **close list** which are empty initially.

![step 1](https://miro.medium.com/v2/resize:fit:875/1*W6CaGse0EnoDi5RNW7Kb1g.png)

- **_Step 2_**: Place the **start node** into the **open list**

![step 2](https://miro.medium.com/v2/resize:fit:875/1*MJwjLSxWe_n1yW7rxkuu7w.png)

- **_Step 3  
   _\***-\* **_a_\***:\* Find the node with **the** **minimum f-value** in the **open list** and **removed** from the list. Denote this node as the **current node**.  
   - **b**: Check if the **current node** is the **target node** or not  
   - **c**: **Populate** all the current node's **neighboring nodes** and do following checks for each neighboring nodes

**1. Is the neighboring node in the close list?**

- Yes. Skip this node.
- No. Go to 2.**2. Calculate g value for the neighboring node and check if a better  
  path(lower g value) is found?** - No, Skip this node
- Yes. Go to 3.**3. Calculate g, h and f value for the neighboring node and set  
  the previous node to the current node\*\***4. Check if the neighbor node in the open list?\*\*
- Yes. Update g, h and f value of the neighboring node in the  
  open list
- No. Insert this neighboring node to the open list

- **d**: Place the **current node** to the **close list** because we have expanded this node.

![step 3](https://miro.medium.com/v2/resize:fit:875/1*ALCIZaJVV_iZ22aJDn8KwA.png)

- **_Step 4_**: Repeat _Step 3_ until reaches the target node

### demo iteration 1

![iteration 1–1](https://miro.medium.com/v2/resize:fit:875/1*3daYK311AZ5EhMZ7SlfMyA.png)

![iteration 1–2](https://miro.medium.com/v2/resize:fit:875/1*yxdTd3QM0kQiZ-Xa5Rdinw.png)

![iteration 1–3](https://miro.medium.com/v2/resize:fit:875/1*bs4TplpOIkxhzx_3TKv7-A.png)

### demo iteration 2

![iteration 2–1](https://miro.medium.com/v2/resize:fit:875/1*eX758M4Z1pHgXiVf2Re1pQ.png)

![iteration 2–2](https://miro.medium.com/v2/resize:fit:875/1*8qG-dpRBcGksbFNUql6cLg.png)

![iteration 2–3](https://miro.medium.com/v2/resize:fit:875/1*wGwIDY1BdPU4fLYd03E_tw.png)

### demo iteration 3

![iteration 3–1](https://miro.medium.com/v2/resize:fit:875/1*WEIx9GyNjStRCgMmd08ksg.png)

![iteration 3–2](https://miro.medium.com/v2/resize:fit:875/1*1o9QqFM6kjeVRD96Wzk_wg.png)

![iteration 3–3](https://miro.medium.com/v2/resize:fit:875/1*AEvC7BRbwoY7OBXwbIGk4A.png)

### demo iteration 4

![iteration 4–1](https://miro.medium.com/v2/resize:fit:875/1*nOouyfpxSOaOOP2nuL9TAA.png)

![iteration 4–2](https://miro.medium.com/v2/resize:fit:875/1*xzenBGkWstsSNEoNtGBHmQ.png)

![iteration 4–3](https://miro.medium.com/v2/resize:fit:875/1*N3nVtRAcjclt4DRBSLnkSQ.png)

### demo iteration 5

![iteration 5–1](https://miro.medium.com/v2/resize:fit:875/1*LfoBualez23-DK5xMWJ7zQ.png)

### final result

![](https://miro.medium.com/v2/resize:fit:875/1*L6s9xmzwxjWjOEe-tvTPKg.png)

At the end, we can **backtrack** the shortest path using the previous node. In this demo, we use A\* algorithm to search the shortest path **without** necessarily **search all the graph.**(We haven't examined node 4 yet, so you can see the node 4 is till on the open list). Unlike Dijkstra's algorithm, it has to expand all the nodes in the graph.

You can check [here](https://yuminlee2.medium.com/dijkstras-algorithm-6ad1e4bf9876) to know more about Dijkstra's algorithm.

## Code Implementation

### Data Structure

Use **Priority queue** to get the lowest f-value node for each run. In this demo, we implement code using **min heap** data structure .

### Complexity

Time: O(nlog(n)), Space: O(n)  
n: the total number of nodes in the graph

### Pseudocode

### initialize a min Heap contains the start node

minHeap = MinHeap([start])While minHeap is not empty:

### grab the minimum f-value node from minHeap and denote as current

current = minHeap.pop() # check if current is the target node  
 if current == target:  
 break

### populate all current node's neighbors

for neighbor in current.neighbors:  
 compute neighbor's g, h, f value

      if neighbor in minHeap:
         if neighbor.g < neighbor.g in minHeap:
             update minHeap
      else:
         insert neighbor into minHeap

### Python

- code

```python
from min_heap import MinHeap
class Node:
    def __init__(self, nodeId, hValue):
        self.id = nodeId # use node idx as id
        self.g = float("inf") # distance from the start node to the current node
        self.h = hValue # estimate distance from the current node to the target node
        self.f = float("inf") # total cost from the start node to the end node
        self.previousNode = None # use for backtrack

def AstartAlgorithm(graph, start, target, hValues):
    nodes = initializeNodes(graph, hValues)

    startNode = nodes[start]
    targetNode = nodes[target]

    # set distance to start node itself to 0
    startNode.g = 0
    startNode.f = startNode.g + startNode.h

   # init open list and close list
    openList = MinHeap([startNode])  # nodes to be expanded
    # closeList = set()  # nodes have expanded

    # repeat until the openList is empty
    while not openList.isEmpty():
        # remove the node with the lowest f-value
        currentNode = openList.remove()
        if currentNode == targetNode:
            break

        # populate all current nodes neighbors
        neighbors = graph[currentNode.id]
        for neighbor in neighbors:
            neighborIdx, distanceToNeighbor = neighbor
            neighborNode = nodes[neighborIdx]

            # check if neighbor in close list
            # if neighborNode in closeList:
            #     continue

            # check if find a better path
            newNeighborG = currentNode.g + distanceToNeighbor
            if newNeighborG >= neighborNode.g:
                continue

            # update neighbor's g, h, f and previousNode
            neighborNode.previousNode = currentNode
            neighborNode.g = newNeighborG
            neighborNode.f = neighborNode.g + neighborNode.h

            # check if the neighbor in the openList
            if not openList.containsNode(neighborNode):
                openList.insert(neighborNode)
            else:
                openList.update(neighborNode)

        # put current node to close list
        # closeList.add(currentNode)

    return backtrackPath(targetNode)

def initializeNodes(graph, hValues):
    nodes = []
    for i in range(len(graph)):
        nodes.append(Node(i, hValues[i]))
    return nodes

def backtrackPath(targetNode):
    if targetNode.previousNode is None:
        return []

    currentNode = targetNode
    path = []

    while currentNode is not None:
        path.append(currentNode)
        currentNode = currentNode.previousNode

    return path[::-1]


if __name__ == "__main__":
    hValues = [20, 16, 6, 10, 4, 0]
    graph = [
            # for vertex 0
            [
                [1, 2], [3, 6]
            ],
            # for vertex 1
            [
                [0, 2], [2, 5]
            ],
            # for vertex 2
            [
                [1, 5], [3, 7], [4, 6], [5, 9]
            ],
            # for vertex 3
            [
                [0, 6], [2, 7], [4, 10]
            ],
            # for vertex 4
            [
                [2, 6], [3, 10], [5, 6]
            ],
            # for vertex 5
            [
                [2, 9], [4, 6]
            ],
        ]

    # startNode = 1, targetNode = 5
    path = AstartAlgorithm(graph, 0, 5, hValues)
    print("The shortest path")
    print("order, nodeId, f-value")
    for idx, node in enumerate(path):
        print(idx+1, node.id, node.f)

"""
The shortest path
order, nodeId, f-value
(1, 0, 20)
(2, 1, 18)
(3, 2, 13)
(4, 5, 16)
"""
```

- min heap

```python
class MinHeap:
    def __init__(self, array):
        self.nodePositionInHeap = {node.id: idx for idx, node in enumerate(array) }
        self.heap = self.buildHeap(array)

    # Time: O(n) | Space: O(1)
    def buildHeap(self, array):
        lastParentNodeIdx = (len(array) - 2) // 2
        for currentIdx in range(lastParentNodeIdx, -1, -1):
            self.siftDown(currentIdx, len(array)- 1, array)
        return array

    # Time: O(logn) | Space: O(1)
    def remove(self):
        if self.isEmpty():
            return

        self.swap(0, len(self.heap)-1, self.heap)
        nodeToRemove = self.heap.pop()
        del self.nodePositionInHeap[nodeToRemove.id]
        self.siftDown(0, len(self.heap)-1, self.heap)
        return nodeToRemove

    # Time: O(logn) | Space: O(1)
    def insert(self, node):
        self.heap.append(node)
        self.nodePositionInHeap[node.id]= len(self.heap)-1
        self.siftUp(len(self.heap)-1, self.heap)

    # Time: O(logn) | Space: O(1)
    def siftDown(self, currentIdx, endIdx, heap):
        childOneIdx = currentIdx*2 + 1
        while childOneIdx <= endIdx:
            childTwoIdx = currentIdx*2 + 1 if currentIdx*2 + 1 <= endIdx else -1
            idxToSwap = childOneIdx
            if childTwoIdx != -1 and heap[childTwoIdx].f < heap[childOneIdx].f:
                idxToSwap = childTwoIdx

            if heap[idxToSwap].f < heap[currentIdx].f:
                self.swap(idxToSwap, currentIdx, heap)
                currentIdx = idxToSwap
                childOneIdx = currentIdx*2 + 1
            else:
                return

    # Time: O(logn) | Space: O(1)
    def siftUp(self, currentIdx, heap):
        parentIdx = (currentIdx - 1) // 2
        while currentIdx > 0 and heap[currentIdx].f < heap[parentIdx].f:
                self.swap(currentIdx, parentIdx, heap)
                currentIdx = parentIdx
                parentIdx = (currentIdx - 1) // 2

    def containsNode(self, node):
        return node.id in self.nodePositionInHeap

    def update(self, node):
        # update is occured when a slower f is found
        self.siftUp(self.nodePositionInHeap[node.id], self.heap)

    def isEmpty(self):
        return len(self.heap) == 0

    def swap(self, i, j, heap):
        self.nodePositionInHeap[heap[i].id] = j
        self.nodePositionInHeap[heap[j].id] = i
        heap[i], heap[j] = heap[j], heap[i]
```


A* search algorithm is a path finding algorithm that finds the single-pair shortest path between the start node(source) and the target node(destination) of a weighted graph.

A Star Algorithm


## Problem Introduction

Let's first consider a question: **Given an array of size 100 with elements arranged from 1 to 100 in order, how can we randomly select one number from it?**

The simplest way is to use the system method `Math.random() * 100`, which will give a random number between 0 and 99, and then use it as an index to select the corresponding element in the array.

Next, consider another question: **Given the same array, how can we randomly select 50 numbers?**

**The numbers must not repeat.** If you simply select 50 numbers randomly, the issue of duplicate numbers may arise.

One possible modification is to store each randomly generated number in an array, and for each subsequent random selection, check if the number is already in the array. If it is, continue to randomly select until 50 unique numbers are chosen.

This method works but has a problem. When the number of selections approaches the size of the array, the probability of repeated numbers increases significantly. For example, **if you need to select 99 numbers from an array of size 100**, following the above approach, as the number of selected numbers increases, the probability of selecting a duplicate number also increases, making the process less efficient.

In this case, we can consider another approach: **shuffle the array first, and then directly select the first 50 numbers.**

This approach works, but the key is to ensure that the "shuffle" is truly random. For example, a deck of cards has 54 cards, and there are $54!$ possible arrangements. A shuffle should be able to **generate any of these $54!$ arrangements with equal probability**.

## Shuffle Algorithm

The **Fisher-Yates shuffle** algorithm was proposed by Ronald Fisher and Frank Yates in 1938 and later adapted for computer programming by Richard Durstenfeld in 1964.

The algorithm is very simple: starting from the last element of the array, swap it with any one of the previous elements (including itself). Then, swap the second-to-last element with one of the remaining elements, and so on.

This process ensures that every element has an **equal probability** of appearing in any position.

## Program Implementation

```typescript
function knuthShuffle<T = any>(array: T[]): T[] {
  const result = array.slice();
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

const arr = [1, 2, 3, 4, 5];
console.log(knuthShuffle(arr));
```

## Proof

The Knuth Shuffle algorithm (also known as the Fisher-Yates Shuffle) can generate all possible permutations with equal probability. To prove that the algorithm is effective in shuffling any sequence, the key is to ensure that **each permutation appears with equal probability**. Below is the mathematical proof.

For a sequence of $n$ elements, starting from the last element, randomly select one of the previous elements (including the current one) to swap. The steps are as follows:

1. For the $i$-th element (starting from $i = n$ down to $i = 2$), randomly select an index $j$ from the range [0, $i-1$] and swap element $a[i]$ with element $a[j]$.
2. Finally, all elements in the sequence are swapped once.

### Objective

We need to prove that this algorithm generates all possible permutations with equal probability. For a sequence of length $n$, there should be $n!$ different permutations, and each permutation should have a probability of $\frac{1}{n!}$.

### Analysis

1. **Total number of permutations**  
   For an array of length $n$, the total number of possible permutations is $n!$. That is, for $n$ elements, the number of unique permutations is:

   $$
   P(n) = n! = n \times (n-1) \times \cdots \times 2 \times 1
   $$

2. **Random selection process in the algorithm**  
   In the $i$-th step, the Knuth Shuffle algorithm randomly selects an index between 0 and $i$ to swap. This selection is uniform, so the probability of selecting any index is $\frac{1}{i+1}$.

   - Step 1: Choose one element out of $n$, with probability $\frac{1}{n}$.
   - Step 2: Choose one of the remaining $n-1$ elements, with probability $\frac{1}{n-1}$.
   - And so on, until no elements remain to swap.

3. **Probability of generating a specific permutation**  
   To prove that Knuth Shuffle generates all permutations with equal probability, we need to show that the probability of generating any specific permutation is $\frac{1}{n!}$.

   The probability of any element being swapped into a certain position is independent for each step:

   - The $n$-th element can be swapped with any of the $n$ elements, with probability $\frac{1}{n}$.
   - The $(n-1)$-th element can be swapped with any of the remaining $n-1$ elements, with probability $\frac{1}{n-1}$.
   - And so on.

   Therefore, the probability of generating any particular permutation is:

   $$
   \frac{1}{n} \times \frac{1}{n-1} \times \cdots \times \frac{1}{1} = \frac{1}{n!}
   $$

4. **Equal probability for all permutations**  
   Since the probability of generating each permutation is $\frac{1}{n!}$ and there are $n!$ distinct permutations, the Knuth Shuffle generates all possible permutations with equal probability.

In conclusion, the Knuth Shuffle algorithm ensures that every element is swapped with equal probability in each step, and the resulting permutations are uniformly distributed across all $n!$ possible permutations. Therefore, the Knuth Shuffle is an **effective** algorithm for shuffling any sequence in a uniformly random manner.


The Knuth Shuffle algorithm (also known as the Fisher-Yates Shuffle) generates all possible permutations with equal probability.

The Knuth Shuffle Algorithm


The Rabin-Karp algorithm, also known as the Karp-Rabin algorithm, was introduced by _Richard M. Karp_ and _Michael O. Rabin_ in 1987. It is designed to address the multiple pattern string matching problem.

Its implementation is somewhat unconventional. It begins by computing the hash values of two strings and then determines whether there is a match by comparing these hash values.

## Algorithm Analysis and Implementation

Choosing an appropriate hash function is crucial. Assuming the text string is $t[0, n)$, and the pattern string is $p[0, m)$, where $0<m<n$, let $Hash(t[i,j])$ represent the hash value of the substring $t[i, j]$.

When $Hash(t[0, m-1])!=Hash(p[0,m-1])$, it is natural to compare $Hash(t[1, m])$. In this process, if we recalculate the hash value for the substring $t[1, m]$, it would require $O(n)$ time complexity, which is not cost-effective. Observing that there are m-1 overlapping characters between the substrings $t[0, m-1]$ and $t[1, m]$, we can use a rolling hash function. This reduces the time complexity of recalculation to $O(1)$.

The rolling hash function used in the Rabin-Karp algorithm primarily leverages the concept of [Rabin fingerprint](https://en.wikipedia.org/wiki/Rabin_fingerprint). For example, the formula to calculate the hash value of the substring $t[0, m-1]$ is as follows:

$$
Hash(t[0, m-1])=t[0]*b^{m-1}+t[1]*b^{m-2}+...+t[m-1]*b^0
\\
\tag{t[0] represents the ASCII code of the character}
$$

Here, $b$ is a constant. In Rabin-Karp, it is generally set to 256 because the maximum value of a character does not exceed 255. The formula above has an issue - hash values could overflow. To address this, we take the modulus, and the value should be as large as possible and preferably a prime number. Here, we take 101.

The formula to calculate the hash value of the substring $t[1, m]$ is then:

$$
Hash(t[1,m])=(Hash(t[0,m-1])-t[0]*b^{m-1})*b+t[m]*b^0\\\tag{Please compare with the previous formula}
$$

The complete code is as follows:

```cpp
#include <iostream>
#include <string.h>

using namespace std;

#define BASE 256
#define MODULUS 101

void RabinKarp(char t[], char p[])
{
    int t_len = strlen(t);
    int p_len = strlen(p);

    // For rolling hash
    int h = 1;
    for (int i = 0; i < p_len - 1; i++)
        h = (h * BASE) % MODULUS;

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++)
    {
        t_hash = (BASE * t_hash + t[i]) % MODULUS;
        p_hash = (BASE * p_hash + p[i]) % MODULUS;
    }

    int i = 0;
    while (i <= t_len - p_len)
    {
        // Considering the possibility of hash collisions, we use memcmp for additional verification
        if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
            cout << p << " is found at index " << i << endl;

        // Rolling hash
        t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;

        // Avoiding negative values
        if (t_hash < 0)
            t_hash = t_hash + MODULUS;

        i++;
    }
}

int main()
{
    char t[100] = "It is a test, but not just a test";
    char p[10] = "test";

    RabinKarp(t, p);

    return 0;
}
```

The output is as follows:

```text
test is found at index 8
test is found at index 29
```

## Complexity Analysis

Let's examine the space complexity first, which is easily determined: $S(n)=O(1)$.

Now, consider the time complexity. Let the length of the text string be n and the pattern string be m. Preprocessing requires $O(m)$, and during matching, in the best case where there are no hash collisions, $T_{best}(n)=O(n-m)$. In the worst case, where there is a collision every time, $T_{worst}(n)=O((n-m)*m)$. In practical scenarios, n is often much larger than m, so the final complexity table is:

| $S_{n}$        | $O(1)$  |
| -------------- | ------- |
| $T_{best}(n)$  | $O(n)$  |
| $T_{worst}(n)$ | $O(mn)$ |

## Application Analysis

The primary application of the Rabin-Karp algorithm is in plagiarism detection for articles, such as the detection system used by [Semantic Scholar](https://www.semanticscholar.org/).

However, from the complexity data above, the Rabin-Karp algorithm does not seem to have a significant advantage. Is it practical for detecting text plagiarism? Feedback from actual usage results indicates that the time complexity for plagiarism detection is only $O(n)$. I believe this is mainly due to the following two points:

1. In real-life articles, the text data does not often exhibit as many hash collisions as we might imagine.
2. The original content in a submitted article is likely to be much larger than the plagiarized content. In other words, successful matches do not occur as frequently as we might imagine.

## References

- [Rabin–Karp algorithm](https://en.wikipedia.org/wiki/Rabin–Karp_algorithm)
- [Searching for Patterns | Set 3 (Rabin-Karp Algorithm)](https://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/)
- [Computer Algorithms: Rabin-Karp String Searching](http://www.stoimen.com/blog/2012/04/02/computer-algorithms-rabin-karp-string-searching/)


It is designed to address the multiple pattern string matching problem.

Rabin-Karp Algorithm


## Problem Description

The Josephus problem is a classic mathematical problem that describes the following scenario:

There are $n$ people standing in a circle. Starting from a certain person, they count off in sequence, and every $m$-th person steps out of the circle. The counting and elimination process continues, looping back to the next person when the end of the circle is reached. This continues until only one person remains. The problem is to determine the initial position of the last person remaining in the circle.

For example, when $n=7$ and $m=3$, the order of elimination is: $3, 6, 2, 7, 5, 1$. The last person remaining is at position $4$.

## Solution

The Josephus problem can be solved using either recursion or mathematical formulas. The recursive solution assumes knowledge of the solution for $n-1$ people, denoted as $f(n-1, m)$, and then calculates the solution for $n$ people using the formula:

$
f(n, m) = (f(n-1, m) + m) \% n
$

Here, $\%$ denotes the modulo operation. The base case is $f(1, m) = 0$, representing the solution when there is only one person.

The mathematical formula solution is derived based on the recurrence relation, resulting in the same formula:

$
f(n, m) = (f(n-1, m) + m) \% n
$

## Programming Implementation

When it comes to solving the Josephus problem, dynamic programming is an effective approach. Here is an example C code implementing dynamic programming to solve the Josephus problem:

```c
#include <stdio.h>

int josephus(int n, int m) {
    int dp[n + 1];
    dp[1] = 0; // Initial position when there is only one person

    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + m) % i;
    }

    return dp[n];
}

int main() {
    int n = 7; // Total number of people
    int m = 3; // Count off to m for elimination

    int lastPerson = josephus(n, m);
    printf("The last person remaining is: %d\n", lastPerson + 1); // Adding 1 due to 0-based indexing

    return 0;
}
```

In the above code, we use a dynamic programming array `dp` to store the next position after each person is eliminated. Through iteration, we can find the initial position of the last person remaining in the circle. In the `main` function, we set the total number of people `n` and the count to `m` for elimination. Then, we call the `josephus` function to calculate the position of the last person remaining and print the result.

Note that we assume people's positions start from 1, while array indices start from 0. Therefore, when printing the position of the last person remaining, we need to add 1.

Using dynamic programming provides an efficient solution to the Josephus problem, avoiding the repetitive calculations of recursion and improving code performance.


A description, analysis and solution for joseph circle problem.

Joseph Circle Problem


In Fibonacci's work _The Book of Calculation_ the Fibonacci sequence is defined as follows:

$$
F_n = \begin{cases}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F_{n-1} + F_{n-2} & \text{if } n \geq 2
\end{cases}
$$

It can be proven that its closed-form formula is:

$$
F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)
$$

With my current knowledge, I can only comprehend two proof methods as follows:

## Matrix Method

Let's first discuss the case when $n \geq 2$. Our goal now is to transform the recurrence formula of the Fibonacci sequence into matrix form. How can we do that? We can approach it from the perspective of a system of linear equations.

First, here is what we know:

$$
F_{n-1} + F_{n-2} = F_{n}
$$

We can add the equation $F_{n-1} + 0 \cdot F_{n-2} = F_{n-1}$ to form a system of linear equations:

$$
\begin{cases}
F_{n-1} + F_{n-2} = F_{n} \\
F_{n-1} + 0 \cdot F_{n-2} = F_{n-1}
\end{cases}
$$

This can be transformed into matrix form as follows:

$$
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F_{n-1} \\
F_{n-2}
\end{bmatrix}
=
\begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix}
$$

Now, we can iterate this process:

$$
\begin{align}
\begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix}
&=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F_{n-1} \\
F_{n-2}
\end{bmatrix} \\
&=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^2
\begin{bmatrix}
F_{n-2} \\
F_{n-3}
\end{bmatrix} \\
&=\cdots \\
&=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{n-1}
\begin{bmatrix}
F_{1} \\
F_{0}
\end{bmatrix}
\end{align}
$$

We denote the matrix $\boldsymbol{A} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}$. So, the problem becomes finding $\boldsymbol{A}^{n-1}$, and then we can calculate $\boldsymbol{A}^{n}$ and replace all instances of $n$ with $n-1$.

Notice that matrix $\boldsymbol{A}$ is a square matrix, and we can utilize the eigenvalues and eigenvectors of matrices.

Eigenvectors can be understood as vectors that, when right-multiplied by the matrix, result in a vector parallel to themselves. Eigenvalues are the scaling factors by which the eigenvectors are scaled when right-multiplied by the matrix. In other words:

$$
\boldsymbol{A}\boldsymbol{x} = \lambda\boldsymbol{x}\tag{1}
$$

Here, $\lambda$ is the eigenvalue, and the non-zero vector $\boldsymbol{x} \in \mathbb{R}^n$ (where $n$ is the order of the square matrix) is the eigenvector corresponding to the eigenvalue $\lambda$ of matrix $\boldsymbol{A}$.

So, the specific approach is to first find the eigenvalues $\lambda_1$ and $\lambda_2$ (usually, an $n$-order matrix has $n$ eigenvalues) and obtain the diagonal matrix $\rm{diag}\{\lambda_1, \lambda_2\}$. Then, we find an invertible matrix $\boldsymbol{P}$ such that:

$$
\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} = \rm{diag}\{\lambda_1, \lambda_2\}
$$

Using matrix multiplication properties:

$$
(\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P})^n = \boldsymbol{P}^{-1}\boldsymbol{A}(\boldsymbol{P}\boldsymbol{P}^{-1})\boldsymbol{A}(\boldsymbol{P}\cdots\boldsymbol{P}^{-1})\boldsymbol{A}\boldsymbol{P} = \boldsymbol{P}^{-1}\boldsymbol{A}^n\boldsymbol{P}\tag{2}
$$

This allows us to calculate $\boldsymbol{A}^{n}$.

Let's first find the eigenvalues. We can rewrite equation $(1)$ as:

$$
(\boldsymbol{A}-\lambda\boldsymbol{E})\boldsymbol{x} = \boldsymbol{0}\tag{3}
$$

Here, $\boldsymbol{E}$ is the identity matrix, and we can compute that $\boldsymbol{A}-\lambda\boldsymbol{E} = \begin{bmatrix}
1-\lambda & 1 \\
1 & -\lambda
\end{bmatrix}$. To ensure that there is a non-zero solution, we solve for:

$$
\left| \boldsymbol{A}-\lambda\boldsymbol{E} \right| = \begin{vmatrix}
1-\lambda & 1 \\
1 & -\lambda
\end{vmatrix} = \lambda^2 - \lambda - 1 = 0
$$

Solving this equation, we obtain $\lambda_1 = \frac{1+\sqrt{5}}{2}$ and $\lambda_2 = \frac{1-\sqrt{5}}{2}$.

Therefore, the diagonal matrix is:

$$
\rm{diag}\{\lambda_1, \lambda_2\} = \begin{bmatrix}
\frac{1+\sqrt{5}}{2} & 0 \\
0 & \frac{1-\sqrt{5}}{2}
\end{bmatrix}
$$

Assuming the eigenvector is $\boldsymbol{x} = \begin{bmatrix}
x & y
\end{bmatrix}^T$, we can substitute $\lambda_1$ and $\lambda_2$ into equation $(2)$ to obtain two systems of equations:

$$
\begin{cases}
(1-\lambda_1)x + y = 0 \\
x - \lambda_1y = 0
\end{cases},
\begin{cases}
(1-\lambda_2)x + y = 0 \\
x - \lambda_2y = 0
\end{cases}
$$

Setting $y = 1$ in both systems of equations gives us the two eigenvectors of the matrix:

$$
\boldsymbol{x}_1 = \begin{bmatrix}
\frac{1+\sqrt{5}}{2} & 1
\end{bmatrix}^T,
\boldsymbol{x}_2 = \begin{bmatrix}
\frac{1-\sqrt{5}}{2} & 1
\end{bmatrix}^T
$$

So, the invertible matrix $\boldsymbol{P}$ is formed by these two eigenvectors:

$$
\boldsymbol{P} = \begin{bmatrix}
\frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\
1 & 1
\end{bmatrix}
$$

Why is it like this? Let $\boldsymbol{P} = \begin{bmatrix}
x_1 & x_2 \\
y_1 & y_2
\end{bmatrix}$ (where $x_1, y_1, x_2, y_2$ are the components of eigenvectors $\boldsymbol{x}_1, \boldsymbol{x}_2$ respectively).

Now, if we calculate $\boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\}$, it exactly equals $\begin{bmatrix}
\lambda_1x_1 & \lambda_2x_2 \\
\lambda_1y_1 & \lambda_2y_2
\end{bmatrix}$. This means that $\boldsymbol{A}\boldsymbol{P} = \boldsymbol{P}\rm{diag}\{\lambda_1, \lambda_2\}$ is inevitable. Left-multiplying by $\boldsymbol{P}^{-1}$, we get $\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P} = \rm{diag}\{\lambda_1, \lambda_2\}$. So, $\boldsymbol{P} = \begin{bmatrix}
x_1 & x_2 \\
y_1 & y_2
\end{bmatrix}$ is reasonable.

Its inverse matrix is easy to calculate:

$$
\boldsymbol{P}^{-1} = \frac{\boldsymbol{P}^*}{\left|\boldsymbol{P}\right|} = \frac{1}{\sqrt{5}}\begin{bmatrix}
1 & \frac{1-\sqrt{5}}{2} \\
1 & \frac{1+\sqrt{5}}{2}
\end{bmatrix}
$$

Substituting into equation $(2)$:

$$
\boldsymbol{A}^n = \boldsymbol{P}(\boldsymbol{P}^{-1}\boldsymbol{A}\boldsymbol{P})^n\boldsymbol{P}^{-1} = \boldsymbol{P}\rm{diag}^n\{\lambda_1, \lambda_2\}\boldsymbol{P}^{-1}
$$

Where the diagonal matrix is:

$$
\rm{diag}^n\{\lambda_1, \lambda_2\} = \begin{bmatrix}
\left(\frac{1+\sqrt{5}}{2}\right)^n & 0 \\
0 & \left(\frac{1-\sqrt{5}}{2}\right)^n
\end{bmatrix}
$$

Therefore,

$$
\boldsymbol{A}^n = \frac{1}{\sqrt{5}}\begin{bmatrix}
\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} & \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}\left(\frac{1-\sqrt{5}}{2}\right) + \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\left(\frac{1+\sqrt{5}}{2}\right) \\
\left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{1-\sqrt{5}}{2}\right)^n & \left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{1-\sqrt{5}}{2}\right) + \left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{1+\sqrt{5}}{2}\right)
\end{bmatrix}
$$

Then,

$$
\begin{bmatrix}
F_{n} \\
F_{n-1}
\end{bmatrix}
= \boldsymbol{A}^{n-1}
\begin{bmatrix}
F_1 \\
F_0
\end{bmatrix}
= \frac{1}{\sqrt{5}}\begin{bmatrix}
\left(\frac{1+\sqrt{5}}{2}\right)^{n} + \left(\frac{1-\sqrt{5}}{2}\right)^{n} \\
\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} + \left(\frac{1-\sqrt{5}}{2}\right)^{n-1}
\end{bmatrix}
$$

Considering only the first row of the matrices on both sides of the equation, we obtain the closed-form formula for the Fibonacci sequence:

$$
F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)
$$

Substituting $n=0$ and $n=1$ to verify, we find that they both satisfy the equation.

---

## Difference Equation Method

Defining the difference of a sequence $\{a_n\}$ as $\Delta a_n = a_{n+1} - a_n$ (using backward difference here), we can define the second-order difference as:

$$
\Delta^2 a_n = \Delta a_{n+1} - \Delta a_n = a_{n+2} - 2a_{n+1} + a_n
$$

Further, we can define the $m$-th order difference:

$$
\Delta^m a_n = \Delta^{m-1} a_{n+1} - \Delta^{m-1} a_n = \sum_{i=0}^{m} (-1)^i C_m^i a_{n+m-i}
$$

And

$$
F(a_n, \Delta a_n,
\Delta a_n, \Delta^2 a_n, \Delta^3 a_n, \ldots)
$$

The Fibonacci sequence, defined as $F_n = F_{n-1} + F_{n-2}$, has a second-order difference that is constant:

$$
\Delta^2 F_n = F_{n+2} - 2F_{n+1} + F_n = F_{n+1} + F_{n+1} - 2F_{n+1} + F_n = F_{n+1} - F_n = F_n
$$

Now, we can write the second-order linear homogeneous difference equation for $F_n$:

$$
\Delta^2 F_n - F_n = 0
$$

This is a characteristic equation, and we can solve it by assuming $F_n = r^n$:

$$
r^2 - 1 = 0
$$

Solving this equation gives us two solutions: $r = 1$ and $r = -1$. Therefore, the general solution for the homogeneous difference equation is:

$$
F_n = c_1 \cdot 1^n + c_2 \cdot (-1)^n
$$

Now, we need initial conditions to find the particular solution. We know that $F_0 = 0$ and $F_1 = 1$. Substituting these into the general solution:

$$
\begin{align*}
F_0 &= c_1 \cdot 1^0 + c_2 \cdot (-1)^0 = c_1 + c_2 = 0 \\
F_1 &= c_1 \cdot 1^1 + c_2 \cdot (-1)^1 = c_1 - c_2 = 1
\end{align*}
$$

Solving this system of equations, we find $c_1 = \frac{1}{2}$ and $c_2 = -\frac{1}{2}$. Therefore, the particular solution for the Fibonacci sequence is:

$$
F_n = \frac{1}{2} \cdot 1^n - \frac{1}{2} \cdot (-1)^n
$$

This can be simplified further by noting that $(-1)^n$ is equal to $(-1)^{n-1} \cdot (-1) = -(-1)^{n-1}$:

$$
F_n = \frac{1}{2} - \frac{1}{2} \cdot (-1)^{n-1}
$$

This is indeed the closed-form formula for the Fibonacci sequence:

$$
F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)
$$

So, we have successfully derived the same result using the difference equation method.

In summary, both the matrix method and the difference equation method lead to the same closed-form expression for the Fibonacci sequence, demonstrating the beauty of mathematics in providing multiple ways to arrive at a solution.


This article gives two methods to derive Fibonacci sequence: matrix method and difference equation method

Use Differential Equation Method and Matrix Method to Find Fibonacci Sequence General Formula


## Problem Description

This article presents an algorithm for the problem of selecting combinations of elements $C(n, m)$.

> Given a set $\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$ of size $n$ where $n>0$, extract $m$ elements $(0<m\leq n)$ as a combination and output all possible combination schemes.

## Model Establishment

According to the combination formula, the number of ways to select $n$ elements from a set of $m$ elements is given by $\left( \begin{array}{c} 	n\\ 	m\\ \end{array} \right) =\frac{P_{n}^{m}}{P_m}=\frac{n!}{m!\left( n-m \right) !}$.

For a set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, an auxiliary marking sequence $A=\left[ 1,1,1,...,0,0,0 \right]$ is established to indicate whether the corresponding elements are included in the combination: $A[i]=1$ indicates that element $a_{i}$ is included in the combination, where $A[i]=0$ indicates that element $a_{i}$ is not included in the combination.

**For example**, for the set $S=\left\{ a_{1},a_{2},a_{3},a_{4} \right\}$ and the combination $C(4,2)$, all possible combinations are $\left\{ a_{1},a_{2} \right\}$, $\left\{ a_{1},a_{3} \right\}$, $\left\{ a_{1},a_{4} \right\}$, $\left\{ a_{2},a_{3} \right\}$, $\left\{ a_{2},a_{4} \right\}$, $\left\{ a_{3},a_{4} \right\}$. The corresponding auxiliary marking sequences are $\left\{ a_{1},a_{2} \right\}\rightarrow\left[ 1,1,0,0 \right]$, $\left\{ a_{1},a_{3} \right\}\rightarrow\left[ 1,0,1,0 \right]$, $\left\{ a_{1},a_{4} \right\}\rightarrow\left[ 1,0,0,1 \right]$, $\left\{ a_{2},a_{3} \right\}\rightarrow\left[ 0,1,1,0 \right]$, $\left\{ a_{2},a_{4} \right\}\rightarrow\left[ 0,1,0,1 \right]$, $\left\{ a_{3},a_{4} \right\}\rightarrow\left[ 0,0,1,1 \right]$.

The content expressed by the auxiliary marking sequence is the elements corresponding to the items marked as $1$ in the sequence, selected in the set and included in the combination. This auxiliary sequence facilitates the computation of combinations.

## Auxiliary Sequence Transformation

The concept of the auxiliary marking sequence has been introduced above. Now, two special auxiliary marking sequences are defined.

**Definition** $A(S)$ represents the **initial state auxiliary marking sequence** for the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, denoted as $A(S)=\left[ a_{1},a_{2},...,a_{n},a_{n+1},a_{n+2},...,a_{m} \right]$, where $a_{i}=1(0<i\leq n)$ and $a_{j}=0(n+1 \leq j\leq m)$. It can be considered as the first combination method among all combination methods for the combination problem.

> **Example** The sequence $A=[1,1,1,1,0,0,0,0,0]$ is the initial state.

The initial state auxiliary marking sequence has been introduced above. Now, the **terminal state auxiliary marking sequence** is introduced.

**Definition** For the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, the auxiliary marking sequence $A=[a_{1},a_{2},...,a_{n-m},...,a_{m}]$ is defined, where $a_{i}=0(0<i\leq n-m)$ and $a_{j}=1(n-m<j\leq m)$. This sequence is called the **terminal state auxiliary marking sequence** of this set.

> **Example** The sequence $A=[0,0,0,0,1,1,1,1,1]$ is the terminal state.

**Definition** The operation function $Countf(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as the number of elements satisfying $a_{j}=1(0<j< i)$ in the subsequence $A=\left[ a_{1},a_{2},...,a_{i} \right]$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Countf(A,i)$ for $i=7$. Since before $A[7]$ (excluding $A[7]$), there are a total of $3$ elements $1$ at $A[1]$, $A[4]$, and $A[6]$, so the value of $Countf(A,i)$ for $i=7$ is $3$.

**Definition** The operation function $Exch(A)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: find the smallest index $i$ satisfying $a_{i}=1$ and $a_{i+1}=0$, where $0<i\leq m-1$. Then exchange their values, i.e., set $a_{i}=0$ and $a_{i+1}=1$, obtaining the new sequence $A'$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Exch(A)$. Obviously, find the minimum $i=1$, and get $a_{1}=1,a_{2}=0$. Swap them to get the new sequence $A'=Exch(A)=\left[ 0,1,0,1,0,1,1,1 \right]$

**Definition** The operation function $Movb(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: let $p=Countf(A,i)$ and $q=i-p-1$. Transform $A$ to get the new sequence $A'=[a_{1},a_{2},...,a_{p},a_{p+1},...,a_{i-1},a_{i},...,a_{m}]$, where $a_{i}=1(1<i\leq p)$ and $a_{j}=0(p<j<i)$.

> **Example** If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Movb(A,i)$ for $i=5$. The new sequence is $A'=Movb(A,5)=\left[ 1,1,0,0,0,1,1,1 \right]$.

**Definition** Based on the auxiliary marking sequence $A$, output a combination scheme for the set $S$, called a restoration for sequence $A$. Denoted as $C(A)=\left\{ a_{i}\in S|A[i]=1 ,0<i\leq m \right\}$.

> **Example** For the set $S=\left\{ a_{1},a_{2},a_{3},a_{4},a_{5},a_{6} \right\}$ and the sequence $A=[1,1,0,0,1,0]$, a restoration for $S$ with respect to $A$ is $\left\{ a_{1},a_{2},a_{5} \right\}$.

## Algorithm Method

- Step 1: Obtain $A=A(S)$ from the set $S$, i.e., the initial state auxiliary marking sequence.
- Step 2: Output $C(A)$.
- Step 3: Check if the obtained auxiliary marking sequence is in the terminal state. If yes, terminate. If no, proceed to the next step.
- Step 4: Perform the transformation $A=Exch(Movb(A))$, and go back to Step 2.

With the above method, all combination schemes for the combination problem of selecting $C(n,m)$ elements from the set $S$ can be output.


This article presents an algorithm for the problem of selecting combinations of elements.

Problem: Element Combination Using Marking Method

When we compile some cross -platform programs, we will inevitably encounter _win32 __linux__ what is the macro of the compiler or the compiler environment.It indicates some information of the current platform environment to the compiler.

C/C++ Cross-Platform Compile-Macros


蓋聞聖人以四海為家，英宰與千齡合契。用能不行而至，春霆仗天地之威；以息相吹，時雨鬱山川之兆。故有元蛟晚集，憑鶴鼎而先鳴；蒼兕晨驚，運龍韜而首出。並能風騰霧躍，指麾成烈士之功；蠖屈虯奔，談笑坐群卿之右。未如越蒼海，棄行間，排紫微，謁天子。於是遭不諱之主，擁非常之位。龍章鳳黻照其前，鏘金鳴玉疊其後。三靈葉讚，超然奉天下之圖；四海承平，高步取寰中之託。君侯之富貴足矣，聖朝之付遇深矣。

故知陽侯息浪，長鯨臥橫海之鱗；風伯停機，大鵬鎩垂天之翼。及其投形巨壑，觸丹浦而雷奔；假勢靈飆，指青霄而電擊。神氣洋洋，謂鱗翮使之然也。殊不知兩儀超忽，動止係於無垠；萬化糾紛，舒捲存乎非我。是以陳平昔之智士也，俯同降卒；百里奚曩之達人也，親為餓隸。當其背強敵，轉康衢，雄慮耿於風雲，危途迫於朝夕，豈自期榮稱相府，西藩開虎據之圖；寵冠齋壇，東向舉能飛之策？顧盼可以蕩川嶽，咄嗟可以降雷雨。遂令用與不用，是非於楚漢之間；知與不知，得失於虞秦之際。故曰：死生有數，審窮達者係於天；材運相符，決行藏者定於已。君侯足下可不謂然乎？

借如勃者，眇小之一書生耳，曾無擊鍾鼎食之榮，非有南鄰北閣之援。山野悖其心跡，煙霧養其神爽。未嚐降身摧氣，逡巡於列相之門；竊譽幹時，匍匐於群公之室。所以慷慨於君侯者，有氣存乎心耳。實以四海兄弟，齊遠契於蕭、韓；千載風雲，托神知於管、鮑。不然，則荷裳桂楫，拂衣於東海之東；菌閣鬆楹，高枕於北山之北。焉複區區屑屑，踐名利之門哉？

至尊以搖河徙嶽之威，當立地開天之運。聖人有作，群材畢舉。星辰入仕，揖讓朱鳥之門；風雨稱臣，奔走蒼龍之闕。方欲停旒金室，引成康於已往；辟纊瑤林，複堯舜於茲日，可謂明明穆穆，盡天子之容貌矣。

抑嚐聞之：丹山九仞，煙峰非數簣之功；紫極千門，雲台俟萬楹之力。故天下至曠，神器不可獨專；天道無私，元勳有待而立。《書》曰：「元首明哉！股肱良哉！」好問則裕，自用則小。況掌萬國之權，受一人之寵，動見臧否，言知利害。君侯足下何時易耶？雖國有大命，不資童子之言；而恭此小心，敢進狂夫之說？伏見遼陽未靖，大軍頻進，有識寒心，群黎破膽。昔明王之制國也，自近而及遠，先仁而後罰，徵實則郊存，徇名則功淺。是以農疏十野，僅逾重石之鄉；禹截九州，不敘流沙之境。豈才不及而智有遺哉？將以辨離方而存正功也。雖至人無外，甲兵曜天子之威；王事有徵，金鼓發將軍之氣。而長城在界，秦漢所以失全昌；巨海橫流，天地所以限殊俗。闢土數千里，無益神封；勒兵十八萬，空疲帝卒。驚烽走傳，駭秦洛之；飛芻免粟，竭淮海之費。於是乘奸放命者出繩纆以生威。因公挾私者入閭閻而競法。雖一物失所，太階延旰食之憂；而百戰方雄，中國鮮終年之樂。圖得而不圖失，知利而不知害。移手足之病，成心腹之疾。征稅屈於東西，威信蹇於表裏。語曰：「勝之不武，不勝為辱，天下之責，四面至矣。」誠可遠凝高策，上薦忠言，決人事於去就，合天情於終始。遂令回麾轉檄，背青邱而騖；列障分亭，巡蒼波而守。昔者齊侯以力，方城為楚國之辭；虞帝崇文，苗人失洞庭之險。況乎仗德綏亂，以直乘邪，明逆順之端，聳華夷之望，雖複舳艫沸海，旌旗觸天，鐵山四面，金城千里，亦不能為敵人計矣。此君侯之未諭一也。

蓋聞星回日運，禦洪荒者貞夫一；電照風行，制寥廓者歸乎靜。《易》曰：「複其見天地之心乎？」語曰：「動之斯和，綏之斯來。」是知源潔則流清，形端則影直，大道起而仁義息，神化周而市獄定。雖複體元立教，眚災耀知遠之書；順時宰物，宥罪發精微之典。而況澆風易漸，淳化難歸？孔明耿介於當朝，子輿殷勤於易簀，蓋有由也。伏見邊凶尚梗，殊恩屢發，亡命山澤者，日月相趨，朝脫桎梏，夕還囹圄。奸徒抱袂因時立僥幸之謀；頑夫頓足，中路紆籲嗟之慘。皆由寬勝於猛，人迷所習，勸沮不彰，廉恥相冒。亦有公卿失職，恥受珪符之任；郎宮有釁，俯舍銅墨之榮。又焉可以宏長風流，抑揚眾務者也？且夫朽索充羈，不收奔馬之逸；輕緡振網，或隨吞舟之勢。況非常之化，方洽於齊人；無妄之恩，乃及於群小。將恐匡衡、管仲，複靈詔於下泉矣。古之善為國者不然。信賞而必罰，道德而齊禮，澤配風雨而無曲惠，威振雷霆而絕私戮。交書聳幣，伏慈厚之師；投金散璧，樹仁明之長。故雖開衢室，蓋明堂，亦將四三皇而六五帝矣，此君侯之未諭二也。

蓋《易》曰：「天地之大德曰生，聖人之大寶曰位，何以守位曰仁，何以聚人曰財。」是知發揮地利，農桑啟其業；振蕩天功，泉貝流其用。伏睹前制屢擾，事非畫一，廛市蕭然，人情怪動，夫煩簡並用，未盡交易之宜；輕重齊行，適啟兼並之路。於是連闤掩闠者，閉肆而乘其屈；布衣韋帶者，闔門而受其困。五方競爽，務淺術以相雄；百郡爭勝，驅末技而成弊。田夫織婦，衣食鮮終朝之給；巨駔洪商。輿馬挾封君之勢，蓋有由來矣。故曰國儲闕於九載，則公上無所給；家廩乏於三年，則妻子非其有。夫陰陽覆逆，天地之常數；百六運窮，湯堯所不免。一旦洪泉決地，大旱焦山，風雨於一歲之間，霜雹於數州之境。繁運廣役，首尾於中外；遝稅增徭，日夕們都鄙。燮陰陽者，將何以處之？一夫竊議，公之盛德虧矣。愚謂嚴程峻法，絕輕陋之貨，則奸鎔之源塞矣。沿風正典，重耕耘之務，則邪贏之計沮矣。然後遠宏教旨，大變流俗，法立有犯而必施，令出唯行而不返。違公竊鑄者，具五刑之戮；因時力田者，懸一命之賞。不然，則賈生、晃錯，複流涕而言矣，此君侯之未諭三也。

嵩衡不拒細壤，故能崇其峻；江海不讓纖流，所以存其廣。是以星台曉辟，上台忘吐握之勞；月殿宵興，中宇軫山林之慕。知夫禦天下者，必待人也。《詩》曰：「濟濟多士，文王以寧。未見君子，憂心如醉。」伏見皇明遠燭，帝采遐宣，張樂岱郊，騰勳社首。徵廉察孝，瑤壇虛不次之階；署行議年，璿檢動非常之詔。天下可謂幸甚矣。於是友月朋霞之客，背青皋而至；馮唐顏駟之才，排紫閣而集。夫豈知終始異數，涇渭同流，蘿薜失圖，簪纓解體？惜哉！群英霧散，名侯招蔽善之嫌；天下雷同，君子鮮長鳴之地。而欲招絕足，致真龍，難矣！此君侯之未諭四也。

《易》曰：「拔茅連茹，以其彙征吉。」豈非順物不若招類，報國不如進賢。陽事昇而雨露歸，陰駕凝而風霜厲。莫不觀時有記，撫氣相求。窮則獨善其私，達則兼善天下。而利已疵物者，以自任為身謀；知進忘退者，謂專榮而得計。豈知夫尺波易謝，寸晷難留？陵穀好遷，乾坤忌滿？君侯足下出納王命，升降天衢，激揚鳳扆之前，趨步麟台之上，亦複知天下有遺俊乎？夫心之精微，口不能言也；言之微妙，書不能文也。伏願辟東閣，開北堂，待之以上賓，期之以國士，使得披肝膽，布腹心，大論古今之利害，高談帝王之綱紀。然後鷹揚豹變，出蓬戶而拜青墀；附景摶風，舍苔衣而見絳闕。幸甚！斯不為難矣。庶幾乎麑卵不棄，終感元枵之精；駿骨時收，或致飛黃之錫。書生王勃死罪死罪再拜。


蓋聞聖人以四海為家，英宰與千齡合契。用能不行而至，春霆仗天地之威；以息相吹，時雨鬱山川之兆。故有元蛟晚集，憑鶴鼎而先鳴；蒼兕晨驚，運龍韜而首出。並能風騰霧躍，指麾成烈士之功。

原点日志

ALL POSTS