C++ 基础语法与算法初步：从循环到递归

函数与模块化编程

#include <iostream>
using namespace std;
long long a[55]; // 全局变量全局都可以使用，而主函数里的 n 只能在主函数内使用

int fbnq(int n) {
    a[1] = 1, a[2] = 1;
    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2]; // 公式还是那样，但是变成函数内部了
    }
    return a[n]; // 函数需要返回值哦（void 函数除外），没有返回值函数再怎么写也没用哦
}

int main() {
    int n;
    cin >> n;
    cout << fbnq(n); // 记得上面定义时括号里写东西了，这里就也要写东西
    return 0;
}

各种函数特点与用法

小提示：类型 函数名(int/long long/bool/其他类型 新创建的变量名)输入变量名的类型 void 是不合法的！若使用了会报错。

练习题目 1：学而思网校提供

#include <cstdio>
#include <cmath>
using namespace std;

// 定义函数
int express(double w) {
    // 以下是本题核心代码
    int money;
    w = round(w * 10) / 10;
    if (w <= 1) {
        money = 13;
    } else {
        w = ceil((w - 1) / 0.5);
        money = 13 + w;
    }
    return money; // 输出花费
}

int main() {
    double w;
    scanf("%lf", &w);
    printf("%d\n", express(w)); // 直接套用函数输出值输出
    return 0;
}

建议：可以再洛谷上寻找一些简单题目专门用函数来写，进行练习。

多重循环（for 循环 plus 版）

模板：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // 此模板还可以不断叠层
        // 这段模板内出现的所有变量名均可替换：i,j,n
    }
}

闲话不多说，直接上题目。

练习题目 1：USACO 题目饲料调配

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

int main() {
    int a, b, c; // 输入数据
    cin >> a >> b >> c;
    int a1, b1, c1;
    cin >> a1 >> b1 >> c1;
    int a2, b2, c2;
    cin >> a2 >> b2 >> c2;
    int a3, b3, c3;
    cin >> a3 >> b3 >> c3;
    for (int i = 0; i < 100; i++) // 使用三重 for 循环
    {
        for (int j = 0; j < 100; j++) // 以后做其他题使用三重 for 循环须慎重（可能会超时）
        {
            for (int k = 0; k < 100; k++) {
                if (!i && !j && !k) {
                    continue;
                }
                int x = a1 * i + a2 * j + a3 * k; // 进行题目内要求的计算
                int y = b1 * i + b2 * j + b3 * k;
                int z = c1 * i + c2 * j + c3 * k;
                if (x * b == y * a && y * c == b * z && x % a == 0) {
                    cout << i << " " << j << " " << k << " " << x / a << endl;
                    return 0; // 输出答案结束程序
                }
            }
        }
    }
    cout << "NONE"; // 若前方未结束程序输出无正解
    return 0;
}

练习题目 2

可以自己之后去练习。

while 循环

// while 循环本质逻辑与 for 循环大差不差，所以小编就不在这里过多废话了
while (true) // 每次循环判断此条件是否成立，成立即继续运行，不成立则反之
{
    cout << "作者真帅";
}

练习题目 1

练习题目 2：数根

题目描述

数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根。如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。 比如，对于 24 来说，把 2 和 4 相加得到 6，由于 6 是一位数，因此 6 是 24 的数根。再比如 39，把 3 和 9 加起来得到 12，由于 12 不是一位数，因此还得把 1 和 2 加起来，最后得到 3，这是一个一位数，因此 3 是 39 的数根。

输入描述

一个整数 n，(1 <= n <= 10^9)

输出描述

一个数字，即 n 的数根

样例 1

输入

39

输出

3

结构体

C++ 结构体的基本概念

在 C++ 中，结构体得到了极大的增强，几乎和类一样强大，唯一区别是默认访问权限为 public（类为 private）。

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

// C++ 结构体定义
struct Student {
    string name; // C++ 中可以直接使用 string
    int age;
    float score;
};

int main() {
    // 创建结构体变量 Student stu1
    // C++ 中不需要写 struct 关键字
    stu1.name = "张三";
    stu1.age = 20;
    stu1.score = 85.5;
    cout << "姓名：" << stu1.name << endl;
    cout << "年龄：" << stu1.age << endl;
    cout << "成绩：" << stu1.score << endl;
    return 0;
}

结构体的定义方式

基本定义

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

// 方式 1：普通定义
struct Person {
    string name;
    int age;
    string phone;
};

// 方式 2：定义时创建对象
struct Car {
    string brand;
    string model;
    int year;
} car1, car2;

// 全局对象
int main() {
    // 方式 3：使用 typedef（C++ 中不太需要）
    typedef struct {
        string city;
        string street;
        int number;
    } Address;
    Address addr = {"北京", "长安街", 1};
    Person p; // 直接使用，不需要 struct 关键字
    Car myCar; // 局部对象
    return 0;
}

结构体的初始化

多种初始化方法

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

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

int main() {
    // 方法 1：聚合初始化（C++11 起）
    Student stu1 = {"张三", 20, 85.5};
    // 方法 2：指定成员初始化（C++11 起）
    Student stu2 = {.name = "李四", .age = 21, .score = 92.0};
    // 方法 3：使用构造函数（结构体可以有构造函数）
    Student stu3("王五", 22, 88.5); // 如果有构造函数的话
    // 方法 4：默认初始化
    Student stu4{}; // name 为空，age=0，score=0
    // 方法 5：逐个赋值
    Student stu5;
    stu5.name = "赵六";
    stu5.age = 23;
    stu5.score = 90.5;
    // 输出验证
    cout << stu1.name << " " << stu1.age << " " << stu1.score << endl;
    cout << stu4.name << " " << stu4.age << " " << stu4.score << endl; // 0 0
    return 0;
}

结构体成员访问

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

struct Point {
    int x;
    int y;
    // 成员函数
    void display() {
        cout << "Point(" << x << ", " << y << ")" << endl;
    }
    // 计算到原点的距离
    double distance() {
        return sqrt(x * x + y * y);
    }
};

int main() {
    Point p1 = {3, 4}; // 直接访问
    cout << "x = " << p1.x << ", y = " << p1.y << endl;
    // 调用成员函数
    p1.display();
    cout << "到原点的距离：" << p1.distance() << endl;
    // 指针访问
    Point *ptr = &p1;
    ptr->x = 5;
    ptr->y = 12;
    cout << "修改后：";
    ptr->display();
    return 0;
}

结构体数组

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

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

int main() {
    // 定义并初始化结构体数组
    Student class1[3] = {{"张三", 20, 85.5}, {"李四", 21, 92.0}, {"王五", 22, 88.5}};
    cout << "班级学生信息：" << endl;
    cout << setw(10) << "姓名" << setw(6) << "年龄" << setw(8) << "成绩" << endl;
    cout << "------------------------" << endl;
    // 遍历数组
    for (int i = 0; i < 3; i++) {
        cout << setw(10) << class1[i].name << setw(6) << class1[i].age << setw(8) << fixed << setprecision(1) << class1[i].score << endl;
    }
    // 动态分配结构体数组
    Student* class2 = new Student[2];
    class2[0] = {"赵六", 19, 78.5};
    class2[1] = {"孙七", 20, 95.0};
    delete[] class2; // 释放内存
    return 0;
}

结构体嵌套

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

// 地址结构体
struct Address {
    string city;
    string street;
    int number;
    void show() {
        cout << city << " " << street << " " << number << "号";
    }
};

// 联系方式结构体
struct Contact {
    string phone;
    string email;
};

// 学生结构体嵌套其他结构体
struct Student {
    string name;
    int age;
    Address addr; // 嵌套 Address
    Contact contact; // 嵌套 Contact
    void showInfo() {
        cout << "姓名：" << name << endl;
        cout << "年龄：" << age << endl;
        cout << "地址：";
        addr.show();
        cout << "\n电话：" << contact.phone << endl;
        cout << "邮箱：" << contact.email << endl;
    }
};

int main() {
    Student stu = {"张三", 20, {"北京", "长安街", 1}, {"13800138000", "[email protected]"}};
    stu.showInfo(); // 访问嵌套成员
    cout << "\n城市：" << stu.addr.city << endl;
    cout << "电话：" << stu.contact.phone << endl;
    return 0;
}

结构体与函数

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

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

// 值传递
void printRect1(Rectangle r) {
    cout << "宽：" << r.width << "，高：" << r.height << "，面积：" << r.area() << endl;
}

// 引用传递（避免复制）
void printRect2(const Rectangle &r) {
    cout << "宽：" << r.width << "，高：" << r.height << "，面积：" << r.area() << endl;
}

// 指针传递
void modifyRect(Rectangle *r, double w, double h) {
    r->width = w;
    r->height = h;
}

// 返回结构体
Rectangle createRect(double w, double h) {
    return {w, h}; // C++11 的统一初始化
}

int main() {
    Rectangle r1 = {10, 5};
    printRect1(r1); // 值传递
    printRect2(r1); // 引用传递
    modifyRect(&r1, 20, 10);
    cout << "修改后：";
    printRect2(r1);
    Rectangle r2 = createRect(15, 8);
    cout << "新矩形：";
    printRect2(r2);
    return 0;
}

结构体与运算符重载

#include <iostream>
using namespace std;

struct Vector2 {
    float x, y;
    // 构造函数
    Vector2(float x = 0, float y = 0) : x(x), y(y) {}
    // 运算符重载
    Vector2 operator+(const Vector2& other) const {
        return Vector2(x + other.x, y + other.y);
    }
    Vector2 operator*(float scalar) const {
        return Vector2(x * scalar, y * scalar);
    }
    // 友元函数重载<<运算符
    friend ostream& operator<<(ostream& os, const Vector2& v) {
        os << "(" << v.x << ", " << v.y << ")";
        return os;
    }
};

int main() {
    Vector2 v1(3, 4);
    Vector2 v2(1, 2);
    Vector2 v3 = v1 + v2;
    Vector2 v4 = v1 * 2;
    cout << "v1 = " << v1 << endl;
    cout << "v2 = " << v2 << endl;
    cout << "v1 + v2 = " << v3 << endl;
    cout << "v1 * 2 = " << v4 << endl;
    return 0;
}

结构体与动态内存

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

struct Node {
    int data;
    Node* next; // 自引用结构体（链表节点）
    Node(int val) : data(val), next(nullptr) {}
};

struct DynamicArray {
    int* arr;
    int size;
    DynamicArray(int n) : size(n) {
        arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = i * 10;
        }
    }
    ~DynamicArray() {
        delete[] arr;
        cout << "内存已释放" << endl;
    }
    void display() {
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    // 链表示例
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    // 遍历链表
    Node* current = head;
    while (current) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
    // 释放链表内存
    while (head) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
    // 动态数组结构体
    DynamicArray da(5);
    da.display(); // da 的析构函数会自动释放内存
    return 0;
}

结构体 vs 类的对比

#include <iostream>
using namespace std;

// 结构体 - 默认 public
struct MyStruct {
    int a; // 默认 public
    void func() {
        // 默认 public
        cout << "Struct function" << endl;
    }
};

// 类 - 默认 private
class MyClass {
    int a; // 默认 private
public:
    void func() {
        cout << "Class function" << endl;
    }
};

// 实际使用中，结构体常用于：
// 1. 简单的数据容器
// 2. 与 C 语言兼容的代码
// 3. 不需要封装和继承的简单对象
struct Point {
    int x, y;
};

// 类用于：
// 1. 复杂的对象
// 2. 需要封装和继承
// 3. 有复杂的成员函数
class Shape {
private:
    Point center;
public:
    virtual void draw() = 0;
};

int main() {
    MyStruct s;
    s.a = 10; // 可以直接访问
    s.func();
    MyClass c;
    // c.a = 10; // 错误！私有成员
    c.func(); // 公有成员函数
    return 0;
}

实用示例：学生成绩管理系统

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

// 学生结构体
struct Student {
    string id;
    string name;
    int age;
    double score;
    // 构造函数
    Student(string id, string name, int age, double score) : id(id), name(name), age(age), score(score) {}
    // 显示学生信息
    void display() const {
        cout << "学号：" << id << "，姓名：" << name << "，年龄：" << age << "，成绩：" << score << endl;
    }
};

// 班级结构体
struct Class {
    string className;
    vector<Student> students;
    void addStudent(const Student& stu) {
        students.push_back(stu);
    }
    void showAll() {
        cout << "\n=== " << className << " 学生列表 ===" << endl;
        for (const auto& stu : students) {
            stu.display();
        }
    }
    double getAverageScore() {
        if (students.empty()) return 0;
        double sum = 0;
        for (const auto& stu : students) {
            sum += stu.score;
        }
        return sum / students.size();
    }
    void sortByScore() {
        sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    }
};

int main() {
    Class c1 = {"计算机 1 班"};
    // 添加学生
    c1.addStudent({"2024001", "张三", 20, 85.5});
    c1.addStudent({"2024002", "李四", 21, 92.0});
    c1.addStudent({"2024003", "王五", 20, 78.5});
    c1.addStudent({"2024004", "赵六", 22, 95.0});
    // 显示所有学生
    c1.showAll();
    // 计算平均分
    cout << "\n班级平均分：" << c1.getAverageScore() << endl;
    // 按成绩排序
    c1.sortByScore();
    cout << "\n=== 按成绩排序后 ===";
    c1.showAll();
    return 0;
}

ASCLL 码

ASCLL 码就像一个字符的身份证，每一个字符都有一个数字来代表，而怎么判断一个字符的'身份证'是多少呢，请看下面示例。

#include <iostream>
using namespace std;

int main() {
    char s = 'A'; // 必须要 char 类型的
    int a = s; // 用 int 来转换字符，变为数字
    cout << a; // 最后输出转换好的数字
    return 0;
}

有一个小提示，字符 A-Z 是挨在一起的，所以我们知道了 A 的身份证是 65，就可以推出 B 的字符是 66，以此类推，注意，小写字符和大写字符不是挨在一起的，所以需要记好'a'的身份证是 97。

推荐大家可以使用菜鸟教程这个网站。

string 类型

不知道大家是否学过 python 的字符串，在 python 中，字符串是可以像数组那样进行下表操作的。而不幸的是，C++ 中正常的 char 类型字符串无法进行下表操作，而 string 类型可以。不过请注意，string 类型没有负索引这个东西:

练习题目 1：

题目描述

有 N 只史莱姆排成一排，每只的颜色用一个英文小写字母表示，所有史莱姆的颜色排列成一个字符串 S。 接下来同样颜色的史莱姆会融合成一只，直到所有相邻的史莱姆颜色都不同。问最后剩下几只史莱姆？

输入格式

第 1 行，1 个正整数 N 第 2 行，字符串 S，表示每只史莱姆的颜色

输出格式

输出最后剩下史莱姆的数量

输入样例#1

10 aabbbbaaca

输出样例#1

5

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int count = 1; // 计数器
    for (int i = 1; i < n; i++) {
        if (s[i] != s[i - 1]) // 判断有几只不同的史莱姆（因为如果有不同的就不会计数）
        {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

string 字符串操作

string 字符串边界代码表格：

字符串拼接：

两个字符串是可以像加法一般拼在一起的，请看示例：

string s = "作者";
string n = "真帅";
string m = s + n;
cout << m;

运行这段代码后终端会显示出'作者真帅这四个字'。

练习题目 1：贪婪的送礼者

以下是 AC 代码，可以用来做对拍。

#include <bits/stdc++.h> // 万能头文件，十分好用，建议背下来
using namespace std;
map<string, int> money;
int n, l, have;
string name[105], x, buddy;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> name[i];
    for (int i = 1; i <= n; i++) {
        cin >> x >> have >> l;
        if (l == 0) continue;
        money[x] -= have;
        int give = floor(have / l);
        money[x] += (have - l * give);
        for (int i = 1; i <= l; i++) {
            cin >> buddy;
            money[buddy] += give;
        }
    }
    for (int i = 1; i <= n; i++) cout << name[i] << " " << money[name[i]] << endl;
    return 0;
}

递归初步

1.1 递归的含义与历史

递归是计算机科学的一个不可分割的算法。递归指的是一个函数直接或间接读取自己的过程。但在我们使用递归的时候要注意不要写成死循环，并且我们也要明确我们写这个递归的目的，要逐步地把问题缩小化。

1.2 举个栗子

递归死循环：

在小明小的时候听过这样的一个故事：从前有座山，山中有座庙，庙里有个老和尚，老和尚在讲故事，讲的是什么呀？从前有座山，山中有座庙，庙里有个老和尚在讲故事……

像这样的故事没有丝毫特点，就像你写死循环的时候重复给机器讲一个'故事'，机器就会困得睡着了，因此就'睡着了'。

1.3 代码示例

int dg(int n) {
    if (n == 87) // 结束条件
    {
        return 1;
    }
    return dg(n + 1); // 引用时 n+1
}

练习题目 1：

此题为欧几里得公式递归写法，AC 代码如下：

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b); // 欧几里得算法公式
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b); // 其实万能头下__gcd(a,b) 可以直接出答案
    return 0;
}

拔高题目 1：

这道题难度较高，使用了我们还未学到的回溯算法，可以自己深研以下。

#include <iostream>
using namespace std;

int n, m, p[15], ans;
bool vis[15];

void dfs(int step) {
    if (step == n + 1) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 1) {
                sum += p[i];
            }
        }
        if (sum == m) {
            ans++;
        }
        return;
    }
    vis[step] = 1;
    dfs(step + 1);
    vis[step] = 0;
    dfs(step + 1);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

回溯法

1.1 前言

在上一个知识点递归初步里的拔高题目 AC 代码使用了回溯法，在这个知识点部分我们来学习回溯法。

1.1.1 什么是回溯法？

小明：老师，回溯法是啥捏，是时空大回溯吗。 老师：对也不完全对，回溯指的是在做题时一种试错过程中不可缺少的部分。比如说…… 小明：老师！也就是说回溯就是一种不撞南墙不回头的做法呗。 老师：对了，我们如果发现一种路线不可行，那么我们立即使用下一条路线，而回到原来选择的那个分支的方法，我们称为回溯法，或者说这也是种枚举的过程

1.1.2 回溯法有什么用呢

有人说，回溯法的底层逻辑就是递归，有回溯的地方就有递归。而回溯在做背包一类的题目中有显著优势，背包这个东西我们后文会提到。

2. 回溯模板

这是一道全排列枚举题目：

AC 代码

#include <cstdio>
#include <cstring>
#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] == 1) {
            continue;
        }
        plan[step] = i; // 回溯核心部分
        vis[i] = 1;
        dfs(step + 1); // 调用自己，递归操作
        vis[i] = 0;
    }
}

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

高精度算法

1. 加法

1.1 前言

在大家的小学时期怎样计算两个数相加呢，想必有的人会使用竖式的方法，而高精度就是来模拟竖式加法。

1.2 代码逻辑

我们知道了高精度加法的具体逻辑，就是模拟人类计算多位数加多位数时使用的竖式计算方式，而在加的时候就会出现多一位的情况。

有时我们就会出现这种尴尬的方式，数组下表 0 的那个部分给到了数字 9，而多的那一位就没有地方了。也许有的人会说，那把 9 的下表设为 1 不就行了，但是有时数位不会多出来一位，若是这样的话有时输出就会出现前导 0，所以，我们就要请出这个方法了——逆序存储。因为这样的话若是没有多出来的那一位就不会出现前导 0 了，因为逆序输出的时候记好是否有多出来的那一位就可以了。

1.3 逆序存储代码：

void add(string s, int a[]) {
    a[0] = s.size();
    for (int i = 1; i <= a[0]; i++)
        a[i] = s[a[0] - i] - '0';
}

1.4 核心代码

在我们加法运算的过程中，一定会出现进位的情况，而我们就要推出进位变量 carry，核心代码实现如下：

void addBIG(int a[], int b[], int c[]) {
    c[0] = max(a[0], b[0]);
    int carry = 0; // 进位函数
    for (int i = 1; i <= c[0]; i++) {
        int t = a[i] + b[i] + carry; // 两位相加并加上前一位的进位数
        c[i] = t % 10; // 存入数组
        carry = t / 10; // 计算下一位进位数值
    }
    if (u > 0) {
        c[++c[0]] = carry;
    }
}

1.5 输出

最后一步也是最重要的一步——逆序输出。因为我们前文说到是逆序存入，so 我们要逆序输出，这样才能输出正确。

1.6 整体代码

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

void s2BIG(string s, int a[]) {
    a[0] = s.size();
    for (int i = 1; i <= a[0]; i++)
        a[i] = s[a[0] - i] - '0';
}

void printBIG(int a[]) {
    for (int i = a[0]; i >= 1; i--)
        cout << a[i];
    cout << endl;
}

void addBIG(int a[], int b[], int c[]) {
    c[0] = max(a[0], b[0]);
    int u = 0;
    for (int i = 1; i <= c[0]; i++) {
        int t = a[i] + b[i] + u;
        c[i] = t % 10;
        u = t / 10;
    }
    if (u > 0) {
        c[++c[0]] = u;
    }
}

int a[1000005], b[100005], c[100005];
string sa, sb;

int main() {
    cin >> sa >> sb;
    s2BIG(sa, a);
    s2BIG(sb, b);
    addBIG(a, b, c);
    printBIG(c);
    return 0;
}

2. 高精度减法