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

这篇具有很好参考价值的文章主要介绍了算法设计与分析 SCAU19184 传球游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

19184 传球游戏

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

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

题型: 编程题 语言: 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 <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]

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

  • 传到第一个人手中: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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 五子棋游戏AI智能算法设计

    五子棋游戏C语言AI智能算法设计  近来发现编制五子棋游戏很有趣,尤其是AI智能算法很烧脑。网上介绍有什么贪心算法,剪枝算法,博弈树算法等等,不一而足。 对于人机对战的电脑智能应子算法,参阅很多五子棋书籍棋谱和五子棋竞赛的对抗棋谱。我感到白棋的后手防御

    2024年02月06日
    浏览(48)
  • 咩了个咩三消小游戏算法逻辑分析 ,提供源码

    咩了个咩类似于这种游戏,三消其实里面的实现逻辑非常复杂的,主要的难点在于: 1, 3个同样的卡牌一组,  牌桌上的卡牌总数要是3个倍数, 即能被3整除, 同时每一种单独的卡牌也都是3个倍数         数据结构如下:         非常精妙的设计:随机在card中生成牌,

    2024年02月10日
    浏览(32)
  • 算法设计与分析--迭代算法

    一、迭代算法简介 二、设计工作步骤 三、迭代--递推法 题目及运行 四、迭代--倒推法 题目及运行 五、总结 算法语言--C语言 迭代算法也称 “辗转法” ,是一种不断用变量的 旧值递推出新值 的解决问题的方法。 迭代算法一般用于数值的计算,是读者早就熟悉的一种算法策

    2024年02月09日
    浏览(50)
  • 【算法分析与设计】算法概述

    数据结构+算法(+设计模式)=程序   理解算法的概念。   掌握算法的计算复杂性概念。   掌握算法复杂性的渐近性态的数学表述。   了解NP类问题的基本概念。   顾名思义,计算(求解)的方法   算法(Algorithm):对特定问题求解步骤的一种描述,是 指令的有

    2024年02月07日
    浏览(36)
  • 【算法分析与设计】贪心算法(下)

      给定带权有向图G =(V,E),其中 每条边的权是非负实数 。另外,还给定V中的一个顶点,称为源。现在 要计算从源到所有其它各顶点的最短路长度 。 这里路的长度是指路上各边权之和 。 这个问题通常称为单源最短路径问题 。   Dijkstra算法是解单源最短路径问题的贪心

    2024年02月08日
    浏览(42)
  • 算法设计与分析之贪心算法

    贪心算法(Greedy Algorithm)是一种基于贪心思想的算法策略。它通过每一步选择当前状态下最优的解决方案,从而逐步得到全局最优解。贪心算法通常在问题具有 贪心选择性质 和 最优子结构性质 时被应用。 贪心算法的基本思想是,每一步选择当前情况下看起来最好的解决方

    2024年02月11日
    浏览(47)
  • 【算法分析与设计】贪心算法(上)

      理解贪心算法的概念。   掌握贪心算法的基本要素   (1) 最优子结构性质   (2) 贪心选择性质   理解贪心算法与动态规划算法的差异   理解贪心算法的一般理论   通过应用范例学习贪心设计策略。   (1) 活动安排问题 ;   (2) 最优装载问题

    2024年02月08日
    浏览(50)
  • SCAU 统计学 实验5

    8.14 总体平均值(μ):7.0 cm 总体方差(σ²):0.03 cm² 样本平均值(x̄):6.97 cm 样本方差(s²):0.0375 cm² 样本大小(n):80 在这个问题中,我们已经知道总体方差(σ²),所以应该使用 z 检验。 将检验以下零假设(H₀): H₀: μ = 7.0 cm 与备择假设(H₁): H₁: μ ≠

    2024年02月01日
    浏览(42)
  • 【四】【算法分析与设计】贪心算法的初见

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i ,都有一个胃口值 g[i] ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 s[j] 。如果 s[j] = g[i] ,我们可以将这个饼干 j 分配给孩子

    2024年03月17日
    浏览(47)
  • 【算法与数据结构】--算法基础--算法设计与分析

    一、贪心算法 贪心算法是一种解决优化问题的算法设计方法,其核心思想是在每一步选择当前状态下的最优解,从而希望最终达到全局最优解。下面将介绍贪心算法的原理、实现步骤,并提供C#和Java的实现示例。 1.1 原理: 贪心算法的原理基于局部最优选择,通过在每一步选

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包