C++ 基础入门：从循环结构到算法初步

注意： 非 void 函数必须包含 return 语句返回对应类型的值。

示例：斐波那契数列函数化

#include <iostream>
using namespace std;

long long fib[55];

long long fbnq(int n) {
    fib[1] = 1, fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

int main() {
    int n;
    cin >> n;
    cout << fbnq(n) << endl;
    return 0;
}

多重循环与嵌套

当问题涉及多维数据或组合枚举时，常使用嵌套循环。需注意时间复杂度，避免不必要的超时。

模板：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // 处理逻辑
    }
}

结构体 (Struct)

结构体用于将不同类型的数据组合成一个整体，默认访问权限为 public。

基本定义与初始化

#include <iostream>
#include <string>
using namespace std;

struct Student {
    string name;
    int age;
    double score;
};

int main() {
    // 聚合初始化 (C++11)
    Student stu1 = {"张三", 20, 85.5};
    
    // 成员访问
    cout << "姓名：" << stu1.name << endl;
    return 0;
}

结构体进阶用法

1. 嵌套结构体：用于表示复杂关系，如学生包含地址信息。
2. 结构体数组：批量管理同类对象。
3. 运算符重载：使结构体支持自定义运算行为。

示例：矩形面积计算

struct Rectangle {
    double width, height;
    double area() const { return width * height; }
};

void printRect(const Rectangle& r) {
    cout << "面积：" << r.area() << endl;
}

字符串与 ASCII 码

ASCII 码

每个字符对应一个数字编码。大写字母 'A' 为 65，小写 'a' 为 97。字符在内存中存储为对应的整数值。

char c = 'A';
int code = c; // code 值为 65

String 类型

C++ 的 std::string 类提供了丰富的字符串操作功能，支持下标访问和拼接。

string s = "Hello";
s += " World"; // 拼接
cout << s[0];   // 输出 'H'

练习：相邻相同字符消除

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] != s[i - 1]) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

递归与回溯

递归基础

递归是函数调用自身的技巧，关键在于明确终止条件和递推关系，防止死循环。

示例：欧几里得算法求最大公约数

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

回溯法

回溯是一种通过试错来解决问题的算法，常用于全排列、组合等问题。核心思想是：尝试一种路径，若不可行则回退并尝试下一条路径。

模板：全排列

#include <iostream>
using namespace std;

bool vis[10];
int plan[10];
int n;

void dfs(int step) {
    if (step == n + 1) {
        for (int i = 1; i <= n; i++) {
            cout << plan[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            plan[step] = i;
            dfs(step + 1);
            vis[i] = false; // 回溯
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

高精度算法

当数值超过 long long 范围时，需使用数组模拟竖式运算。

核心思路

1. 逆序存储：数组下标 1 存个位，便于进位处理。
2. 逐位运算：模拟手工加法/减法，处理进位。
3. 逆序输出：从高位到低位打印结果。

示例：高精度加法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 字符串转数组 (逆序)
void strToArr(string s, vector<int>& a) {
    a.clear();
    for (int i = s.size() - 1; i >= 0; i--) {
        a.push_back(s[i] - '0');
    }
}

// 高精度加法
vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int t = 0;
    for (size_t i = 0; i < a.size() || i < b.size() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main() {
    string sa, sb;
    cin >> sa >> sb;
    
    vector<int> A, B;
    strToArr(sa, A);
    strToArr(sb, B);
    
    vector<int> C = add(A, B);
    
    for (int i = C.size() - 1; i >= 0; i--) {
        cout << C[i];
    }
    cout << endl;
    return 0;
}

以上内容涵盖了 C++ 编程的核心基础。建议读者结合具体题目进行练习，逐步理解代码背后的逻辑。