一个问题是易验证的是指对该问题的给定实例的每个解,都可以有效地验证其正确性.例如,求一个整数的非平凡因子问题是易验证的,而求一个整数的最小非平凡因子就不是易验证的.在一般情况下,易验证问题未必是易解的.(1)给定一个解易验证问题P的蒙特卡罗方法,设计一个相应的解问题P的拉斯维加斯算法.(2)给定一个解易验证问题P的拉斯维加斯算法,设计一个相应的解问题P的蒙特卡罗算法.
(1)试证明上述算法mc3(x)是一致的27/32正确的算法,因此是84%正确的
(2)试证明如果me(x)不是一致的,则mc3(x)的正确率有可能低于71%.
算法设计:给定平面上n个点,计算这n个点的最短双调TSP回路.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的平面上的点数.在接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标.
结果输出:将计算的最短双调TSP回路的长度(保留2位小数)输出到文件output.txt.
试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.
为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.
算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.
结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!