青岛建设管理局网站,wordpress怎么设计,重庆公司企业网站建设,哪里有做ppt的网站动态规划题目汇总
斐波那契数列#xff1a;1#xff0c;1#xff0c;2#xff0c;3#xff0c;5#xff0c;8#xff0c;13…… 递归一把解决三类问题#xff1a;1.数据定义是按照递归的#xff08;斐波那契数列#xff09;。2.问题解法是按递归算法实现的。 3.数据…动态规划题目汇总
斐波那契数列11235813…… 递归一把解决三类问题1.数据定义是按照递归的斐波那契数列。2.问题解法是按递归算法实现的。 3.数据形式是按照递归形式定义的。 递归的一般形式
void rec(形参列表)
{if(test) return; //边界条件//注意 递归一定要有边界条件否则就会死循环rec(实参列表) //递归调用语句序列2 //递归返回段(回溯)
}
有一种兔子从出生后第3个月起每个月都生一只兔子小兔子长到第三个月后每个月又生一只兔子。例假设一只兔子第3个月出生那么它第5个月开始会每个月生一只兔子。一月的时候有一只兔子假如兔子都不死问第n个月的兔子总数为多少 输入一个int型整数表示第n个月 输出对应的兔子总数
#include iostream
using namespace std;
int total(int n);
int total(int n)
{if(n1||n2)//这个叫边界条件return 1;elsereturn total(n-1)total(n-2);//递归调用
}
int main() {//斐波那契数列int n,num;cinn;numtotal(n);coutnum;
}
把m个同样的苹果放在n个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法 注意如果有7个苹果和3个盘子511和151被视为是同一种分法。
解题思路 假设有m个苹果和n个盘子我们可以将问题分为两种情况 1. 盘子中至少有一个盘子为空这种情况下我们可以将m个苹果放在n-1个盘子中即将问题转化为将m个苹果放在n-1个盘子中的分法。所以这种情况下的分法数为f(m, n-1)。 2. 盘子中所有盘子都有苹果这种情况下我们可以将每个盘子中放入一个苹果然后将剩余的m-n个苹果放在n个盘子中即将问题转化为将m-n个苹果放在n个盘子中的分法。所以这种情况下的分法数为f(m-n, n)。 综上所述将m个苹果放在n个盘子中的分法数为f(m, n) f(m, n-1) f(m-n, n)。 边界条件 - 当m0时表示没有苹果需要放入盘子中所以只有一种分法即所有盘子都为空。 - 当n0时表示没有盘子可以放苹果所以没有分法。 根据上述递推关系和边界条件可以使用递归或动态规划的方法来求解。
#include iostream
using namespace std;int fn(int m,int n)
{if(n1) return 0;if(m0) return 0;if(m0) return 1;return fn(m-n,n)fn(m,n-1);//没有空盘子有1个空盘子
}int main() {int m,n;cinmn;coutfn(m,n);
}
n*m的棋盘格子n为横向的格子数m为竖向的格子数从棋盘左上角出发沿着边缘线从左上角走到右下角总共有多少种走法要求不能走回头路即只能往右和往下走不能往左和往上走。
#include iostream
using namespace std;
int digui(int x,int y)
{if(x1||y1)//只有一行或者一列的时候就有xy种方法return xy; //否则就往上或者往下走一步。return digui(x-1,y)digui(x,y-1);//if(x0)//return 1;//if(y0)//return 1;//return xy; //否则就往上或者往下走一步。//return digui(x-1,y)digui(x,y-1);//if(m0||n0)//return 0;//else if(n1m0)//return 1;//else if(m1n0)//return 1;//else //return(digui(m-1, n)digui(m,n-1));
}int main() {int m,n;cinnm;coutdigui(m,n);}
最长递增子序列问题 4.
class Solution {public:int LIS(vectorint arr) {if (arr.empty())return 0;int N arr.size();vectorintdp(N, 1);int maxLen 1;for (int i 1; i N; i) {for (int j 0; j i; j) {if (arr[i] arr[j]) {dp[i] max(dp[i], dp[j] 1); //长度加1}}maxLen max(maxLen, dp[i]);//更新最大长度}return maxLen;}}; BFS广度优先搜索算法
#include iostream
#include cstdio
#include queue
using namespace std;
int Map[5][5]; //定义地图大小
int dir[4][2] {1,0,-1,0,0,-1,0,1}; //定义方向
int n,m,ans;
struct node
{int x,y,step;} now,nextt; //保存走步
int BFS(int x,int y)
{queuenodeq;int xx,yy,zz;Map[x][y]2; //走过初始点now.xx;now.yy;now.step0;q.push(now); //从当前点开始while(!q.empty()){nowq.front();q.pop();for(int i0; i4; i) //遍历四个方向{xxnow.xdir[i][0];yynow.ydir[i][1]; //走一步if(xx0xx5yy0yy5Map[xx][yy]!1Map[xx][yy]!2) //可以走{nextt.xxx;nextt.yyy;nextt.stepnow.step1; //步数加一Map[now.x][now.y]2; //走过一个点if(Map[xx][yy]3) //到达终点return nextt.step;q.push(nextt);}for(int i0; i5; i){ //打印地图for(int j0; j5; j)cout Map[i][j];cout endl;}cout endl;}}return -1; //走不过去
}int main()
{for(int i0; i5; i) //输入地图for(int j0; j5; j)cin Map[i][j];Map[4][4]3; //定义终点ansBFS(0,0);cout ans endl;return 0;}
自己重构的走迷宫的代码
#include algorithm
#include iostream
#include cstdio
#include queue
#include vector
using namespace std;
int n,m;
int zuiyou;
vectorvectorintmaze; //定义地图大小
struct point{int x,y;
};
int fangxiang[4][2]{{-1,0},{1,0},{0,-1},{0,1}}; //定义上下左右
vectorvectorint path(5,vectorint(5));//记录每次的方向,0,1,2,3对应上下左右
vectorvectorintfan;struct node{int x,y,z;
}now, nextt;;void bfs(int x,int y)
{ // vectorvectorint path(n, vectorint(m));maze[x][y]2;queue node q;now.xx;now.yy;now.z0;q.push(now);while(!q.empty()){ nowq.front();maze[now.x][now.y]2;q.pop();for( int i0;i4;i){int xxnow.xfangxiang[i][0];int yynow.yfangxiang[i][1];if(xx0xxnyy0yymmaze[xx][yy]3){ path[xx][yy]i;if(maze[xx][yy]3)zuiyounow.z1;}if(xx0xxnyy0yymmaze[xx][yy]0){ nextt.xxx;nextt.yyy;nextt.znow.z1;q.push(nextt);path[xx][yy]i;}}}int iin-1,jjm-1;fan.push_back({ii,jj});while(ii!0||jj!0){ int numpath[ii][jj];iiii-fangxiang[num][0]; jjjj-fangxiang[num][1]; fan.push_back({ii,jj});}reverse(fan.begin(),fan.end());
}int main()
{ cinnm;mazevectorvectorint(n,vectorint(m)); //定义地图大小 for(int i0;in;i){for(int j0;jm;j){cinmaze[i][j];}}maze[4][4]3;bfs(0, 0);coutzuiyouendl;;coutendl;for(auto t:fan){coutt[0],t[1];coutendl;}} DFS深度优先搜索算法一般用于查找图中的路径、连通性检测、拓扑排序等。 深度优先搜索使用栈Stack数据结构来保存需要探索的节点。每次访问一个节点时将其标记为已访问并将其未访问的邻居节点压入栈中。然后从栈中弹出一个节点继续访问该节点的未访问邻居节点直到栈为空。
如果需要找到最短路径可以考虑使用其他算法如广度优先搜索BFS或 Dijkstra 算法。一般最小步数、最短距离、最小操作次数等问题采用BFS。
