# Euler Project 14

## linked list
1. 在 collatzLength 函式中，使用 while 迴圈來計算 Collatz 數列的長度。迴圈的條件是當 n 不等於 1 時繼續執行。

2. 在迴圈內部，首先檢查是否已經計算過數字 n 的 Collatz 數列長度。如果 n < LIMIT 且 lens[n] 不是 NULL，則表示已經計算過，我們可以使用儲存在 lens[n] 的節點值來更新目前的長度 len。並減去 1 以獲得正確的長度。

3. 如果 lens[n] 是 NULL 或 n >= LIMIT，表示我們還未計算過該數字的 Collatz 數列長度。在這種情況下，我們根據 Collatz 數列的規則更新 n 的值並將 len 的計數增加 1。

#define LIMIT 1000000

int collatzLength(long n, Node** lens) {
    int len = 1;

    while (n != 1) {
        if (n < LIMIT && lens[n] != NULL) {
            len += lens[n]->value - 1;
            break;
        }

        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;

        len++;
    }

    return len;
}

4. 程式碼中的 freeLinkedList 函式，用於釋放連結串列所佔用的記憶體。使用迴圈遍歷串列並釋放每個節點。

void freeLinkedList(Node* head) {
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
}

5. 在 main 函式中，使用 malloc 分配一個 Node* 指標的陣列，大小為 LIMIT。然後，使用迴圈將每個指標初始化為 NULL。

Node** lens = (Node**)malloc(LIMIT * sizeof(Node*));
    for (int i = 0; i < LIMIT; ++i)
        lens[i] = NULL;

6. 為數字 1 創建一個節點。在 lens[1] 中使用 malloc 分配一個新的 Node，並將 value 設置為 1，表示數字 1 的 Collatz 數列長度。next 指標設置為 NULL。

lens[1] = (Node*)malloc(sizeof(Node));
lens[1]->value = 1;
lens[1]->next = NULL;

7. 在主迴圈中，我們使用迴圈從 2 開始遍歷到 LIMIT - 1。對於每個數字 i，我們調用 collatzLength 函式來計算 Collatz 數列的長度。

8. 如果計算得到的長度 len 大於目前的最大長度 maxlen，則更新 maxlen 和 maxi 的值。

9. 在計算完 Collatz 數列長度後，我們檢查 i 是否小於 LIMIT，如果是的話，則使用 malloc 分配一個新的節點並將其添加到 lens 陣列的相應位置。

int maxi = 1, maxlen = 1;

for (int i = 2; i < LIMIT; ++i) {
    int len = collatzLength(i, lens);

    if (len > maxlen) {
        maxlen = len;
        maxi = i;
    }

    if (i < LIMIT) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->value = len;
        newNode->next = NULL;
        lens[i] = newNode;
    }
}

10. 最後，我們使用迴圈遍歷 lens 陣列，釋放每個數字的連結串列所佔用的記憶體。然後，使用 free 釋放 lens 陣列本身所佔用的記憶體。

for (int i = 1; i < LIMIT; ++i)
        freeLinkedList(lens[i]);
    free(lens);

### 為甚麼要開兩層指標?
在程式碼中使用兩層指標 Node** lens 是為了在 collatzLength 函式中能夠修改 lens 陣列中的節點指標。

原始的 lens 陣列是一個 Node* 指標的陣列，每個指標指向一個連結串列的節點。當我們在 collatzLength 函式中計算 Collatz 數列的長度時，需要能夠存取和修改這個連結串列。然而，如果只使用單層指標，則在函式內部修改 lens 陣列中的指標只會影響到函式內部的複本，不會影響到 main 函式中的 lens 陣列。

因此，我們使用兩層指標 Node** lens，其中第一層指標 Node** 指向 lens 陣列本身，第二層指標 Node* 指向連結串列的節點。這樣，在 collatzLength 函式中修改 lens 陣列的指標時，可以直接影響到 main 函式中的 lens 陣列。

總結而言，使用兩層指標 Node** lens 可以在 collatzLength 函式中修改 lens 陣列的內容，以便儲存每個數字的 Collatz 數列的長度。這樣就能夠在主函式中使用這些資訊，進一步處理和顯示結果。
## 最終成果

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    long value;
    struct Node* next;
} Node;

#define LIMIT 1000000

int collatzLength(long n, Node** lens) {
    int len = 1;

    while (n != 1) {
        if (n < LIMIT && lens[n] != NULL) {
            len += lens[n]->value - 1;
            break;
        }

        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;

        len++;
    }

    return len;
}

void freeLinkedList(Node* head) {
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    Node** lens = (Node**)malloc(LIMIT * sizeof(Node*));
    for (int i = 0; i < LIMIT; ++i)
        lens[i] = NULL;

    lens[1] = (Node*)malloc(sizeof(Node));
    lens[1]->value = 1;
    lens[1]->next = NULL;

    int maxi = 1, maxlen = 1;

    for (int i = 2; i < LIMIT; ++i) {
        int len = collatzLength(i, lens);

        if (len > maxlen) {
            maxlen = len;
            maxi = i;
        }

        if (i < LIMIT) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            newNode->value = len;
            newNode->next = NULL;
            lens[i] = newNode;
        }
    }

    printf("%d: %d\n", maxi, maxlen);

    for (int i = 1; i < LIMIT; ++i)
        freeLinkedList(lens[i]);
    free(lens);

    return 0;
}

## 遞迴版
1. collatzLength 函式用於計算給定數字的考拉茲序列長度。它接受一個數字 n 和一個保存已計算長度的陣列 lens，並回傳數字 n 的序列長度。

int collatzLength(long n, int* lens)

2. 如果 n 的值為 1，表示序列已結束，因此回傳長度 1。

3. 如果 n 的值小於 LIMIT（1000000）並且 lens[n] 不為 0，表示我們之前已計算過數字 n 的序列長度，可以直接從陣列 lens 中取得並返回。

if (n == 1)
    return 1;
if (n < LIMIT && lens[n] != 0)
    return lens[n];

4. 如果以上條件不滿足，我們需要根據考拉茲猜想的規則計算序列長度。根據規則：

如果 n 是偶數，則將其除以 2
如果 n 是奇數，則將其乘以 3 並加 1
遞迴調用 collatzLength 函式，傳入新的數字並累加 1。

if (n % 2 == 0)
    len = collatzLength(n / 2, lens) + 1;
else
    len = collatzLength(n * 3 + 1, lens) + 1;

5. 如果 n 小於 LIMIT，我們將計算出的長度存儲在 lens 陣列中。

if (n < LIMIT)
    lens[n] = len;

## 最終成果

#include <stdio.h>

#define LIMIT 1000000

int collatzLength(long n, int* lens) {
    if (n == 1)
        return 1;
    if (n < LIMIT && lens[n] != 0)
        return lens[n];

    int len = 1;
    
    if (n % 2 == 0)
        len = collatzLength(n / 2, lens) + 1;
    else
        len = collatzLength(n * 3 + 1, lens) + 1;

    if (n < LIMIT)
        lens[n] = len;
    
    return len;
}

int main() {
    int lens[LIMIT] = {0}; // 初始化0
    
    lens[1] = 1; // 1的長度就是1

    int maxi = 1, maxlen = 1; // 初始化

    for (int i = 2; i < LIMIT; ++i) {
        int len = collatzLength(i, lens);

        if (len > maxlen) {
            maxlen = len;
            maxi = i;
        }
    }

    printf("%d: %d\n", maxi, maxlen);
    return 0;
}

## 時間複雜度:
時間複雜度大概為 O(n log n)，其中 n 是 LIMIT 的值，也就是 1000000。