走方格&&跳格子(dp,递归,排列组合三种方法)

走方格&&跳格子(dp,递归,排列组合三种方法)走方格 给定一个 n mn m 的方格阵 沿着方格的边线走 从左上角 0 0 0 0 开始 每次只能往右或者往下走一个单位距离 问走到右下角 n m n m 一共有多少种不同的走法 输入格式 共一行 包含两个整数 nn 和 mm 输出格式 共一行

大家好,我是讯享网,很高兴认识大家。

走方格:

给定一个 n×mn×m 的方格阵,沿着方格的边线走,从左上角 (0,0)(0,0) 开始,每次只能往右或者往下走一个单位距离,问走到右下角 (n,m)(n,m) 一共有多少种不同的走法。

输入格式

共一行,包含两个整数 nn 和 mm。

输出格式

共一行,包含一个整数,表示走法数量。

数据范围

1≤n,m≤101≤n,m≤10

输入样例:

2 3 

讯享网

输出样例:

讯享网10

方法一:dp动态规划,定义一个二维数组a[12][12],当跳到a[i][j]时,该方案数总是由两部分组成,

一部分是跳到a[i-1][j]的方案数,另一部分是跳到a[i][j-1]的方案数,即a[i][j]=a[i-1][j]+a[i][j-1],特别的,当i==0||j==0时,方案只有一种,即a[i][j]=1

#include <iostream> using namespace std; int m,n; int main() { cin>>m>>n; int a[12][12]={0}; for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) if(i==0||j==0) a[i][j]=1; else a[i][j]=a[i-1][j]+a[i][j-1]; cout<<a[m][n]<<endl; return 0; }

方案二:递归,先列出样例所有方案数的情况,符合dfs深度优先搜索,

每次搜索中

若搜到了点 (n,m),那么 cnt++
否则如果不是最右边的点,那么搜该点右边的点
如果不是最下面的点,那么搜该点下面的点

讯享网#include <iostream> using namespace std; int m,n,cnt=0; void dfs(int a,int b) { if(a==m&&b==n) cnt++; if(a<m) dfs(a+1,b); if(b<n) dfs(a,b+1); } int main() { cin>>m>>n; dfs(0,0); cout<<cnt<<endl; return 0; }

方案三:排列组合,每次都是走n+m步,然后从中选出n步向下.fenzi和fenmu数字可能会特别大,int会爆,所以用longlong

#include<iostream> using namespace std; int main() { int n,m; long long fenzi=1,fenmu=1; cin>>n>>m; for(int i=1;i<=n+m;i++) { if(i>n) fenzi=fenzi*i; if(i<=m) fenmu=fenmu*i; } // cout<<fenzi<<' '<<fenmu<<endl; cout<<fenzi/fenmu<<endl; return 0; }

跳格子:


讯享网

一个楼梯共有 nn 级台阶,每次可以走一级或者两级,问从第 00 级台阶走到第 nn 级台阶一共有多少种方案。

输入格式

共一行,包含一个整数 nn。

输出格式

共一行,包含一个整数,表示方案数。

数据范围

1≤n≤151≤n≤15

输入样例:

讯享网5 

输出样例:

8

方案一:f[i]代表跳到第i级台阶的方案数

讯享网#include<iostream> using namespace std; int main() { int f[20],n; cin>>n; f[1]=1,f[2]=2; for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; cout<<f[n]<<endl; return 0; } 

方案2:

#include<iostream> using namespace std; int n,cnt=0; void dfs(int a) { if(a==n) cnt++; else if(a<n) //一定要有这个条件,要不然退出不了dfs { dfs(a+1); dfs(a+2); } } int main() { cin>>n; dfs(0); cout<<cnt<<endl; return 0; }

方案三:以样例为例,方案由1 1 1 1 1,

1112,1121,1211,2111,

221,212,122,

每一种单独的方案符合排列组合问题,n个台阶,每一种方案最少有(n+1)/2个数,最多有n个数

讯享网#include<iostream> using namespace std; int main() { int n,cnt=1,res=0,up=1,down=1; //res代表有几个2 cin>>n; int a=(n+1)/2; //向上取整 while (n --&&n>=a) { up=1,down=1; res++; for(int i=n;i>n-res;i--) up=up*i; for(int i=1;i<=res;i++) down=down*i; cnt=cnt+up/down; } cout<<cnt<<endl; return 0; }

小讯
上一篇 2025-03-14 11:43
下一篇 2025-01-23 21:14

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/112476.html