网站建设合同管辖,如何设置网站关键字,网站建设白云,人才网站的seo怎么做目录 前言#xff1a;题目#xff1a;思路#xff1a;递归#xff1a;代码及详细注释#xff1a; 状态压缩dp#xff1a;代码及详细注释#xff1a; 总结#xff1a; 前言#xff1a;
这道题原本是蓝桥上的题#xff0c;现在搜不到了#xff0c;网上关于此题的讲解… 目录 前言题目思路递归代码及详细注释 状态压缩dp代码及详细注释 总结 前言
这道题原本是蓝桥上的题现在搜不到了网上关于此题的讲解更是寥寥无几仅有的讲解也只是递归思想python讲解和状态压缩dp的解决方法都没有这里就带大家用状态压缩dp方法来解决此题。
题目
大奖赛计分规则 每位选手需要回答10个问题其编号为1到10越后面越有难度。答对的当前分数翻倍答错了则扣掉与题号相同的分数选手必须回答问题不回答按错误处理。每位选手的起步分都是10分某获胜选手最终得分刚好是100分请推断出哪个题目答对了哪个题目答错了答对的记为1答错的记为0则10个题目的回答情况可用仅含1和0的串来表示。任务是算出所有可能情况每个答案占一行。填空题
输出 0010110011 0111010000 1011010000
思路
递归
分析本题首先想到递归思想从得分100逆推出初始分数为10的方案。 首先定义一个字符串
如果本题答对了则总得分除2字符串首位加1因为是从第10题往前推所以要逆序加
如果本题答错了则总得分加上本题的序号数字符串首位加0
这里还有一个小细节如果得分是奇数则不能除2只能答错。
代码及详细注释
def ScoreOut(qs, score, out):# 如果qs为0if qs 0:# 如果score等于10if score 10:print(out) # 输出当前字符串outreturn out # 返回当前字符串outelse:return # 返回空字符串else:# 如果score为偶数if score % 2 0:# 递归调用函数分别将score除以2并在开头添加字符1以及将score加上qs并在开头添加字符Oreturn ScoreOut(qs - 1, score // 2, 1 out) ScoreOut(qs - 1, score qs, O out)else:# 如果score为奇数只递归调用将score加上qs并在开头添加字符Oreturn ScoreOut(qs - 1, score qs, O out)# 初始调用函数
ScoreOut(10, 100, )
状态压缩dp
什么是状态压缩
利用一串0/1数字二进制数来表示各个点的状态
这就要求使用状态压缩的对象的状态必须只有两种0 或 1如果有三种状态用三进制来表示也未尝不可。
需要将状态数据实现为基本数据类型比如 intlong 等即状态压缩。比如说棋盘上的格子放棋子或者不放硬币的正面或反面题目的对或错等。
状态压缩要求状态数据中的单元个数不能太大比如用 int 来表示一个状态的时候状态的单元个数不能超过 3232位CPU所以题目一般都是至少有一维的数据范围很小。
当然Python不需要考虑数的大小是否受限。
分析本题上面用递归讲解过本题有递归就用动态规划来解决众所周知递归很好理解和书写但是递归的时间复杂度都不低会有大量冗余计算。像本题中
如图 会出现大量相同得分情况这就需要借助动态规划来处理重复计算了。
动态规划五部曲来分析
确定dp数组的定义
对于数组dp[i] :
下标表示10道题目的对错状态dp[i]表示对应得分
下标 i 的二进制数表示对错状态如 i 2 时 i 的二进制数为 10 此时10第1题答错之后的提还没有做二进制数的得分为多少i 7 时i的二进制数为111此时第1题答对第2题答对之后的题还没有做的得分为多少 特别注意 这里首位的1二进制后的数没有实际含义不表示题目对错这个在下面会讲解
题目中有10道题总共的有2 ** 10 - 1 种可能种情况可能的情况用2进制计算就可以得出如从000000000到111111111的可能数
对于0000000000这些都是10个数不用挨个数了二进制是这么表示但10进制中这个数就是0
要想这个二进制数有意义最前面就要加个1否则无论有几个0都表示0这个数所以我们在定义dp数组长度的时候不能为2 ** 10 而是为 2 ** 11因为二进制10000000001后面10个0的10进制数为 2 ** 11
大家之前做题接触的二进制情况肯定不多所以这里会稍微有点绕。这里主要理解前面自定义的1就好跟补码的符号位有异曲同工之妙只不过这里仅仅用来补位。
dp数组的递推公式
状态压缩dp的递推公式还跟别的动规的递推公式不太一样这里需要用到位运算符
这里简单讲解一下位运算符 : 表示运算数的各二进制位全部左移若干位低位补0 如 7 1 14 因为7的二进制数为111左移一位后为11101110的十进制数为14
右移跟左移同理。
还有python的二进制数可以用bin()函数来求如bin(7) 0b1110b表示二进制bin(7)的类型为字符串型。但是直接写0b111 就表示整型。
因为第二道题的得分是由第一道题的得分算出来的如
dp[0b1 1] dp[0b1] - 1 # dp[0b10]即dp[2]
dp[(0b1 1) 1] dp[0b1] * 2 # dp[0b11]即dp[3]对于第cur道题
如果答错dp[i 1] dp[i] - cur 如果答对dp[(i 1) 1] dp[i] * 2
在推导递推公式的时候如果不太清楚就看看dp数组的定义切记第一个1无实义
dp数组如何初始化
因为第一个1无实义所以
dp[0b1] 10 # dp[1]初始化得分为10dp数组遍历顺序
毫无疑问题是从前往后答的dp数组也是从左往右推
打印dp数组
画的有点丑下标最好写成二进制形式。
求出dp数组后就把得分为100且10道题全都做了的结果输出就行。比较简单有很多种方法就不细说了。
代码及详细注释
import math# 初始化一个长度为2^11的数组初始值为0
dp [0] * 2 ** 11
dp[1] 10 # dp[1]初始化得分为10
# dp[0b1 1] dp[0b1] - 1 dp[0b10]即dp[2]
# dp[(0b1 1) 1] dp[0b1] * 2 dp[0b11]即dp[3]maxscore 160 # 最大分数为160因为160怎么减题目序号都到不了100也可以设170等等
for i in range(1, 2 ** 10):if dp[i] -1:continueelse:cur int(math.log2(i 1)) # 计算准备做的题目序号因为第一个1无实际意义1之后的数才表示题的对错if dp[i] - cur 0:dp[i 1] -1else:dp[i 1] dp[i] - curif dp[i] * 2 maxscore:dp[(i 1) 1] -1else:dp[(i 1) 1] dp[i] * 2result []
while True:if 100 in dp:index dp.index(100) # 找到值为100的索引dp[index] 0if len(bin(index)) 13:result.append(bin(index)) # 将长度为13(10道题都做完了头三位为0b1)的二进制数添加到结果列表中else:breakfor res in result:print(res[3:]) # 输出结果列表中每个元素的第3位之后的内容
总结
状态压缩dp还是比较难的但把dp的定义吃透就比较好理解了。
