• 算法设计与分析 SCAU19184 传球游戏


    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


    解题思路

    一、深度优先搜索

    解题思路

    搜索即将所有情况列出来,每传到一个同学手中时,他都有两种选择,一个是往左传,一个是往右传,我们只要计算传到最后一次时是否传回第一个人手中即可。

    类似于击鼓传花,只不过击鼓传花结束条件是时间到了,而这题的结束条件是传的次数到了

    算法思路
    1. 递归的传参有两个,一个是记录传到第几次,一个是记录传到编号为几的人手上。
    2. 递归终止条件,达到第 m 次;如果此时符合条件(即传到第一个人手上),就将记录的 res 进行加一即可。
    3. 每次递归都有两种选择,一个是往左传,一个是往右传。
    4. 注意在编写第三步时,要分三种特殊情况,因为此题为圆圈,第一个人可以传到最后一个人手上,最后一个人可以传到第一个人手上。因此第一种情况是此时传到第一个人手中,第二种情况时此时传到最后一个人手中,第三种情况就是普通情况,传到中间任意一个人手中
    补充

    如果此题还要求输出传递的序列,那么便可新增一个记录序列的 nums 数组,在递归时同时压入 nums,且需要记得回溯即可(即还原状态)。



    更多注释可查看下方的完整代码中,有助于理解

    代码如下
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    /*
    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60


    二、动态规划

    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]

    但需要注意有特殊情况,第一个人左边是最后一个人,最后一个人右边是第一个人,所以特殊情况特殊处理即可。

    • 传到第一个人手中:a[i][j] = a[i - 1][2] + a[i - 1][n]
    • 传到最后一个人手中:a[i][j] = a[i - 1][n - 1] + a[i - 1][1]


    代码如下
    #include 
    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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23


    最后

    对我感兴趣的小伙伴可查看以下链接

  • 相关阅读:
    ChatGPT的原理
    基于工程车辆/物流车辆/消防车辆远程通信的车队管理解决方案
    ubuntu 安装 zsh、ohmyzsh并配置必要插件
    42.会话划分问题求解(打标)
    Oracle查询固定时间间隔
    医学YOLOv8 | 脑肿瘤检测 Accuracy 99%
    Redis(01)| 数据结构
    Selenium WebDriver类的常用属性和方法汇总
    【计算机系统基础1】gdb、gcc简易使用指南
    数据可视化?这些平台能处
  • 原文地址:https://blog.csdn.net/weixin_53893220/article/details/128075992