草庐IT

HNUCM-2022年秋季学期《算法分析与设计》练习15

乖巧乐芬达 2023-04-08 原文

目录

问题 A: X星人的地盘

问题 B: X星人的递归

问题 C: X星人的礼物

问题 D: X星人的股票


问题 A: X星人的地盘

题目描述

一天,X星人和Y星人在一张矩形地图上玩抢地盘的游戏。
X星人每抢到一块地,在地图对应的位置标记一个“X”;Y星人每抢到一块地,在地图对应的位置标记一个“Y”;如果某一块地无法确定其归属则标记一个“N”。
最终统计谁拥有的地盘最大,即统计“X”和“Y”的个数。如果“X”的个数多,则说明X星人的地盘更大,输出“X win”;反之,如果Y星人的地盘更大,则输出“Y win”;如果X星人和Y星人拥有的地盘一样大,则输出“The same”。

输入

单组输入。
第1行输入两个正整数m和n,表示地图矩阵的行和列。(m和n均不超过1000)
从第2行到第m+1行,输入一个由'X'、'Y'和'N'三种字符组成的矩阵,每行包含n个字符,一共m行。

输出

如果X星人拥有的地盘大,输出“X win”;如果Y星人拥有的地盘大,输出“Y win”;如果拥有的地盘一样大,输出“The same”。

思路:简单题,就是数数,但是数据应该有点小问题,不适用python和java的一般输入,会导致wa。改用多组输入的方式循环输入即可解决。

x, y = 0, 0
while True:
    try:
        string = input()
        x, y = x + string.count('X'), y + string.count('Y')
    except:
        break
print('X win') if x > y else print('Y win') if y > x else print('The same')

问题 B: X星人的递归

题目描述

X星人想使用递归编写一个程序求如下表达式的计算结果:  (1<n<=1000)
S(n) = 1 -  4 + 9 - 16 + 25 - 36 +......
输入n,输出表达式S(n)的结果。
请你编写一个递归程序帮助X星人实现该功能。

输入

单组输入,输入一个正整数n,1<n<=1000。

输出

输出表达式S(n)的计算结果。

思路:简单题,直接用递归的话,注意递归深度。

import sys

sys.setrecursionlimit(1000000)


def fun(x: int):
    if x == 1:
        return 1
    else:
        t = -1 if x % 2 == 0 else 1
        return fun(x - 1) + t * (x ** 2)


n = int(input())
print(fun(n))

问题 C: X星人的礼物

题目描述

六一儿童节到了,X星人宝宝收到了很多很多礼物。他决定把这些礼物装到自己的礼物箱中。为此,他准备了很多个型号相同的礼物箱,每个礼物箱能够装礼物的最大重量都是一样的。但是X星人宝宝不希望在一个礼物箱里面装太多礼物(可能担心礼物会被压坏吧),每个礼物箱最多只允许装2个礼物
假设X星人宝宝收到了N个礼物,现在给出每一个礼物的重量和一个礼物箱的最大装载量,请你编写一个程序计算X星人宝宝最少要用多少个礼物箱才能够把所有的礼物都装完

输入

单组输入。
每组两行,第1行输入两个正整数,分别表示礼物的数量N和每个礼物箱的最大装载量C,其中1<=N<=1000,1<=C<=100,两者之间用英文空格隔开。
第2行输入N个不超过100的正整数,分别表示每一个礼物的重量,两两之间用英文空格隔开。
输入保证最重的礼物的重量<=C。

输出

针对所输出的数据,输出将所有的礼物全部都装完所需的礼物箱的最少个数。

思路:对礼物的重量进行排序,从首尾开始选取礼物放入盒中,如果礼物的重量小于等于c,两者都放入盒中,否则只有最重的礼物放入盒中。

n, c = map(int, input().split())
goods, cnt = [int(i) for i in input().split()], 0
i, j, _ = 0, n - 1, goods.sort()
while i < j:
    if goods[i] + goods[j] <= c:
        cnt, i, j = cnt + 1, i + 1, j - 1
    else:
        cnt, j = cnt + 1, j - 1
print(cnt) if i != j else print(cnt + 1)

问题 D: X星人的股票

题目描述

X星人最近迷上了炒股,他炒股有个习惯,每次看到股票跌的时候就会买入
现在给出某只股票一段时间的股价,假如该股票每天最多只能买入一次,请你编写一个程序计算X星人最多可以买入几次该股票

输入

单组输入。
第1行输入一个正整数N表示某股票股价连续交易的天数。(1<=N<=1000)
第2行输入N个正整数表示该股票在N个连续交易日的股价,两两之间用英文空格隔开。(扩展知识:交易日是指股票交易发生的时间。常见的交易日时间是周一至周五,另外法定节假日和周末,股票市场和基金市场都是休市的。)

输出

请输出X星人最多可以买入股票的次数(不考虑第1次买入,只考虑中间买入的次数)。

思路:其实就是一个最长下降子序列的题目,只是题意不好理解。

n = int(input())
nums, d = [int(i) for i in input().split()], [1] * n
for i in range(1, n):
    for j in range(i):
        if nums[i] < nums[j] and d[i] < d[j] + 1:
            d[i] = d[j] + 1
print(max(d) - 1)

有关HNUCM-2022年秋季学期《算法分析与设计》练习15的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息,信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同,算法可以分为对称加密、非对称加密、对称加密和非

  2. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中,下列关于数学运算结果正确的是:(B)a=10b=3print(a//b)print(a%b)print(a/b)A.3,3,3.3333...B.3,1,3.3333...C.3.3333...,3.3333...,3D.3.3333...,1,3.3333...解析:    在Python中,//表示地板除(向下取整),%表示取余,/表示除(Python2向下取整返回3)2.如下程序Python2会打印多少个数:(D)k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析:    按照题意每次循环K/2,直到K值小于等

  3. 映宇宙2022年营收63亿元:同比下降三成,毛利率提升4.3个百分点 - 2

    3月26日,映宇宙(HK:03700,即“映客”)发布截至2022年12月31日的2022年度业绩财务报告。财报显示,映宇宙2022年的总营收为63.19亿元,较2021年同期的91.76亿元下降31.1%。2022年,映宇宙的经营亏损为4698.7万元,2021年同期则为净利润4.57亿元;期内亏损(净亏损)为1.68亿元,2021年同期的净利润为4.33亿元;非国际财务报告准则经调整净利润为3.88亿元,2021年同期为4.82亿元,同比下降19.6%。 映宇宙在财报中表示,收入减少主要是由于行业竞争加剧,该集团对旗下产品采取更为谨慎的运营策略以应对市场变化。不过,映宇宙的毛利率则有所提升

  4. 100个python算法超详细讲解:画直线 - 2

    1.问题描述使用Python的turtle(海龟绘图)模块提供的函数绘制直线。2.问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成,而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下:1)TurtleScreen类:定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  5. 建模分析 | 平面2R机器人(二连杆)运动学与动力学建模(附Matlab仿真) - 2

    目录0专栏介绍1平面2R机器人概述2运动学建模2.1正运动学模型2.2逆运动学模型2.3机器人运动学仿真3动力学建模3.1计算动能3.2势能计算与动力学方程3.3动力学仿真0专栏介绍?附C++/Python/Matlab全套代码?课程设计、毕业设计、创新竞赛必备!详细介绍全局规划(图搜索、采样法、智能算法等);局部规划(DWA、APF等);曲线优化(贝塞尔曲线、B样条曲线等)。?详情:图解自动驾驶中的运动规划(MotionPlanning),附几十种规划算法1平面2R机器人概述如图1所示为本文的研究本体——平面2R机器人。对参数进行如下定义:机器人广义坐标

  6. 网站日志分析软件--让网站日志分析工作变得更简单 - 2

    网站的日志分析,是seo优化不可忽视的一门功课,但网站越大,每天产生的日志就越大,大站一天都可以产生几个G的网站日志,如果光靠肉眼去分析,那可能看到猴年马月都看不完,因此借助网站日志分析工具去分析网站日志,那将会使网站日志分析工作变得更简单。下面推荐两款网站日志分析软件。第一款:逆火网站日志分析器逆火网站日志分析器是一款功能全面的网站服务器日志分析软件。通过分析网站的日志文件,不仅能够精准的知道网站的访问量、网站的访问来源,网站的广告点击,访客的地区统计,搜索引擎关键字查询等,还能够一次性分析多个网站的日志文件,让你轻松管理网站。逆火网站日志分析器下载地址:https://pan.baidu.

  7. ABB-IRB-1200运动学分析MATLAB RVC工具分析+Simulink-Adams联合仿真 - 2

    一、机器人介绍        此处是基于MATLABRVC工具箱,对ABB-IRB-1200型号的微型机械臂进行正逆向运动学分析,并利Simulink工具实现对机械臂进行具有动力学参数的末端轨迹规划仿真,最后根据机械模型设计Simulink-Adams联合仿真。 图1.ABBIRB 1200尺寸参数示意图ABBIRB 1200提供的两种型号广泛适用于各作业,且两者间零部件通用,两种型号的工作范围分别为700 mm 和 900 mm,大有效负载分别为 7 kg 和5 kg。 IRB 1200 能够在狭小空间内能发挥其工作范围与性能优势,具有全新的设计、小型化的体积、高效的性能、易于集成、便捷的接

  8. 关于Qt程序打包后运行库依赖的常见问题分析及解决方法 - 2

    目录一.大致如下常见问题:(1)找不到程序所依赖的Qt库version`Qt_5'notfound(requiredby(2)CouldnotLoadtheQtplatformplugin"xcb"in""eventhoughitwasfound(3)打包到在不同的linux系统下,或者打包到高版本的相同系统下,运行程序时,直接提示段错误即segmentationfault,或者Illegalinstruction(coredumped)非法指令(4)ldd应用程序或者库,查看运行所依赖的库时,直接报段错误二.问题逐个分析,得出解决方法:(1)找不到程序所依赖的Qt库version`Qt_5'

  9. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字,该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动,每第二个数字的值加倍。将乘积的数字(例如,10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾),则根据Luhn公式该数字有效;否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

  10. Ruby 斐波那契算法 - 2

    下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14,但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗? 最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen

随机推荐