C++ 基础教程：从 For 循环到算法初步

函数特点与用法

练习题目：

题目描述 计算花费。输入重量 w，若 w<=1 则花费 13；否则花费 13 + ceil((w-1)/0.5)。

代码实现

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

int express(double w) {
    w = round(w * 10) / 10;
    if (w <= 1) {
        return 13;
    } else {
        double temp = ceil((w - 1) / 0.5);
        return 13 + (int)temp;
    }
}

int main() {
    double w;
    scanf("%lf", &w);
    printf("%d\n", express(w));
    return 0;
}

多重循环

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // 可叠层使用
    }
}

练习题目：饲料调配

题目描述 给定三种饲料的营养成分及需求，求满足需求的饲料组合数量。

代码实现

#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 (int j = 0; j < 100; j++) {
            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;
}

while 循环

while (true) {
    // 条件成立时继续运行
}

练习题目：数根

题目描述 将一个数的各位数字相加，若结果不是一位数则重复此过程，直到得到一位数。

输入描述 一个整数 n (1 <= n <= 10^9)

输出描述 一个数字，即 n 的数根

样例 输入：39 输出：3

结构体

C++ 结构体的基本概念

在 C++ 中，结构体默认访问权限为 public。

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

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

int main() {
    Student stu1;
    stu1.name = "张三";
    stu1.age = 20;
    stu1.score = 85.5;
    cout << "姓名：" << stu1.name << endl;
    cout << "年龄：" << stu1.age << endl;
    cout << "成绩：" << stu1.score << endl;
    return 0;
}

结构体的定义方式

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

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

// 方式 3：使用 typedef
typedef struct {
    string city;
    int number;
} Address;

结构体的初始化

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

int main() {
    // 聚合初始化
    Student stu1 = {"张三", 20, 85.5};
    // 指定成员初始化
    Student stu2 = {.name = "李四", .age = 21, .score = 92.0};
    // 默认初始化
    Student stu4{};
    return 0;
}

结构体嵌套

struct Address {
    string city;
    string street;
    int number;
};

struct Student {
    string name;
    Address addr;
};

int main() {
    Student stu = {"张三", {"北京", "长安街", 1}};
    return 0;
}

结构体与函数

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

void printRect(const Rectangle &r) {
    cout << r.width << " " << r.height << endl;
}

结构体 vs 类的对比

• 结构体：默认 public，常用于简单数据容器。
• 类：默认 private，常用于复杂对象封装。

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

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

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

    void display() const {
        cout << "学号：" << id << "，姓名：" << name << endl;
    }
};

struct Class {
    string className;
    vector<Student> students;

    void addStudent(const Student& stu) {
        students.push_back(stu);
    }

    void showAll() {
        for (const auto& stu : students) {
            stu.display();
        }
    }
};

int main() {
    Class c1 = {"计算机 1 班"};
    c1.addStudent({"2024001", "张三", 20, 85.5});
    c1.showAll();
    return 0;
}

ASCII 码

ASCII 码是字符的数字表示。char 类型可转换为 int 获取其 ASCII 值。

#include <iostream>
using namespace std;

int main() {
    char s = 'A';
    int a = s;
    cout << a; // 输出 65
    return 0;
}

注意：'A'-'Z' 连续，'a'-'z' 连续，但大小写之间不连续。

string 类型

C++ 中的 string 类型支持下标操作，但不支持负索引。

字符串拼接

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

练习题目：史莱姆融合

题目描述 有 N 只史莱姆排成一排，颜色用英文小写字母表示。相同颜色的相邻史莱姆会融合。问最后剩下几只？

代码实现

#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;
}

递归初步

递归指函数直接或间接调用自己的过程。需注意终止条件以避免死循环。

代码示例

int dg(int n) {
    if (n == 87) {
        return 1;
    }
    return dg(n + 1);
}

练习题目：欧几里得算法

题目描述 计算两个整数的最大公约数。

代码实现

#include <iostream>
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) << endl;
    return 0;
}

回溯法

回溯法是一种试错过程，当发现当前路径不可行时回退到上一步选择其他分支。

模板：全排列枚举

#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]) continue;
        plan[step] = i;
        vis[i] = true;
        dfs(step + 1);
        vis[i] = false;
    }
}

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

高精度算法

加法

模拟竖式加法，逆序存储数组以方便处理进位。

#include <iostream>
#include <string>
#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;
}

减法

原理同加法，将进位改为退位，并需比较两数大小。

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

// ... (省略部分辅助函数，逻辑同上)

bool cmpBIG(int a[], int b[]) {
    if (a[0] != b[0]) return a[0] < b[0];
    for (int i = a[0]; i >= 1; i--)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}

void subBIG(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;
        if (t < 0) {
            c[i] = t + 10;
            u = 1;
        } else {
            c[i] = t;
            u = 0;
        }
    }
    while (c[c[0]] == 0 && c[0] > 1) c[0]--;
}

int a[1005], b[1005], c[1005];
string sa, sb;

int main() {
    cin >> sa >> sb;
    s2BIG(sa, a);
    s2BIG(sb, b);
    if (cmpBIG(a, b)) subBIG(b, a, c);
    else subBIG(a, b, c);
    printBIG(c);
    return 0;
}