标签 C/CPP 下的文章

前言
指针是很多人在学习C语言路上所遇到的一个极难的障碍,有许多人都因为无法理解指针而放弃了学习C语言。我个人一开始也是完全无法理解指针,在刻苦钻研半年后,我终于完全理解了指针这一语法难点。下面我就指针的理解与应用进行详细的讲解~~

指针是什么
很多初学者可能无法理解这些问题:指针是什么?为什么要用指针?用指针有什么好外?为什么scanf里的参数要用指针,而printf却要用变量名?
首先,指针本身是个变量,存储内容是一个地址,这一点已经令人很难理解了。我们需要明白,所谓“内存条”物理上真的就是一条,各种数据占据了不同的位数。因此,我们可以给每个内存都标一个地址,这样计算机就能更好地访问数据(别问我为什么,可以自己想一下,如果全世界都没有门牌号,你访问某人的家会不会更麻烦)。地址(指针)是十六进制数,标号顺序相当于从0号开始不断增加,说的明白些,地址就是从内存条第一格开始数,到当前格是几格。
如果你有了一个变量的指针,那么你就可以用指针来访问这个地址来改变其值,那这样来说,我们是否可以直接用地址来访问并更改某个变量呢?答案是肯定的。下面是一个例子:

#include <stdio.h>
main(){
    int a=0;
    int *p=&a;/*定义指针变量p,并赋值为a的地址*/
    *p=1;
    printf("%d",a);/*输出结果应为1*/
    return 0;
}

在C语言中,用*指针变量名的形式表示指针变量指向地址的值。
这样我们就可以解释为什么printf的参数是变量的值,而scanf的参数是指针了:printf输出变量时只需要变量的值,与变量的地址无关;而scanf则要改变变量的值,只有变量的值并不能改变它,必须得到它的地址。

用指针写个函数
指针的用处非常大,下面我们用指针写个简单的小程序:交换变量值的函数。

/*不批注了,自己看吧*/
#include <stdio.h>
void swap(int *a,int *b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
    return ;
}
main(){
    int x,y;
    scanf("x=%d,y=%d",&x,&y);
    swap(&x,&y);
    printf("x=%d,y=%d",x,y);
    return 0;
}
但是如果把程序写成下面这样:

include <stdio.h>

void swap(int a,int b){

int t;
t=a;
a=b;
b=t;
return ;

}
main(){

int x,y;
scanf("x=%d,y=%d",&x,&y);
swap(a,b);
printf("x=%d,y=%d",x,y);
return 0;

}
那么x和y的值最后不会被交换,因为swap函数里的代码只是交换了参数a,b的值,作用域在函数内,对main函数里的变量没有任何影响。

指针进阶版——函数指针
指针可以指向变量,那么也可以指向函数,下面是一个示例:

/*使用指针变量及可变参数,写一个任意参数数量的比较程序*/
#include <stdio.h>
#include <stdarg.h>
int compare(int (*cmp)(int,int),int num,...){
    va_list valist;
    va_start(valist,num);
    int ans=va_arg(valist,int),i=0;
    while(++i<=num) ans=cmp(ans,va_arg(va_list,int));
    return ans;
}
/*下面定义了两个常用cmp函数(取大值和取小值)*/
int MAX_CMP(int a,int b){
    if(a>=b) return a;
    else return b;
}
int MIN_CMP(int a,int b){
    if(a<=b) return a;
    else return b;
}
/*也可以自定义需要的cmp函数*/
main(){
    int t,a,b,c,d;
    scanf("%d%d%d%d%d",&t,&a,&b,&c,&d);
    switch(t){/*用户选择取最大、最小值*/
        case 1:
            printf("%d",compare(MAX_CMP,4,a,b,c,d);
            break;
        case 2:
            printf("%d",compare(MIN_CMP,4,a,b,c,d);
            break;
    }
    return 0;
}

(这个compare函数可以自己开个文档存着,需要时拿出来微调一下即可~)

结语
本文介绍了C语言中对指针的使用,用简单的程序帮助学习者了解指针的用法。我是faryou,下次见!(好久没写正经的文章了,肝了一个多小时,还是用平板写,心疼下高中生吧~)

前言
今天我们学习另一种DP——区间DP。

程序设计思路
(由于无法从概念上描述题意,这里直接放题目~)
202409081725774600907409.png
题意很好理解,要求我们求出合并所有石堆的最小代价。
首先思考一维DP式,很容易想到将dp[i]定义为合并从第一堆石子到第i堆石子所花费的代价。但是,状态转移方程怎么办?!由于本题中合并的顺序不唯一,第一堆石子也有可能最后合并,所以这个方法不可行。
这个时候我们需要思考一下:某个区间的最小代价一定是这个区间分为2个区间后这两个区间的代价之和。这样我们可以得到二维DP的定义:dpi代表从第i堆到第j堆石子合并所需要的最小代价。然后再思考,不难得到:我们可以对某个区间进行分割,这个分割点就是我们要去找的。故我们可以列出以下方程:dpi=min(dpi,dpi+dpi+k+1+s[j]-s[i-1](s[i]为从第一堆石子到第i堆石子代价的前缀和,用来累加代价,自行理解,另外需要预处理)。最后一个问题:dpi如何初始化?首先如果只有一堆那合并的代价为0,故dpi=0,而由于我们求最小代价,dp[i]j可以初始化成一个很大的数,方便比较操作。

代码实现

#include <stdio.h>
#include <memory.h>
//今天想重温一下C语言,故用C语言
int n,m[1001],dp[1001][1001],s[1001];//均如题意或已讲解

int min(int a,int b){//C语言没有min函数,所以手搓一个
    if(a<b) return a;
    else return b;
}

main(){
    scanf("%d",&n);
    memset(s,0,sizeof(s));
    memset(dp,0x3f3f3f3f,sizeof(dp));//初始化为大数
    for(int i=1;i<=n;i++) dp[i][i]=0;
    for(int i=1;i<=n;i++) scanf("%d",&m[i]);
    for(int i=1;i<=n;i++) s[i]=m[i]+s[i-1];//计算前缀和
    for(int len=1;len<=n;len++) for(int i=1;i<=n;i++){//len为长度,先计算长度为1的区间之后逐渐累加并重叠
        int j=i+len-1;
        if(j>n) break;//防越界
        for(int k=0;k<len;k++) dp[i][j]=min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+s[j]-s[i-1]);//dp式
    }
    printf("%d",dp[1][n]);
    return 0;
}

可以看到,区间DP的代码很简洁,所以重在理解~

结语
区间DP没有变式,其O(n3)的时间复杂度也无法进行优化,理解即可。我是faryou,再见!

前言
广度优先搜索适合用于解决一些走迷宫之类的问题,可以解决深度优先搜索“搜得太深一时出不来”的问题。今天我们学习一下BFS的基本思路。

程序设计思路
BFS与DFS不同就在于BFS是按照层次遍历(在树上表现为从上到下一层一层,横向遍历),而DFS则是有多深走多深,不管层数。理论上来说,两者都属于暴力。
BFS通过队列实现,即每次从队列中取出一个点进行相关操作,并在这次循环内察看其子节点是不是叶子节点,如果是非叶子节点就把这个点入队,之后将这个父节点出队,处理下一个点,直到处理完所有节点(队列空),实现遍历。
还是下面这棵树:
202408311725079771374628.png
使用BFS的遍历顺序为:2→7→8→1→6→9→5→3→4。

代码实现
来看一道题:
202408311725083121921990.png
这是一道经典的BFS题目,我们可以将马不同的行走路线看成一棵树上不同的分支。直接上代码——

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

int n,m,x,y,ans[401][401],ssb[9]={0,-2,-2,-1,-1,2,2,1,1},sbb[9]={0,-1,1,-2,2,-1,1,-2,2},iq,aq;//n、m、x、y如题意,ans存放从起点到各个点的最短路径,iq、aq为临时变量
bool visit[401][401];//记录当前点有没有访问过

int main(){
    queue<int> f1,f2;//队列,分别记录f1与f2
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=-1;
    f1.push(x);
    f2.push(y);//先将起点入队,开始计算
    ans[x][y]=0;//起点到起点距离为0
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) visit[i][j]=false;//初始化
    visit[x][y]=true;//已经访问过起点
    while(!f1.empty()){//循环直到队列空
        iq=f1.front();
        aq=f2.front();//取出x、y分别计算
        f1.pop();
        f2.pop();//出队
        for(int i=1;i<=8;i++){//马下一步可以到八个方向
            int nexx=iq+ssb[i];
            int nexy=aq+sbb[i];//临时变量记录
            if(nexx>0 && nexy>0 && nexx<=n && nexy<=m && !visit[nexx][nexy]){//判断是否超界或访问过
                visit[nexx][nexy]=true;//当前点标记
                ans[nexx][nexy]=ans[iq][aq]+1;
                f1.push(nexx);
                f2.push(nexy);//进队列
            }
        }
    }
    for(int i=1;i<=n;i++){//输出
        for(int j=1;j<=m;j++) printf("%-5d",ans[i][j]);
        printf("\n");
    }
    return 0;
}

再来看下面这题:
202408311725083785844735.png
这题可以视作遍历二叉树,即上楼和下楼分别为节点。看代码:

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

struct node{//floor存放一层,d存放到该层的步数
    int floor,d;
}now;

int n,a,b,k[201],dist;//n、a、b、k如题意,dist为临时变量
bool vis[201];//记录是否到达
queue<node> iq;//队列

int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&k[i]);
        vis[i]=false;
    }//初始化+读入
    iq.push((node){a,0});//起点入队
    vis[a]=true;//起点已访问过
    while(!iq.empty()){//循环直到队列空
        now=iq.front();//存放这次循环要处理的点
        iq.pop();//出队
        if(now.floor==b) break;//当已经到达终点时,退出循环。由于广搜可以保证搜索的步数逐渐增加,所以不会漏掉步数更少的情况
        dist=now.floor-k[now.floor];//临时记录(下楼)
        if(dist>=1 && dist<=n && !vis[dist]){//判断未超界且未访问过
            iq.push((node{dist,now.d+1}));//入队
            vis[dist]=1;//标记
        }
        dist=now.floor+k[now.floor];//临时记录(上楼)
        if(dist>=1 && dist<=n && !vis[dist]){//同上
            iq.push((node{dist,now.d+1}));
            vis[dist]=1;
        }
    }
    if(now.floor==b) printf("%d",now.d);
    else printf("-1");
    return 0;
}

这里注意不要忘记开vis数组,否则可能会死循环(出现环状结构时)。

结语
BFS是很重要的一个算法,只要想清楚自己的树是怎么样的就可以轻松完成程序。我是faryou,再见!

前言
搜索是算法学习者经常会用的一种算法,本质上是暴力算法的一种优化。我们在初期经常会用到BFS和DFS。今天我们来学习DFS。

什么是递归
简单来说,就是函数自己调用自己。因为函数在运行过程中产生的数据通常是存放在栈中的,所以它可以在递归开始返回后将最后一次入栈的数据出栈,再回到上一个程序。来看一个具体的例子:
202408191724059642553302.png
本题很简单,但是也可以不用循环做,可以使用递归:

#include <bits/stdc++.h>

int times(int n){//递归程序
    if(n==1) return 1;
    else return n*times(n-1);//自己调用自己
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",times(n));
    return 0;
}

这里程序在函数中不断调用自己,直到n=1时开始回归,巧妙的实现了从1乘到n。
需要注意的是,递归在使用过程中会有损耗,故在时间复杂度相同时会慢于普通循环。

程序设计思路
首先我们要明白搜索都是基于树论的。你想要使用搜索,就必须先自己构造出一棵树。
202408191724022847421665.png
如上图所示,就是一棵树的图形表示。
与BFS不同,DFS的原则是“不撞南墙不回头”,因此如果使用DFS对上面的树进行搜索,顺序应该是:2→7→1→6→5→3→8→9→4。
由于图片中展示的是一棵二叉树,而实际问题中树的子树数量不是固定的,所以通常会使用递归的方式写程序。

代码实现
下面是一个例子:
202408191724061868280978.png
这是一道典型的DFS的题目。在这题中,由于两个皇后肯定不会在同一行,我们可以对每一行可能出现的情况进行枚举,再进行判断。于是问题就变成了要遍历n棵n叉树并判断。下面是代码——

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

int n,ans=0,out[14];//ans用于累加,out数组存放要输出的答案
bool flag;//用于记录是否有答案

void dfs(int step){//step为行数
    if(step>n){//出口程序
        ans++;
        if(ans<=3){//输出前三个答案
            for(int i=1;i<=n;i++) printf("%d ",out[i]);
            printf("\n");
        }
    }
    for(int i=1;i<=n;i++){
        flag=true;//初始化flag
        for(int j=1;j<step;j++) if(out[j]==i || abs(i-out[j])==step-j){//前一个条件判断纵向,后一个条件判断是否处于同一45°角上。
            flag=false;//当不满足条件时,将答案标记为错误并直接跳出循环不再判断(剪枝)
            break;
        }//用之前放置的所有皇后进行判断
        if(!flag)continue;//当答案不正确时,进入下一循环
        out[step]=i;//存下答案
        dfs(step+1);//进行下一层判断
    }
    return ;
}

int main(){
    scanf("%d",&n);
    dfs(1);
    printf("%d",ans);
    return 0;
}

这里我们使用递归不断调用自己,达到一个函数搞定的效果。再来看一个例子:
202408311725085714602356.png
这题也是经典的地图搜索题,上代码:

#include <bits/stdc++.h>

int r,c,n,a,b,iq[1010];//r、c、n如题意,a、b用来存放起点坐标,iq[i]为第i次操作的方向编号(1、2、3、4分别代表东、南、西、北)
char Map[55][55],input[6];//Map用于存地图,input用来输出操作的内容
bool ans[55][55],flag[55][55][1010];//ans存放能否到达坐标对应点,flag[i][j][k]存放是否在第k步到达(i,j)(记忆化)
void dfs(int num,int x,int y){//num代表递归层数,x、y代表要进行搜索的坐标
    if(flag[x][y][num]) return ;//如果当前点已经算过则返回
    if(num>=n){//当层数大于步数时退出计算
        ans[x][y]=true;
        return ;
    }//以下为分类讨论
    int i=x,j=y;
    if(iq[num]==1) while(1){//当下一步向东走时,横坐标不断加1直到超界或撞墙
        j++;//一步一步走
        if(j>=c || Map[x][j]=='X') break;//判断超界或撞墙
        dfs(num+1,x,j);//计算下一步
    }
    if(iq[num]==2) while(1){//同上
        i++;
        if(i>=r || Map[i][y]=='X') break;
        dfs(num+1,i,y);
    }
    if(iq[num]==3) while(1){//同上
        j--;
        if(j<0 || Map[x][j]=='X') break;
        dfs(num+1,x,j);
    }
    if(iq[num]==4) while(1){//同上
        i--;
        if(i<0 || Map[i][y]=='X') break;
        dfs(num+1,i,y);
    }
    flag[x][y][num]=true;//将当前位置标记为已走过
    return ;
}

int main(){
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) ans[i][j]=false;
    for(int i=0;i<r;i++) scanf("%s",Map[i]);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) if(Map[i][j]=='*'){
        a=i;
        b=j;
    }
    scanf("%d",&n);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) for(int k=0;k<n;k++) flag[i][j][k]=false;
    for(int i=0;i<n;i++){//每读入一个操作就转义为数字操作编号
        scanf("%s",input);
        if(input[0]=='E') iq[i]=1;
        if(input[0]=='S') iq[i]=2;
        if(input[0]=='W') iq[i]=3;
        if(input[0]=='N') iq[i]=4;
    }
    dfs(0,a,b);//从(a,b)出发
    for(int i=0;i<r;i++){//输出
        for(int j=0;j<c;j++){
            if(Map[i][j]=='X') printf("X");
            else if(ans[i][j]) printf("*");//如果该点可以到达,输出'*'
            else printf(".");
        }
        printf("\n");
    }
    return 0;
}

这题要我们对地图进行计算,还是很好理解的。这里我加上了记忆化,效率更高。

DFS的优化——剪枝
剪枝,顾名思义,就是通过程序方法直接排除一些子树,以求提高效率。主要分为可行性剪枝和奇偶性剪枝。
可行性剪枝,就是从题目意义上将某些不可能的情况排除。比如说,要计算一个人能不能在规定时间刚刚好走到某个格子(路线不能重复),如果你在搜索的过程中碰到一种情况:这张地图上所有格子的总数比单位时间内可以走的路程还要少,那根本就不用算了,直接false!
还有一种奇偶性剪枝。我们可以将一张地图看成这样:
0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0
在这张图上,从0走到1或从1走到0肯定要奇数步,从0走到0或从1走到1肯定要偶数步。所以如果碰到这种平面图算步数的搜索题也可以直接用奇偶性pass一部分。
剪枝的具体代码可以是多样化的,但是其中心目的只有一个——减少搜索量。

记忆化DFS
DFS在调用的递归嵌套过多时会爆栈,因此我们可以为其加上记忆化以防超界。记忆化是指在一棵树中,可能会有重复的子树,导致重复计算,所以我们可以使用数组将一种情况记录下来,下次再碰到这个情况直接跳过计算,以减少调用。
记忆化DFS是一种以更高的空间复杂度换取更低的时间复杂度的方法。当代码面临TLE时,不妨试试加上记忆化。例如上面案例中的第二题就是利用了flag数组,减少了运算量。当然,在加记忆化时也要注意空间复杂度不能过高,否则爆空间~

总结
从理论上来说,DFS和DP问题是可以互相转化的,只要学好一个,两者的问题都能解决。所以,如果你还在为了列出状态转移方程而苦恼,不妨试试用DFS的思路去思考DP问题。不过,普通的DFS容易因循环过多而爆栈,为了解决这个问题,我们需要用到优化版DFS——记忆化DFS。我是faryou,再见!

前言
最短路径是求在一张有向图中,起点到终点的距离。求最短路径的方法有很多,如SPFA、floyd、dijkstra等,今天我们学习dijkstra的思路与代码,其优点是时间复杂度和空间复杂度都很低,缺点是不能处理重边。

程序设计思路
dijkstra基于贪心实现,又有点类似DP,其思路大致如下:先把起点到所有点的距离都设为inf(一个很大的数),然后在所有与起点相连接的边中找到最短的一条,将这个新的点作为起点,并更新从起点出发到这个点的最短距离,直到找到终点。这个逐步更新的操作被称为松弛。

代码实现
202408311725062861878389.png
洛谷上还有一道数据随机的模板题,这题专卡SPFA,但对我们的dijskla没有影响,下面是代码:

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

struct Edge{//结构体用来存一条边的起点、终点、长度
    int to,dis,ne;
}edge[2000005];

int n,m,s,cnt,dist[2000005],head[2000005],x,y,z;//n、m、s如题意,cnt用来计数,dist存起点到各个点的最短距离
bool visit[2000005];//类似BFS中记录已经访问的点

void Add_edge(int from,int to,int w){//加入数组
    edge[++cnt].to=to;
    edge[cnt].dis=w;
    edge[cnt].ne=head[from];
    head[from]=cnt;
}

struct node{
    int id,dis;
    bool operator <(const node &a)const{ return a.dis<dis; }//优先队列升序排序
};
void dijkstra(){
    priority_queue<node> q;
    q.push(node{s,0});
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;
    while(!q.empty()){
        node a=q.top();
        q.pop();//类似BFS的队列
        int now=a.id;
        if(visit[now]) continue;
        visit[now]=1;
        for(int i=head[now];i;i=edge[i].ne){//查所有边
            int j=edge[i].to;
            if(dist[now]+edge[i].dis<dist[j]){//判断走的这条路是不是比原来的更短
                dist[j]=dist[now]+edge[i].dis;
                q.push(node{j,dist[j]});
            }
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Add_edge(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++) printf("%d ",dist[i]);
    return 0;
}

结语
dijkstra不能处理重边,这一点在选择方法时需要注意。我是faryou,再见!