问题标题: 刚回归

H2-v4-阶段3-课时5-迷宫问题-课后讲义

本节课思维导图

一、搜索与回溯

 
  搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，但是可以利用搜索与回溯的技术求解。
  回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
 

二、回溯法框架

void dfs(int k) { if(到目的地) 输出解 //边界条件 else for (i=1;i<=算符总数;i++) //枚举所有可能性 if (满足条件){ //约束条件 保存结果和状态 dfs(k+1); //递归搜索 恢复保存结果之前的状态 //状态恢复 } } }

三、迷宫问题

  我们现在来看一下经典的迷宫问题。
  在一方形迷宫中有n*m个格子，我们知道闯迷宫的人的初始坐标 (sx,sy) 以及目标出口 (tx,ty)，以及迷宫中若干障碍物的坐标。每次我们可以向上、下、左、右的格子做一次移动，让我们判断是否能够到达迷宫出口，或者统计到达迷宫出口的方案数。

用void dfs(int x,int y)表示走到(x,y)格子。

1. 边界条件（递归的终点）

  当到达出口 (tx,ty) 时结束

if(x==tx && y==ty) { 输出解/计数/标记； return; }

2. 枚举所有可能性

  从（x,y）往上、下、左、右分别探索

dfs(x-1,y); dfs(x+1,y); dfs(x,y-1); dfs(x+1,y-1);

  或

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; for(int i=0;i<4;i++){ int nx=x+dir[i][0],ny=y+dir[i][1]; dfs(nx,ny); }

3. 约束条件

①不能走到障碍处

  这可通过输入的地图信息来判断。比如将地图信息用一个二维数组map[x][y]来存储，map[x][y] = 1表示障碍，map[x][y] = 0表示道路。

②不能走出地图边界

  如果地图的大小为m*n，且左上角格子下标为（1,1），则到达的坐标（x,y）要满足1<=x<=m, 1<=y<=n

③已经走过的位置不能再走

  已经走过的位置我们可以通过一个全局的二维数组vis[x][y]来记录。其中可以用vis[x][y] = 1表示(x, y)这个位置已经走过，vis[x][y] = 0表示(x, y)这个位置未走过。

if(map[x][y]==0 && vis[x][y]==0 && x>=1 && x<=m && y>=1 && y<=n){ (x,y)可以走; }

四、课堂练习

1401 迷宫

/* 1401 迷宫 n*m的迷宫 T个障碍物 起点——>终点的方案数 每个方格最多经过1次——>同一个路线，走过的不能走 规则：上右下左四个方向，按顺序去查找 【样例】 3 3 2 1 1 3 1 1 3 2 1 结果为2 注意：①回到起点之后结束了吗？ ——>没有，起点的四个方向都判断完才结束 ②什么时候回溯？ 1、走到终点 2、无路可走 方向数组 */ #include<iostream> using namespace std; int n,m,t,cnt; int sx,sy,ex,ey; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; bool g[10][10];//标记是不是障碍物 bool vis[10][10];//标记有没有走过 void dfs(int x,int y){ //边界 if(x==ex&&y==ey){ cnt++; return ; } //遍历四个方向，判断能不能走 for(int i=0;i<4;i++){ int nx=x+dir[i][0]; int ny=y+dir[i][1]; //判断可不可以走 if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]==0&&vis[nx][ny]==0){//未越界&&不是障碍物&&没走过 //递归之前进行标记 vis[nx][ny]=1; dfs(nx,ny); //回溯——>撤销标记 vis[nx][ny]=0; } } //无路可走 return ; } int main(){ cin>>n>>m>>t; cin>>sx>>sy>>ex>>ey; //输入障碍物 while(t--){ int u,v; cin>>u>>v; g[u][v]=1; } //起点最开始要被标记******* vis[sx][sy]=1; dfs(sx,sy); cout<<cnt; return 0; }

4956 棋盘（2）

#include<iostream> using namespace std; int n,t; bool flag; bool g[10][10];//表示可不可以走 1表示可以走 bool vis[10][10];//标记走没走过 int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; void dfs(int x,int y){ //剪枝优化 if(flag==true){ return ; } //边界——>走到终点 if(x==n&&y==n){ flag=1; return ; } //遍历四个方向 for(int i=0;i<4;i++){ int nx=x+dir[i][0]; int ny=y+dir[i][1]; //未越界&&可以走&&没走过 if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&g[nx][ny]==1&&vis[nx][ny]==0){ vis[nx][ny]=1; dfs(nx,ny); vis[nx][ny]=0; } } //无路可走 return ; } int main(){ cin>>n>>t; while(t--){ int a,b,c; cin>>a>>b>>c; g[a][b]=1; } //起点标记 vis[1][1]=1; dfs(1,1); cout<<flag; return 0; }

3020 道路施工

#include<bits/stdc++.h> using namespace std; int a,b,N,cnt,x,y; int dir[4][2]={{1,0},{0,1}}; bool g[20][20];//是否有障碍物 bool vis[20][20];//是否是回头路 void dfs(int x,int y){ if(x==a&&y==b){ cnt++; return ; } for(int i=0;i<2;i++){ int dx=x+dir[i][0],dy=y+dir[i][1]; if(dx>=1&&dx<=a&&dy>=1&&dy<=b&&!vis[dx][dy]&&!g[x][y]){ vis[dx][dy]=true; dfs(dx,dy); vis[dx][dy]=false; } } return ; }

H2-v4-阶段3-课时4-实数域上的二分及二分综合应用-课后讲义

本节课思维导图

一、 实数域上的二分

  有些情况中，我们需要在某个范围中查找一个小数值。并且如果答案具有单调性，则我们可以使用二分查找。

  首先在实数域上的二分查找中，我们不能再以l等于r作为循环的终止条件。因为两个小数不能准确判断相等。所以我们改用l和r的距离小于精确度eps来终止循环。这时l和r的更新直接更新到mid位置即可。

  当精确到小数点后k位时，eps通常取10-(k+2)。

二、 课堂题代码

2886 Pie

/* 分析题意： 有n个派，每个派都有一个半径，每个派都是一个高为1 有p个朋友，加上自己有p+1个人 每个人都会一块派但不能 几个派的小块拼成 问：每个人拿到的派最大是多少？ 分析： 派是圆柱型，高度都是1，那么计算的时候只要算面积就可以了 人数：p+1 解x可能是一个小数 x越大分的人数越少 范围： 0 - 最大的一块派面积 问题单调性: 假设x是问题的解， 如果x是正确的，要寻求最大的解，可以排除x以下 如果x不是正确的，那么x以上的也不行，排除x以上 所以分析问题是单调的 思路： 求解转判定，利用二分来查找 */ #include<iostream> using namespace std; double a[10005],pi=3.141592653589; double maxn=-1,eps=1e-5; int n,f,r; bool check(double mid){ int cnt=0; for(int i=1;i<=n;i++){ cnt+=(int)(a[i]/mid); } return cnt>=f+1;//切的块数大于等于人数 } int main(){ cin>>n>>f; for(int i=1;i<=n;i++){ cin>>r; a[i]=pi*r*r;//计算面积 maxn=max(maxn,a[i]);//上限是最大值 } double l=0,r=maxn; while(l+eps<r){ double mid=(l+r)/2; if(check(mid)){ l=mid; }else{ r=mid; } } printf("%.3f",l); return 0; }

额外知识补充

可以看下9163这个题，假如用当前的这个思路去做

然后测试这个样例
577862887 373 696573
会发现最后会产生死循环

通过调试发现后面的值是不变化的，主要就是eps的精度不够，加上基本没变化，就会陷入死循环，这个时候需要换一种方式去解决

2780 月利率

/* 一个人从银行贷款后，在一段时间内他(她)将不得不每月偿还固定的分期付款 要求计算出最大利率，可以在规定的日期还完 分析样例： 1000 100 12 总钱数 1000 ，每个月还100,12月还完 将利率2.9带入后，看下过程 月份 本月的本金 本月贷款 还款金额 下月的本金 1 1000 1029 100 929 2 929 955.941 100 855.941 3 855.941 880.763 100 780.763 4 780.763 803.405 100 703.405 5 703.405 723.804 100 623.804 6 623.804 641.895 100 541.895 7 541.895 557.609 100 457.609 8 457.609 470.88 100 370.88 9 370.88 381.636 100 281.636 10 281.636 289.803 100 189.803 11 189.803 195.307 100 95.307 12 95.307 98.0713 100 -1.92872 最后第12月还完的金额是负数，说明还完了，这个解是正确的 可以推算出： 利率越高，还的时间越长 分析问题的单调性 假设 x是问题的解 如果x是正确的，要寻求最大的，可以排除x以下 如果x不是正确的，那么x以下的也不行，排除x以上的 解的范围是： 0 - 极限的10是绝对不行的 */ #include<iostream> using namespace std; double s,p,m,eps=1e-5; bool f(double mid){ double t=s;//总钱数 for(int i=1;i<=m;i++){ t=t*(1+mid);//当月的贷款 t-=p;//还完剩下的 } return t<=0;//是否能还完 } int main(){ cin>>s>>p>>m; double l=0,r=10;//利率是10 就还不完了 while(l+eps<r){ double mid=(l+r)/2; if(f(mid)){ l=mid; }else{ r=mid; } } printf("%.1f",int(l*1000+0.5)/10.0); return 0; }

10272 接水

/* 分析： 水龙头越多，接水时间越少 枚举范围： 1 - n(人数是n) 分析问题的单调性： 假定x是问题的解 如果x是正确的，要寻求小的解，可以排除x以上 如果x不是正确的，那么x小的必然不行，可以排除x以下的 排队的策略： 当轮到第i个人接水，需要找排队时间最少的水龙头 */ #include<iostream> #include<algorithm> #include<cstring> using namespace std; int n,x,t[15],b[15];//t:第i个人的接水时间 b:水龙头接水时间 bool f(int mid){ memset(b,0,sizeof(b)); for(int i=1;i<=n;i++){//第i个人接水 //选择排队最少的那个 sort(b+1,b+mid+1); b[1]+=t[i];//第一个排队时间最少 } int maxn=-1; for(int i=1;i<=mid;i++){ maxn=max(maxn,b[i]); } return maxn<=x; } int main(){ cin>>n>>x; for(int i=1;i<=n;i++){ cin>>t[i]; } int l=1,r=n,ans; while(l<=r){ int mid=(l+r)/2; if(f(mid)){ ans=mid; r=mid-1; }else{ l=mid+1; } } cout<<ans; return 0; }

别发这种帖子，会被举报，这个不能发的，快采纳吧

哪一种

哪种，是不是for循环、while循环的层次，还是位运算那种？