19184 传球游戏
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC;JAVA
Description
n个同学站成一个圆圈,其中的一个同学手里拿着一个球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意)。
从1号同学手里开始传的球,传了m次以后,又回到1号同学手里,请问有多少种不同的传球方法。
两种传球方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。
比如有三个同学1号、2号、3号,球传了3次回到1号手里的方式有1->2->3->1和1->3->2->1,共2种。
输入格式
一行,有两个用空格隔开的整数n,m(3≤n≤30,1≤m≤30)。
输出格式
符合题意的方法数。
输入样例
3 3
输出样例
2
解题思路
一、深度优先搜索
解题思路
搜索即将所有情况列出来,每传到一个同学手中时,他都有两种选择,一个是往左传,一个是往右传,我们只要计算传到最后一次时是否传回第一个人手中即可。
类似于击鼓传花,只不过击鼓传花结束条件是时间到了,而这题的结束条件是传的次数到了。
算法思路
- 递归的传参有两个,一个是记录传到第几次,一个是记录传到编号为几的人手上。
- 递归终止条件,达到第 m 次;如果此时符合条件(即传到第一个人手上),就将记录的 res 进行加一即可。
- 每次递归都有两种选择,一个是往左传,一个是往右传。
- 注意在编写第三步时,要分三种特殊情况,因为此题为圆圈,第一个人可以传到最后一个人手上,最后一个人可以传到第一个人手上。因此第一种情况是此时传到第一个人手中,第二种情况时此时传到最后一个人手中,第三种情况就是普通情况,传到中间任意一个人手中
补充
如果此题还要求输出传递的序列,那么便可新增一个记录序列的 nums 数组,在递归时同时压入 nums,且需要记得回溯即可(即还原状态)。
更多注释可查看下方的完整代码中,有助于理解
代码如下
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
/*
3 3
*/
using namespace std;
const int N = 1050;
const int inf = 1e9+7;
const int mod = 1e9+7;
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long ll;
int n, m; // n 个同学传 m 次
int res = 0;
// cur 为传了几次,i 为传到序号为几的人手上
void dfs(int cur, int i) {
if(cur == m + 1) {
// 如果最后这次传回第1个人手上,则满足条件
if(i == 1) {
res++;
}
return;
}
// 由于是圈,第一个人的左手边是最后一个人
if(i == 1) {
dfs(cur + 1, n); // 传给左手边的人
dfs(cur + 1, i + 1); // 传给右手边的人
} else if(i == n) {
// 由于是圈,最后一个人的右手边是第一个人
dfs(cur + 1, i - 1); // 传给左手边的人
dfs(cur + 1, 1); // 传给右手边的人
} else{
dfs(cur + 1, i - 1); // 传给左手边的人
dfs(cur + 1, i + 1); // 传给右手边的人
}
}
int main()
{
cin >> n >> m;
dfs(1, 1);
cout << res << endl;
return 0;
}
二、动态规划
1. dp 方程定义
- a[i][j] 表示第 i 次传球传到 j 同学手里的方案数
2. 状态转移方程
当传到 j 同学手中时,传过来的位置有两种情况,一种是从左边即 j - 1,一种是从右边即 j + 1,因此 a[i][j] = a[i - 1][j - 1] + a[i - 1][j + 1]
但需要注意有特殊情况,第一个人左边是最后一个人,最后一个人右边是第一个人,所以特殊情况特殊处理即可。文章来源:https://www.toymoban.com/news/detail-418863.html
- 传到第一个人手中:a[i][j] = a[i - 1][2] + a[i - 1][n]
- 传到最后一个人手中:a[i][j] = a[i - 1][n - 1] + a[i - 1][1]
代码如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n,m,a[35][35]={0};
cin>>n>>m;
a[0][1]=1;
for(i=1;i<=m;i++)
{ /**< a[i][j]表示第i次传球传到j同学手里的方案数 */
for(j=1;j<=n;j++)
{/**< a[i][j]=a[i-1][j-1]+a[i-1][j+1] */
if(j==1)
a[i][j]=a[i-1][2]+a[i-1][n];
else if(j==n)
a[i][j]=a[i-1][n-1]+a[i-1][1];
else
a[i][j]=a[i-1][j-1]+a[i-1][j+1];
}
}
cout<<a[m][1];
return 0;
}
最后
对我感兴趣的小伙伴可查看以下链接文章来源地址https://www.toymoban.com/news/detail-418863.html
- 我的掘金主页:https://juejin.cn/user/1302297507801358
- 博客主页:http://blog.zhangjiancong.top/
- 公众号:Smooth前端成长记录
到了这里,关于算法设计与分析 SCAU19184 传球游戏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!