cpp基础入门学习快快排、指针、函数、递归、费波拉且数列、剪枝

当使用指针时，我们实际上是在操作内存地址。指针是一个变量，它存储了内存中某个对象的地址。通过指针，我们可以直接访问该地址处的对象。

在快速排序算法中，我们使用指针来操作数组。例如， int *arr 中的 arr 是一个指向整型数据的指针。我们可以使用指针来访问和修改数组中的元素，而无需使用数组索引。

在快速排序算法中，我们通过将数组分为两个部分来实现排序。这里的 "低位" 和 "高位" 是指数组中的索引位置。

"低位" 表示的是当前子数组的最低（最左）索引。在代码中，我们使用 low 变量来表示。初始情况下，它指向要排序的子数组的第一个元素。

"高位" 表示的是当前子数组的最高（最右）索引。在代码中，我们使用 high 变量来表示。初始情况下，它指向要排序的子数组的最后一个元素。

通过指定一个基准值，并根据这个基准值将数组的元素移动到基准值的左边或右边，我们可以将数组分成两个部分。然后，我们递归地对每个部分执行相同的操作，直到整个数组有序。

因此，在算法的每一次递归调用中，我们通过更新 "低位" 和 "高位" 来处理不同的子数组，从而实现了排序。每次递归调用都会将子数组分割成更小的部分，直到排序完成。

8.这行代码执行的是将找到的小于基准值的元素移到低位，并将 first 指针向后移动的操作。

让我们逐步解释这行代码的执行过程：

1. if (first < last)：这个条件判断语句检查 first 指针是否小于 last 指针。只有当此条件为真时，即 first 指针确实小于 last 指针时，才会执行接下来的操作。

2. arr[first++] = arr[last]：这行代码将 arr[last] 的值赋给 arr[first]。也就是说，将高位 last 指向的元素的值复制到低位 first 指向的位置。

   • 注意：first++ 表示先将 arr[first] 的值赋给 arr[last]，然后再将 first 指针向后移动一位。这样可以保持在每一次赋值操作之后，first 指针指向的是下一个空槽位，用于下一轮的赋值操作。

   例如，假设原始数组是 [5, 2, 7, 3, 9]，而当前 first 指向索引为 0 的元素（值为 5），last 指向索引为 3 的元素（值为 3）。那么这行代码执行后的结果是 [3, 2, 7, 3, 9]。同时， first 指针向后移动一位，指向了索引为 1 的位置。

因此，这行代码的作用是将找到的小于基准值的元素移到低位，并将 first 指针向后移动，确保下一次迭代时正确处理剩余的子数组。

递归是一种算法或函数调用自身的方式。在计算机科学中，通过递归可以解决那些可以被分解成较小的、相同问题形式的问题。

递归算法通常包含两个部分：基本情况和递归调用。

1. 基本情况：基本情况是指可以直接处理的最简单的情况。当满足基本情况时，递归不再继续执行，而是返回一个特定的结果。这个结果可以是某个值、空值或者其他定义的返回值。

2. 递归调用：递归调用是指在算法或函数内部，通过调用自身来处理规模更小的相同问题。通过将大问题分解成更小的子问题，递归确保问题规模逐渐减小，最终达到基本情况。每次递归调用都会向基本情况靠近一步。

递归算法的执行过程如下：

1. 检查是否满足基本情况的条件。如果满足，则返回一个特定的结果。
2. 如果不满足基本情况，就将问题分解成较小的、相同问题形式的子问题。
3. 通过递归调用自身，解决这些子问题。
4. 将子问题的结果组合起来，以解决原始问题。
5. 返回最终的结果。

需要注意的是，递归算法必须有明确的结束条件，否则可能导致无限递归，造成程序崩溃或运行时间过长。每次递归调用都应该使问题规模减少，最终能够达到基本情况。

递归在许多算法和数据结构中都有广泛应用，例如树遍历、排序算法（如快速排序和归并排序）、图算法等。使用递归可以使算法更简洁、易于理解和实现。

函数是一段可重复使用的代码块，用于执行特定的任务或操作。函数将一组输入（参数）映射到输出（返回值），并且可以在程序的不同部分被多次调用。

函数通常由以下几个组成部分：

1. 函数名：函数的标识符，用于唯一标识该函数。
2. 参数列表：函数接受的输入值，也称为参数。参数可以有零个或多个，并通过逗号分隔。函数根据参数的类型和顺序来执行特定的操作。
3. 函数体：函数的主要代码块。它包含了实现特定功能的一系列语句。
4. 返回值：函数执行完毕后返回的结果。返回值可以是任何数据类型，也可以为空（没有返回值）。

函数的优势在于代码的模块化和重用性。通过将代码分解成多个函数，每个函数只关注特定的任务，从而简化了代码的编写和维护。此外，函数还能提高代码的可读性和可测试性。

函数的基本使用流程如下：

1. 定义函数：使用特定的语法规则（根据编程语言的要求）定义函数，指定函数名称、参数列表和函数体。
2. 调用函数：在需要使用函数的地方，通过函数名和相应的参数列表调用函数。
3. 执行函数：当函数被调用时，程序会转到函数体内部，并按照定义的操作执行相应的代码。
4. 返回结果：如果函数定义了返回值，函数执行完毕后会将结果返回给调用方。
5. 继续执行：一旦函数执行完毕并返回结果，程序将继续执行调用函数的后续代码。

需要注意的是，函数可以有副作用，即对外部环境产生可观察的改变。副作用可能包括修改全局变量的值、输出信息到控制台或修改文件内容等。准确理解函数的输入和输出，以及其对外部环境的影响，对于编写正确且可预测的程序至关重要。

分治是一种算法设计技术，将一个大问题划分成若干个相同或相似的子问题，在每个子问题上独立地求解，最后将子问题的解合并得到原问题的解。

分治算法通常包括三个步骤：

1. 分解（Divide）：将原问题划分成若干个规模较小、结构与原问题相似的子问题。这一步骤可以通过递归方式实现，将问题持续分解直至达到一个可以直接解决的基本情况。

2. 解决（Conquer）：递归地解决子问题。对于足够小的子问题，可以直接求解得到结果。如果子问题规模较大，可以再次进行分解，直到达到基本情况。

3. 合并（Combine）：将子问题的解合并，得到原问题的解。合并的过程通常需要一些额外的处理来解决子问题之间的关联。

分治算法的关键思想是将原问题分解为更小的子问题，并且子问题之间应该相互独立。通过递归地求解子问题并将其合并，最终可以得到原问题的解。

分治算法在许多经典算法中得到广泛应用，例如归并排序、快速排序和二分查找等。这些算法都使用了分治的思想，通过将问题划分为更小的子问题来提高求解效率。分治算法的优势在于可以将复杂的问题简化为易于理解和解决的子问题，并且可以充分利用并行计算的能力。

然而，分治算法并不适用于所有类型的问题。在设计和应用分治算法时，需要仔细分析问题的性质和要求，以确定是否适合采用分治策略来解决。

#include <iostream>

int fibonacci(int n) {
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    std::cout << "请输入要计算的斐波那契数列项数：";
    std::cin >> n;
    
    for (int i = 0; i <= n; ++i) {
        std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
    }
    
    return 0;
}

#include <iostream>
using namespace std;

// 递归计算斐波那契数列的函数
int fibonacci(int n) {
    if (n <= 0) // 基准情况：当 n 小于等于 0 时，返回 0
        return 0;
		else if (n == 1||n==2) // 基准情况：当 n 等于 1 时，返回 1
        return 1;
    else // 递归情况：将问题拆分为子问题，并递归调用 fibonacci 函数，并返回两个子问题的和
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cin >> n;
    
    // 循环计算并输出前 n+1 项斐波那契数
    for (int i = 0; i <= n; ++i) {
        cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
    }
    
    return 0;
}

分治是一种算法设计技术，将一个大问题划分成若干个相同或相似的子问题，在每个子问题上独立地求解，最后将子问题的解合并得到原问题的解。

分治算法通常包括三个步骤：

分解（Divide）：将原问题划分成若干个规模较小、结构与原问题相似的子问题。这一步骤可以通过递归方式实现，将问题持续分解直至达到一个可以直接解决的基本情况。

解决（Conquer）：递归地解决子问题。对于足够小的子问题，可以直接求解得到结果。如果子问题规模较大，可以再次进行分解，直到达到基本情况。

合并（Combine）：将子问题的解合并，得到原问题的解。合并的过程通常需要一些额外的处理来解决子问题之间的关联。

分治算法的关键思想是将原问题分解为更小的子问题，并且子问题之间应该相互独立。通过递归地求解子问题并将其合并，最终可以得到原问题的解。

分治算法在许多经典算法中得到广泛应用，例如归并排序、快速排序和二分查找等。这些算法都使用了分治的思想，通过将问题划分为更小的子问题来提高求解效率。分治算法的优势在于可以将复杂的问题简化为易于理解和解决的子问题，并且可以充分利用并行计算的能力。

然而，分治算法并不适用于所有类型的问题。在设计和应用分治算法时，需要仔细分析问题的性质和要求，以确定是否适合采用分治策略来解决。

当输入参数 n 为 5 时，调用 fibonacci(5) 函数。

首先，判断 n 是否小于等于 0，如果不是，则进一步判断是否等于 1。在这种情况下，n 等于 5，不满足这两个条件，因此执行递归情况。

在递归情况下，我们需要计算 fibonacci(4) 和 fibonacci(3) 的值，并返回它们的和。

对于 fibonacci(4)，我们再次进行相同的判断。它不满足基准情况，因此继续执行递归情况。我们需要计算 fibonacci(3) 和 fibonacci(2) 的值，并返回它们的和。

对于 fibonacci(3)，我们再次进行相同的判断。它仍然不满足基准情况，因此继续执行递归情况。我们需要计算 fibonacci(2) 和 fibonacci(1) 的值，并返回它们的和。

对于 fibonacci(2)，它恰好满足基准情况之一，因此返回 1。

对于 fibonacci(1)，它也恰好满足基准情况之一，因此返回 1。

回到刚才的递归调用 fibonacci(3)，我们已经获得了 fibonacci(2) 和 fibonacci(1) 的值，它们分别是 1 和 1。我们将它们相加，得到结果 2，并返回。

回到调用 fibonacci(4)，我们已经获得了 fibonacci(3) 和 fibonacci(2) 的值，它们分别是 2 和 1。我们将它们相加，得到结果 3，并返回。

回到初始调用 fibonacci(5)，我们已经获得了 fibonacci(4) 和 fibonacci(3) 的值，它们分别是 3 和 2。我们将它们相加，得到最终的结果 5，并返回。

因此，fibonacci(5) 的返回值是 5。

#include <iostream>
#include <unordered_map>

// 使用 unordered_map 存储已经计算过的结果
std::unordered_map<int, int> memo;

int fibonacci(int n) {
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    
    // 在 memo 中查找是否已经计算过该值
    auto it = memo.find(n);
    if (it != memo.end()) {
        return it->second; // 返回已经计算过的结果
    }
    
    // 如果没有计算过，则进行计算，并将结果存入 memo 中
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = result;
    
    return result;
}

int main() {
    int n;
    std::cout << "请输入要计算的斐波那契数列项数：";
    std::cin >> n;
    
    for (int i = 0; i <= n; ++i) {
        std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
    }
    
    return 0;
}

以下是斐波那契数列函数的框架代码，你可以在此基础上实现剪枝或者其他优化措施：

#include <iostream>
#include <unordered_map>

// 使用 unordered_map 存储已经计算过的结果
std::unordered_map<int, int> memo;

int fibonacci(int n) {
    // 基准情况
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;

    // 在 memo 中查找是否已经计算过该值
    auto it = memo.find(n);
    if (it != memo.end()) {
        return it->second; // 返回已经计算过的结果
    }

    // 递归情况，计算并存储结果
    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = result;

    return result;
}

int main() {
    int n;
    std::cout << "请输入要计算的斐波那契数列项数：";
    std::cin >> n;

    for (int i = 0; i <= n; ++i) {
        std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
    }

    return 0;
}

这个框架代码使用了记忆化技术，避免了重复计算相同的项，提高了计算效率。你可以在此基础上进行剪枝操作或其他优化措施来进一步改进算法效率。

使用记忆化技术可以通过将已经计算过的结果存储起来，避免重复计算相同的项，从而提高算法的效率。以下是使用记忆化技术的一般步骤：

1. 创建一个数据结构（例如，哈希表、字典、数组等）来存储已经计算过的结果。这个数据结构将充当记忆存储器。

2. 在每次需要计算某个项时，首先检查该项是否已经存在于记忆存储器中。可以通过查找项的键值进行判断。

3. 如果该项已经存在于记忆存储器中，直接返回存储的结果。

4. 如果该项不存在于记忆存储器中，进行计算，并将计算得到的结果存储在记忆存储器中，以备将来使用。

下面是一个示例，演示如何使用记忆化技术计算斐波那契数列：

# 使用字典存储已经计算过的结果
memo = {}

def fibonacci(n):
    # 基准情况
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    # 检查是否已经计算过该项
    if n in memo:
        return memo[n]  # 返回已经计算过的结果

    # 计算并存储结果
    result = fibonacci(n - 1) + fibonacci(n - 2)
    memo[n] = result

    return result

n = int(input("请输入要计算的斐波那契数列项数："))
for i in range(n + 1):
    print(f"fibonacci({i}) = {fibonacci(i)}")

在上面的示例中，我们使用了一个字典 memo 来存储已经计算过的斐波那契数列项的结果。在每次计算前，我们首先检查该项是否已经存在于字典中，如果存在，则直接返回结果；否则进行计算，并将计算得到的结果存储在字典中。这样，在后续的计算中，如果需要相同的项，就可以直接通过字典中的存储结果返回，而无需重新计算。

记忆化技术可以有效避免重复计算，提高算法的效率。特别是对于递归算法，记忆化技术往往能够显著减少计算量，提升性能。

回溯是一种常见的解决组合优化问题的算法框架，它通过穷举所有可能的解，并根据问题的约束条件进行剪枝来找到最优解。下面是一个简单的回溯算法框架示例：

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& solution, vector<int>& candidates, int target) {
    // 判断当前解是否满足条件
    if (is_solution(solution, target)) {
        process_solution(solution);
        return;
    }

    // 遍历所有可能的选择
    for (int i = 0; i < candidates.size(); i++) {
        if (is_valid(candidates[i], solution)) {
            // 做出选择
            make_choice(candidates[i], solution);
            
            // 递归进入下一层决策树
            backtrack(solution, candidates, target);
            
            // 撤销选择
            undo_choice(candidates[i], solution);
        }
    }
}

int main() {
    vector<int> solution;
    vector<int> candidates;
    int target;

    // 初始化solution、candidates和target

    backtrack(solution, candidates, target);

    return 0;
}

上述代码中，backtrack函数是回溯算法的核心部分，其中的函数is_solution、process_solution、is_valid、make_choice和undo_choice需要根据具体问题进行实现。

在main函数中，首先初始化solution、candidates和target，然后调用backtrack函数开始执行回溯算法。

请注意，代码中的is_solution、process_solution、is_valid、make_choice和undo_choice函数需要根据具体问题进行定义。这些函数的功能是根据问题的要求进行判断、处理解、验证选择的有效性、执行选择和撤销选择。

通过在回溯算法中灵活运用剪枝策略，可以提高算法的效率，并找到最优解或满足特定条件的解。在实际应用中，需要根据问题的特点设计合适的剪枝策略，以达到更好的性能和结果。

在递归模型中进行剪枝，需要考虑递归结构的特殊性。以下是一般的递归剪枝步骤：

1. 确定剪枝策略：首先，需要确定剪枝的具体策略和目标，例如减少参数数量、降低计算复杂度等。

2. 定义递归剪枝函数：根据递归模型的结构，定义一个递归剪枝函数，用于遍历递归的子结构，并进行相应的剪枝操作。

3. 遍历递归结构：从根节点开始，对递归结构进行遍历，访问每个节点。在每个节点上，判断是否满足剪枝条件，如果满足则进行剪枝操作，否则继续遍历其子节点。

4. 剪枝操作：对于满足剪枝条件的节点，可以根据具体需求进行不同的剪枝操作。常见的剪枝方式包括将权重置零、删除节点、合并节点等。

5. 更新递归结构：剪枝操作后，需要更新递归结构，确保剪枝后的模型仍然保持有效的递归结构。可能需要重新连接节点、更新连接权重等。

6. 递归调用：对于非叶节点，需要递归调用剪枝函数，对其子节点进行剪枝操作。

7. 结束条件：当遍历完整个递归结构或者达到剪枝的停止条件时，剪枝过程结束。

在递归模型中进行剪枝时，需要考虑模型结构的连续性和依赖关系。因此，在设计剪枝策略和实现剪枝算法时，需要仔细考虑与递归结构相关的因素，并保证剪枝后的模型仍然具有有效的递归性质。

需要注意的是，递归剪枝的具体方法和实现细节因模型和任务而异。在实践中，建议参考相关研究论文、工具库或咨询专业人士，以获得更具体和针对性的指导。

https://blog.csdn.net/lady_killer9/article/details/108539937

https://blog.csdn.net/qq_17753903/article/details/82954281

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 2)
        return 1;

    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int temp = (a + b) % 100000007;
        a = b;
        b = temp;
    }

    return b;
}

int main() {
    int n;
    cin >> n;

    int result = fibonacci(n);
    cout << result << endl;

    return 0;
}