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：饲料调配

#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：数根

题目描述

数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根。如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。 比如，对于 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

while 循环

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

结构体

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

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

ASCII 码

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

#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：贪婪的送礼者

#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：组合求和

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

AC 代码：

#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.高精度减法

内容正在更新中……