wordpress网站提速,wordpress模板应用,微信营销平台系统,长沙外贸网站前引#xff1a;继上篇我们讲到暴力递归的过程#xff0c;这一篇blog我们将继续对从暴力递归到动态规划的实现过程#xff0c;与上篇类似#xff0c;我们依然采用题目的方式对其转化过程进行论述。上篇博客#xff1a;https://blog.csdn.net/m0_65431718/article/details/…前引继上篇我们讲到暴力递归的过程这一篇blog我们将继续对从暴力递归到动态规划的实现过程与上篇类似我们依然采用题目的方式对其转化过程进行论述。上篇博客https://blog.csdn.net/m0_65431718/article/details/129604874?spm1001.2014.3001.5502一.n皇后问题八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在n×n的棋盘上摆放n个皇后使任意两个皇后都不能处于同一行、同一列或同一斜线上。 我们的解题思路如下采用暴力递归既然要求任意两个皇后不能在同一行和同一列和同一斜线我们依次对这三者进行讨论①同一行每一层递归代表一行我们只要保证在每一层递归中只放置一个皇后即可②同一列按照题目的要求我们在访摆放第n层的皇后时要保证它和前面n-1等皇后都不冲突这就意味着我们在进行下一层递归的时候仍能有方法访问前面皇后摆放的位置我们的第一考虑对象当然是数组但是比较巧妙的是它是一个n*n的棋盘第一个n代表行第二个n代表列我们只需要建立一个长度为n的一维数组下标代表第几行下标对应的数组元素代表列作为参数带入到下一层递归中斜线也是如此我们详细展开说说列和斜线的要求对于列来说我们要遍历缓存使前面的缓存和当前列不相等即为不冲突对于斜线的要求来说对于一个正方形棋盘我们其实很容易想到的是直线的斜率为1也就是说两个元素行的变化如果等于列的变化我们可以说在同一条斜线上。我们根据思路给出codepublic class NEmpress {public static void main(String[] args) {//创建dateint n4;int[]datanew int[n];System.out.println(process(data, 0, n));}//创建递归过程public static int process(int[]data,int i,int n){//判断出口条件:共有n个元素一旦当前行越过了n-1则说明成功if(in){return 1;}//循环处理每一列//如果没结束int res0;for(int j0;jn;j){//判断当前元素是否有效if(isValid(data,i,j)){data[i]j;//进入下一层递归res process( data, i1, n);}}return res;}private static boolean isValid(int[] data, int i, int j) {//在data中检验是否存在for(int k0;ki;k){//第一个是判断从0到i-1行中列的元素是否相等第二个是判断是否在同一斜线if(data[k]j||(Math.abs(i-k)Math.abs(j-data[k]))){return false;}}return true;}
}
如果不改变问题的实现思路很难去实现大的效率提升但是考虑不同的方法仍能在一定程度上提升效率常数级提升采用位运算总体的实现逻辑和之前的暴力递归完全相同但是就具体细节做出了一定的改动我们给出递归的核心代码并改动进行解释说明:limit:是位数限制,对于行列数为N的棋盘limit的限制是对于前N个二进制位数均为1对于N行列的棋盘而言前N个二进制位代表棋盘的每一行第一个二进制位代表第一行第二个代表第二行........①col:对于每次摆放个皇后就将这个二进制位置变为1表示这个二进制位不能摆放皇后了②leftLim:左斜线限制如果leftLim为1代表对于当前行来说这个位置不能摆放皇后了。③RightLim:右斜线限制如果RightLim为1同样对于当前行来说这个位置不能摆放皇后了。④limitcol:代表col前N个二进制位都是1表示N个皇后都已经摆放好了游戏结束退出递归⑤limit(~(col|leftLim|rightLim))pos是在每一行中能选择的列⑥ mostRightpos(~pos1)取出最右边的一位⑦ pos-mostRight将最右边的位置从可选择的位数中去除使当前行不能放置皇后⑧while(pos!0) 循环当前行中能选择的位置⑨res process2(limit,col|mostRight,(leftLim|mostRight)1, (rightLim|mostRight)1)循环下一层public static int process2(int limit,int col,int leftLim,int rightLim){//递归出口if(limitcol){return 1;}//计算能放的位置int pos limit(~(col|leftLim|rightLim));int mostRight0;int res0;//检验是否能递归while(pos!0){//找最右的位置mostRightpos(~pos1);pos-mostRight;res process2(limit,col|mostRight,(leftLim|mostRight)1, (rightLim|mostRight)1);}return res;我们对代码中的几个点进行解释说明三.机器人走路问题从暴力递归到动态规划的实践问题要求如下1.假设有排成一行的n个位置记为1-N,N一定大于等于22.开始时机器人在m位置上m一定是1-N中的一个3.机器人要在规定的步数到达指定的终点计算到达指定终点的路线有多少条4.如果机器人来到1位置只能往右来到2位置5.如果机器人来到N位置只能往左来到N-1位置6.如果机器人在其他位置则机器人可以往右也可以往左对于暴力递归实现思路就相对比较简单对于当前位置而言如果位置是1他只能选择2如果在2-N-1的位置他可以向左和向右走如果在N位置只能往N-1的位置走不断走直到剩余步数为0判断是不是要求的位置然后返回结果。我们给出关于暴力递归的代码public int walking(int N,int cur,int rest,int P){//编写递归出口if(rest0){if(curP){return 1;}else {return 0;}}//排除特殊情况在0位置处只能往后走if(cur1){return walking(N, cur1, rest-1, P);}//在最后一个位置只能往前走if(curN){return walking(N, cur-1, rest-1, P);}//在中间可以往前往后走return walking(N, cur-1, rest-1, P)walking(N, cur1, rest-1, P);}为什么说这是从暴力递归到动态规划的实践开始呢我们对此进行解释我们能在暴力递归的基础上修改为动态规划什么是动态规划呢是将暴力递归中重复计算的过程转化为缓存从而降低暴力递归中重复计算的次数转而从相关缓存中获取是一种典型的空间换时间的策略对于动态规划而言其实最难的部分是写出关于动态规划的转移方程。对这道题来说这种动态规划的类型是记忆性搜索如果这个位置有缓存就直接返回缓存结果否则递归。动态规划的的code如下public int walkCache(int N,int cur,int rest ,int [][]dp,int P){if(dp[cur][rest]!-1){return dp[cur][rest];}if(rest0){dp[cur][rest]curP?1:0;return dp[cur][rest];}if(cur1){dp[cur][rest]walkCache(N, cur1, rest-1, dp,P);return dp[cur][rest];}if(curN){dp[cur][rest]walkCache(N, cur-1, rest-1, dp,P);return dp[cur][rest];}return dp[cur][rest]walkCache(N, cur-1, rest-1, dp,P)walkCache(N, cur1, rest-1,dp, P);}}四.零和博弈问题问题描述思路对于A而言作为先手他一定在纵观全局后选择对自己最有利的计划而B作为后手只能在A 选择之后在此基础上选择对自己最友好的计划和策略换句话说B选择的只能是A选择剩下的。所以我们需要设计两个函数一个是先手函数选择其中相对自己而言最优的策略即为选择自己能选的棋中的最大值而同样需要设计一个后手函数它的作用是在后手参与下选择相对较小的选择只能选择A选剩下的我们给出codepackage violencerecursion;/*** author tongchen* create 2023-03-21 16:09*/
public class GameWin {public static void main(String[] args) {GameWin gameWin new GameWin();int[]arr{1,100,1};System.out.println(gameWin.win(arr));}public int win(int[]arr){//零和博弈问题解题思路先手的人拿最优的选择后手的人只能被迫接收最差的结果int left0;int right arr.length-1;return Math.max(f(arr, 0, arr.length-1),s(arr, 0, arr.length-1));}private int f(int[] arr, int left, int right) {//递归出口if(leftright){return arr[left];}//选择已知策略中最优的选择return Math.max(arr[left]s(arr,left1,right),arr[right]s(arr,left,right-1));}private int s(int[] arr, int left, int right) {if(rightleft){return 0;}//B相当于从第二个棋子先选择因为第一个棋子肯定被A选走了B先手选第二个棋子//但是这种情况下B只能选择在A纵观全局后选择最优策略之后被迫选择劣的选择即最小值return Math.min(f(arr, left1, right),f(arr, left, right-1));}
}后续会更新关于动态规划的转移方程的编写思路过程希望大家能持续关注捏~
