【2023.3.5】MOOC程序设计与算法笔记

三、二分算法

1-BinarySearch函数

#include
//在包含size个元素的、从小到大排序的int数组a里查早元素p。
//如果找到，则返回元素下标。否则返回-1。复杂度O(log(n))
int BinarySeach(int a[], int size, int p) {int L = 0;int R = size - 1;while (L <= R) {int mid = L + (R - L) / 2;if (a[mid] == p) {return mid;}if (a[mid] > p)R = mid - 1;elseL = mid + 1;}return -1;
}int main() {int a[] = { 0,1,3,4,6,7,9,11,15,18 };int n;printf("input:");scanf("%d", &n);int i = BinarySeach(a, 10, n);printf("a[%d]=%d\n",i, a[i] );return 0;
}

四、分治

把一个任务分成形式与原任务相同、规模更小的多个任务，分别完成。

1-归并排序

一般用递归实现。

菜鸟教程：归并排序：含动图解释。

#include
#includevoid MergeSort(int* a, int n);
void Merge(int* a,  int mid, int end);int main() {int a[100] = { 2,4,5,8,1,14,9,12,15,33,3 ,44,22,11,33};int len = 0;for (len = 0; a[len]; len++);printf("%d\n", len);MergeSort(a, len);for (int i = 0; i < len; i++)printf("%d ", a[i]);
}void MergeSort(int* a, int n) {if (n <= 1) {return;}MergeSort(a, n / 2);MergeSort(a + n / 2, n - n / 2);Merge(a,  n / 2, n  );}
void Merge(int* a,  int mid, int end) {int* b = (int* )malloc(end*sizeof(int));int i = 0, j = mid;int k = 0;while (i < mid && j < end) {if (a[i] < a[j]) {b[k++] = a[i++];}else {b[k++] = a[j++];}}while (i < mid) {b[k++] = a[i++];}while (j < end) {b[k++] = a[j++];}for (i = 0; i < k; i++)a[i] = b[i];free(b);
}

2-快速排序

i 和 j 同时往中间移动。

#include
#includevoid QuickSort(int* a, int n);
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}int main() {int a[100] = { 22,11,33,2,4,5,8,1,14,9,12,15,55,3 ,44};int len = 0;for (len = 0; a[len]; len++);printf("%d\n", len);QuickSort(a, len);for (int i = 0; i < len; i++)printf("%d ", a[i]);
}void QuickSort(int* a, int n) {if (n <= 1)return;int k = a[0];int i = 0, j = n - 1;while (i != j) {while (i < j) {if (a[j] >= k)j--;else {swap(a + i, a + j);break;}}while (i < j) {if (a[i] <= k) {i++;}else {swap(a + i, a + j);break;}}		}//printf("i=%d,j=%d\n", i, j);//重点：此时再将i左边和右边分开快速排序，所以要减一加一,避开第i个。QuickSort(a , i);QuickSort(a + i + 1, n - i-1);
}

五、深度优先搜索

1-基本模型-通用套路

深度优先搜索dfs基本模型-通用套路：摘自：深度优先搜索DFS-C语言实现、思路/解析-简笔

void dfs(step)
{/*1.判断边界，判断本阶段的DFS是否已经结束了*/if(foo == bar){/*Do something*/return ;}/*2.尝试每一种可能，类似于走迷宫中的在每一个点尝试每个方向*/for(i=0;i<_MAX_;++i){do_something();dfs(step+1);//进行下一步undo_something();}return ;
}

2-迷宫问题

已知迷宫地图，输出迷宫的路程解和步数。

//10*10迷宫地图
//S表示起点，E表示出口，#表示墙，O表示路
//该地图有两个解
char map[N + 1][N + 1] = {{"SO##OOO###"},{"#OOOO#OOO#"},{"#O##O###O#"},{"OOO#OO##O#"},{"O#O##OO###"},{"O#####O###"},{"O#OOOOO###"},{"OOO#O#####"},{"###OOO#OOE"},{"##OO#OOO##"},
}; 

通过dfs跑出迷宫答案

dfs，深度优先搜索，就是从一个节点一直往深处搜索，直到走到尽头，再往回走，走下一个节点，再次深搜……就相当于来回遍历，一个人走迷宫。

是基于回溯的思想。而回溯就是基于栈结构。

所以有两种写法，一种是直接递归，一种是自己构造堆栈、压栈出栈。

（1）基于递归的写法

不过递归调用，本就是由系统的堆栈支持的。所以也算堆栈结构。

不用自己实现堆栈，实现起来肯定要简单些。

#include
#define Max 50
#define MapN 10//表示N*N迷宫/*该地图唯一解 
//10*10迷宫地图，S表示起点，E表示出口，#表示墙，O表示路
char map[N+1][N+1] = {{"SO##OOO###"},{"#OOOO#OOO#"},{"#O##O###O#"},{"#OO#OO##O#"},{"O#O##OO###"},{"O#####O###"},{"O#OOOOO###"},{"OOO#O#####"},{"###OOO#OOE"},{"##OO#OOO##"},
};*///10*10迷宫地图，S表示起点，E表示出口，#表示墙，O表示路
//该地图有两个解
char map[MapN + 1][MapN + 1] = {{"SO##OOO###"},{"#OOOO#OOO#"},{"#O##O###O#"},{"OOO#OO##O#"},{"O#O##OO###"},{"O#####O###"},{"O#OOOOO###"},{"OOO#O#####"},{"###OOO#OOE"},{"##OO#OOO##"},
}; int Visit[Max][Max] = { 0 };void dfs(int x, int y, int step);
void PrintAns(int Ans[Max][Max], int step);int main() {int startX = 0, startY = 0, step = 0;Visit[startX][startY] = 1;dfs(startX, startY, step);return 0;
}void dfs(int x, int y, int step) {if (map[x][y] == 'E') {PrintAns(Visit, step);return;}for (int i = 0; i < 4; i++) {int NextX = x, NextY = y;switch (i){case 0:NextX += 1; break;case 1:NextX -= 1; break;case 2:NextY += 1; break;case 3:NextY -= 1; break;}if (NextX >= 0 && NextX < MapN && NextY >= 0 && NextY < MapN) {if (map[NextX][NextY] != '#' && Visit[NextX][NextY] != 1) {Visit[NextX][NextY] = 1;dfs(NextX, NextY, step + 1);Visit[NextX][NextY] = 0;}}}}void PrintAns(int Ans[Max][Max], int step) {for (int i = 0; i < MapN; i++) {for (int j = 0; j < MapN; j++) {if (Ans[i][j]) {putchar('*');}else {putchar(' ');}}putchar('\n');}printf("Total Steps:%d\n", step);putchar('\n');}

（2）基于堆栈的写法

基于堆栈结构的写法，（我不大熟悉，尝试着写，写得不好）

后面才知道，c++有现成的stack容器，用于使用堆栈这种数据结构，不用我们自己写压栈、出栈这些函数，

使用教程参考：C语言-stack的应用

#include
#include
#define Max 50
#define MapN 10//表示N*N迷宫//10*10迷宫地图，S表示起点，E表示出口，#表示墙，O表示路
//该地图有两个解
char map[MapN + 1][MapN + 1] = {{"SO##OOO###"},{"#OOOO#OOO#"},{"#O##O###O#"},{"OOO#OO##O#"},{"O#O##OO###"},{"O#####O###"},{"O#OOOOO###"},{"OOO#O#####"},{"###OOO#OOE"},{"##OO#OOO##"},
}; struct StepInStatk {int x;int y;int k;//记录已走过的上下左右，0~3,4表示所有方向已走过int step;//第多少步。StepInStatk* pNext;
};int Visit[Max][Max] = { 0 };//记录改坐标是否已走过。void dfsByStack(StepInStatk* pFirstStep,int step);
void PrintAns(StepInStatk* pStackTop);
StepInStatk* InitStep(int x,int y);//初始化迷宫的起始位置
StepInStatk* PushStepStack(StepInStatk* pStackTop, int x,int y);//压栈
StepInStatk* PopStepStack(StepInStatk* pStackTop);//出栈int main() {int startX = 0, startY = 0;StepInStatk* pFirstStep = InitStep(startX, startY);Visit[startX][startY] = 1;dfsByStack(pFirstStep, 0);return 0;
}void dfsByStack(StepInStatk* pFirstStep, int step) {StepInStatk* pStackTop = pFirstStep;while (1) {int i;for (i = pStackTop->k; i < 4; i++) {int NextX = pStackTop->x;int NextY = pStackTop->y;switch (i){case 0:NextX += 1; break;case 1:NextX -= 1; break;case 2:NextY += 1; break;case 3:NextY -= 1; break;}if (NextX >= 0 && NextX < MapN && NextY >= 0 && NextY < MapN) {if (Visit[NextX][NextY] == 0 && map[NextX][NextY] != '#') {Visit[NextX][NextY] = 1;//标记这个位置已走过。pStackTop->k = i + 1;//迷宫的走法上下左右，k表示下一次应走的方向，k=4时表示4个方向皆走过了。pStackTop = PushStepStack(pStackTop, NextX, NextY);break;}}}if (map[pStackTop->x][pStackTop->y] == 'E') {//找到出口PrintAns(pStackTop);Visit[pStackTop->x][pStackTop->y] = 0;pStackTop = PopStepStack(pStackTop);}else if (i == 4) {//表示该节点的四个方向都已经走过了，已无路可走，需要回溯。Visit[pStackTop->x][pStackTop->y] = 0;pStackTop = PopStepStack(pStackTop);}if (pStackTop == NULL)//只有当栈底，也就是第一个起始节点的四个方向都遍历完，才会pop出栈，使pStackTop指向NULL。break;}
}StepInStatk* InitStep(int x, int y) {StepInStatk* pFirstStep = (StepInStatk*)malloc(sizeof(StepInStatk));pFirstStep->x = x;pFirstStep->y = y;pFirstStep->k = 0;pFirstStep->step = 0;pFirstStep->pNext = NULL;return pFirstStep;
}StepInStatk* PushStepStack(StepInStatk* pStackTop, int x, int y) {StepInStatk* pStep = (StepInStatk*)malloc(sizeof(StepInStatk));pStep->x = x;pStep->y = y;pStep->k = 0;pStep->step = pStackTop->step + 1;pStep->pNext = pStackTop;return pStep;
}
StepInStatk* PopStepStack(StepInStatk* pStackTop) {return pStackTop->pNext;
}void PrintAns(StepInStatk* pStackTop) {StepInStatk* pStep = pStackTop;int Ans[MapN+1][MapN+1] = { 0 };int step = pStackTop->step;while (pStep != NULL) {Ans[pStep->x][pStep->y] = 1;pStep = pStep->pNext;}for (int i = 0; i < MapN; i++) {for (int j = 0; j < MapN; j++) {if (Ans[i][j]) {putchar('*');}else {putchar(' ');}}putchar('\n');}printf("Total Steps:%d\n", step);putchar('\n');}

六、广度优先搜索BFS

广度优先算法，基于队列的数据结构。

学习视频:B站：洛谷 普及组试炼场 - 广度优先搜索 （BFS)

0-quene队列的使用

使用队列数据结构，c++里有现成的容器queue。

queue的使用案例：C语言-队列(queue)的应用

#include 
#include 
using namespace std;int main(){queue q;for(int i = 0; i < 5; i++){q.push(i);cout << "成功将" << i << "入队" << endl;}cout << endl;while(!q.empty()){cout << "当前队首：" << q.front() << "\t当前队尾：" << q.back();cout << "\t当前队列大小：" << q.size() << endl;q.pop();}return 0;
}

1-洛谷P1162 填涂颜色

洛谷：P1162 填涂颜色

#include 
#include 
using namespace std;struct location {int x;int y;
};
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,1,0,-1 };
int aa[40][40] = { 0 };
int visit[40][40] = { 0 };
int main() {int n = 0;cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> aa[i][j];}}queue queue;location Temp = { 0,0 };queue.push(Temp);visit[0][0] = 1;while (!queue.empty()) {for (int i = 0; i < 4; i++) {int dx = queue.front().x + xx[i];int dy = queue.front().y + yy[i];if (dx >= 0 && dx <= n + 1 && dy >= 0 && dy <= n + 1) {if (visit[dx][dy] == 0 && aa[dx][dy] == 0) {visit[dx][dy] = 1;Temp.x = dx;Temp.y = dy;queue.push(Temp);}}}queue.pop();}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (visit[i][j] == 1 || aa[i][j] == 1) {cout << aa[i][j] << " ";}else {cout << "2 ";}}cout << endl;}return 0;
}

2-洛谷P1443 马的遍历

洛谷：P1443 马的遍历

#include 
#include 
using namespace std;struct location {int x;int y;int s;//表示步数，第几步
};
int xx[] = { 1, 1, 2, 2,-1,-1,-2,-2};
int yy[] = { 2,-2, 1,-1, 2,-2, 1,-1};
int map[402][402] = { -1 };
int visit[402][402] = { 0 };
int main() {int n, m, x, y;cin >> n >> m >> x >> y;//全部置为-1，表示这些点没有访问过。for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {visit[i][j] = -1;}}queue queue;visit[x][y] = 0;queue.push( { x, y, 0 });//这样push也是一个结构体数据。while (!queue.empty()) {for (int i = 0; i < 8; i++) {int dx = queue.front().x + xx[i];int dy = queue.front().y + yy[i];if (dx >= 1 && dy >= 1 && dx <= n && dy <= m) {if (visit[dx][dy] == -1) {location temp = { x,y,0 };temp.x = dx;temp.y = dy;temp.s = queue.front().s + 1;//BFS的特性，其队列首部和尾部的一定是相邻步骤数，相差为1.queue.push(temp);visit[dx][dy] = temp.s;//记录马访问该点时的步骤数量。}}}queue.pop();}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << visit[i][j] << ' ';}cout << endl;}return 0;
}