问题标题: Grammar / Algorithm Etc 讲解1

序

整理了一下c++语法，算法的玩意，发出来得了。

 

        c++介绍

了解c++的发展过程
C++ 是由 Bjarne Stroustrup 于 1979 年在新泽西州美利山贝尔实验室开始设计**的。
于1998年发布第一版c++98，是第一个c++标准。
于2003年发布第二版c++03，是第二个c++标准。
于2006年进行了c++**能技术报告。
于2007年发布了c++TR1，进行了库扩展。
于2010年进行了数学函数的扩展。
于2011年发布第三版c++11，是第三个c++标准。同年进行了十进制浮点数扩展。
于2014年发布第四版c++14，是第四个c++标准。
于2015年发布filesystem TS，便于文件**。同年发布parallelism TS，用于并行计算的扩展。
于2016年发布concurrency TS，用于并发计算的扩展。
于2017年进行了标准库扩展，协程库扩展，发布了第五版c++17，是第五个c++标准。

C++是综合了C的过程化程序设计的中高级语言程序。
C++引入了面向对象的概念，使得**人机交互类型的应用程序更为简单、快捷。
很多优秀的程序框架包括Boost、Qt、MFC、OWL、wxWidgets、WTL就是使用的C++。
C++的别名：C++ Programming Language/c plus plus
 

以后更。

姜宇轩在2022-05-20 19:49:09追加了内容

            时间复杂度

时间复杂度是指代码执行所需的时间。

举例如下：

for(int i=1;i<=1000;i++){
    cout<<"i的值为"<<i<<endl;
}

此代码循环遍历了1~1000，共1000遍，所以时间复杂度为1000。
时间复杂度可以用大O表示法进行表示。
时间复杂度是精确的，比如1000，就可以表示为O(1000)。

如果时间是不精确的，例如：

int n,a[10005],cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
    cin>>a[i];
    if(a[i]%3==0&&a[i]%6==0){
    cnt++;
    }
}
for(int i=1;i<=cnt;i++){
    cout<<"有"<<i<<"个数是3的倍数以及6的倍数"<<endl;
}

此代码的第一个循环是精确时间的，时间是O(n);
而第二个循环并不是精确的，但绝对在0~n之中（可能没有为0），所以取max值。
max(0,n)=n;
所以粗略计算第二个循环的时间为n。
所以此代码的时间复杂度是O(2n);

如果是双重循环：

for(int i=1;i<=x;i++){
    for(int j=1;j<=y;j++){
    cout<<i*j<<" ";
    }
    cout<<endl;
}

外层循环时间x，内层循环时间y，每一次外层循环当中都要循环y次。
时间复杂度O(x*y);

关于时间复杂度的知识可以用于判断程序是否超时，避免多次才能ac。
 

姜宇轩在2022-05-22 13:10:15追加了内容

关于日期问题（这章有点水）

【点1】储存每月天数
    在许多日期问题中都需要用到每个月的天数进行解题。
    我们不能每次需要就判断12次（12个月），所以要用数组存储下来。

    int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};    //每个月的天数

【点2】判断闰年
    在许多日期问题中都需要判断闰年。
    那么怎么判断闰年？
    闰年的二月是29天。

    if(这个年份是闰年){
        mon[2]=29;
        //或者mon[2]++;
    }

    闰年的定义：
    能被4整除而且不能被100整除。
    或者能被400整除。

     if(year%4==0&&year%100!=0||year%400==0){
        mon[2]=29;
     }

姜宇轩在2022-05-22 17:04:51追加了内容

爆肝一年！整出来了

问：上一行表达了作者怎样的思想感情？【doge】

        递推

递推是指在一个有规律的序列中用已有的条件求位置条件。
1、2、3、4......
我们可以通过前四项的规律求出第五项是5，第六项是6......
这就是递推。

对应题目:1028

斐波那契数列，又称黄金分割数列。
指得是这样一个数列：
数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
即：1, 1, 2, 3, 5, 8......
现给出一个正整数N，求斐波那契数列中第N项是多少？
N<=46

前46项的斐波那契数列用int是能存下的。

定义一个答案数组，按照题目，将1、2项赋值为1。

int f[50],n;
cin>>n;
f[1]=1;
f[2]=1;

循环多少次能把数列写完整？
由于1、2项已经赋值，所以从3开始遍历即可，循环n-2次。

for(int i=3;i<=n;i++){
    f[i]=______1______;
}

1空处填f[i]=f[i-1]+f[i-2]，表示第i项的值等于前面两个数的和。

输出什么？题目给出：求第N项，所以输出第N的值f[n]。

递推要找四要素：
1.边界      本题中为f[1]=1,f[2]=1
2.递推式    本题中为f[i]=f[i-1]+f[i-2]
3.解        本题中为f[n]
4.？（大佬回答）

**：求斐波那契数列时最好用long long型。

姜宇轩在2022-05-23 19:42:30追加了内容

 

递推转递归

有时，我们可能会采用递归的方法解题。
递归指的是一开始就想着输出答案，但解不出来，**前面的数推解。

例如求斐波那契数列的第5项。
第五项不知道，用第四项和第三项求。
第四项不知道，用第三项和第二项求。
第三项不知道，用第二项和第一项求。

而递归也是要有边界的，如果一直求不出来，就会**循环。

编写函数完成递归：（求斐波那契第五项）
 

int f(int n){            //n表示要求的项数
    if(n==1) return 1;   //边界
    if(n==2) return 1;   //边界
    return f(n-1)+f(n-2); //递归式
}  

题目：3938
采用递推：

long long f[45],n;
f[1]=1;
cin>>n;
for(int i=2;i<=n;i++){
    f[i]=f[i-1]*2+1;
    cout<<f[i]<<" ";
}

转递归：

int f(int n){
    if(n==1) return 1;
    return f(n-1)*2+1;
}   

 

姜宇轩在2022-05-24 18:47:55追加了内容

点1 快速排序的时间复杂度
快速排序的时间复杂度是O(nlogn)。

点2 排序算法的稳定**列举
快速排序，选择排序是不稳定的。
冒泡排序，插入排序是稳定的。

点3 判断稳定**
数列中值相同的元素，在排序过程中相对顺序不改变，这种排序算法就是稳定的。

点4 快排的步骤
1.在数列中找到一个元素做基准值（标兵）
2.把比基准值小的元素尽量往左放，比基准值大的元素尽量往右放
3.对左边以及右边的数列继续进行上述步骤操作

点5 快排代码实现
 

void q_sort(int a[],int l,int r){  //对a[l]~a[r]进行排序
    int mid=a[(l+r)/2];            //标兵（基准值）
    int i=l,j=r;
    while(i<=j){
        while(a[i]<mid) i++;       //确定i的位置
        while(a[j]>mid) j--;       //确定j的位置
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(l<j) q_sort(a,l,j);         //对左边继续排序
    if(i<r) q_sort(a,i,r);         //对右边继续排序
}

 

姜宇轩在2022-05-25 20:48:24追加了内容

sort排序

c++有一种自带的库排序函数sort。
使用格式：
sort(范围起点，范围终点);
注：需加头文件

#include<algorithm>

例如：

int a[55];
for(int i=1;i<=50;i++){
    cin>>a[i];
}
sort(a+1,a+50+1);

上述代码首先输入了a数组的前50项元素（下标从一开始）。
sort排序表示把a数组下标从1~50的部分排序（默认从小到大）。

可以自定义排序方式：
在主函数前编写cmp函数：

bool cmp(int x,int y){        //表示参与排序的值
    return x>y;               //表示排序规则，此处为从大到小排序
}

完成一个从大到小排序的代码：

#include<iostream>
#include<algorithm>
using namespace std;
int a[55];
bool cmp(int x,int y){        //表示参与排序的值
    return x>y;               //表示排序规则，此处为从大到小排序
}
int main(){
    for(int i=1;i<=50;i++){    //输入前50项的值
        cin>>a[i];
    }
    sort(a+1,a+50+1,cmp);      //第三个位置表示排序规则，不写则为从小到大
    for(int i=1;i<=50;i++){
	 cout<<a[i]<<" ";
    }
    return 0;
}

题目：3827

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[20005];
bool cmp(int x,int y){
    if(x%10!=y%10){
        return x%10>y%10;     //要先判断个位数排序，如果个位数不相同，按个位数排序
    }
    return x<y;               //在按照数字大小排序
}
int main(){   
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
 	cout<<a[i]<<endl;
    }
    return 0;
}

看在我这么肝的份上，点个赞吧

@酷町扫地僧 能申精吗？？？求！

姜宇轩在2022-05-29 17:49:52追加了内容

我来更了！

首先，抱歉，最近几天都没有更新，因为学校的诵读比赛，耽误了时间

 

二分基**

对应题目：二分查找1

二分的含义是指把数组分成两半，寻找值，每次可以排除一半左右的元素。

题目讲解：
在一个有n个元素的从小到大的序列中（无重复元素）寻找t存不存在。
存在则输出位置，不存在输出-1。
n<=10^8+100000

如果按照普通遍历，肯定会超时。
这时我们就要使用二分。

例:
n=6
t=2
1 2 3 4 5 6

首先定义l和r（left,right）表示要在l~r范围内找。
把数组分成两半，取中间值为mid。
mid可能比t小，可能大于t，可能相等。

mid如果比t小，说明t在mid的右边。
mid如果比t大，说明t在mid的左边。
mid如果与t相等，说明找到了t。

mid如果比t小，我们要在mid右边找，mid本身也不可能是。
mid如果比t大，我们要在mid左边找，mid本身也不可能是。

示范代码：

int l=1,r=n;
bool flag=false;                //记录是否找到
while(l<r){
    int mid=(l+r)/2;            //取中间
    if(a[mid]<t){     
        l=mid+1;                //把范围更新为[mid+1,r]  
    }else if(a[mid]>t){
        r=mid-1;                //把范围更新为[l,mid-1]
    }else{
        cout<<mid;              //a[mid]==t，直接输出位置
	flag=true;
	break;
    }
}
if(flag==false){                //并没有找到
    cout<<-1;
}

例如本例使用循环遍历，时间为6。
使用二分，找2次就可以找到了。
二分的时间复杂度是O(logn)。

姜宇轩在2022-05-30 19:34:05追加了内容

无限循环（**循环）

众所周知，c++中有两种循环，一种是for循环，一种是while循环。
两种**循环方式：

1.用for循环写**循环：

for(;;){          //只写两个分号
    ......
}

2.用while循环写**循环：

while(true){
    ......
}

很水啊！对吧

@酷町扫地僧 @酷町猫 @酷町侠 

能申精吗？

姜宇轩在2022-05-31 18:51:35追加了内容

为什么我这么用心，却没人看？

呜呜呜~~~

姜宇轩在2022-05-31 19:06:19追加了内容

        常用函数（一，以后会更更多）

1.判断字符串是否为回文串：

bool check(string s){        
    int i=0,j=s.size()-1;     //双指针
    while(i<j){
        if(s[i]!=s[j]){       //有相对应的字符不相同
            return false;     //不是回文串
        }
    }
    return true;              //是回文串
}

2.判断数字是否是质数：

bool check(int n){
    if(n<=1) return false;          //1和0都不是质数
    for(int i=2;i<=sqrt(n);i++){ 
        if(n%i==0) return false;    //能整除，不是质数
    }
    return true;                    //是质数 
}

3.在数组第i个元素后插入新元素k：

void InSert_(int a[],int i,int k,int n){   //数组名，插入元素的位置，插入的元素，数组原本大小
    n++；                                  //插入元素，数组大小变化
    for(int j=n+1;j>=i+1;j--){
        a[j]=a[j-1];
    }
    a[i]=k;                                //插入元素
}

4.把数组中第i个元素删除：

void ErAse(int a[],int i,int n){  //数组名，删除位置，大小
    for(int j=i;j<n;j++){
        a[j]=a[j+1];
    }
    n--;                         //改变数组大小
}

球球各位同学帮帮忙，马上就要突破10个赞了！！！申精申精！！！回复，评论，点赞，分享都是对我最大的支持！此系列若无人白**，结贴！注：此贴大佬别**，都是给一些刚刚学c++的新手看的，大佬可以参考！我不明白为什么看的人这么少，回复，评论，点赞，分享的人这么少，我发的帖子可能不好，有漏洞，错误，请大家指出！我不明白我是不是和这类帖子无缘，给我建议我都会尽可能去改变，改善，改良，改进！希望各位同学能多参与，多评论！！！

 

姜宇轩在2022-05-31 19:14:47追加了内容

这个帖子可能要废了

正如你看到的，这个帖子可能（一定）要废了。我每天会花半个小时至一个小时完成并改良1~3篇分享，但没人看！我自认为应该是我不擅长这类教学类的帖子，我也会觉得是我帖子的风格不和同学们口味，但我已经尽力了，希望各位同学能指出我帖子的不足与缺点，我会尽自己最大力量改善，改变，改良，改进！现在的存稿还有5~7篇，我也想是不是因为我有时候会拖更？我貌似在问答中不是一个大人物，不是一个人人皆知的大佬。我其实不希望自己声誉大，只希望能给同学们送去好的教学，不详细，不专业，似乎只是为了自己很娱乐似的。

请大家指出不足，提出建议！！！