给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.
算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
对于任意长度不超过6的升序字符串,迅速计算出它在上述字典中的编码.
算法设计:对于给定的长度不超过6的升序字符串,计算它在上述字典中的编码.
数据输入:输入数据由文件名为input.txt的文本文件提供.文件的第1行是一个正整数k,表示接下来有k行.在接下来的k行中,每行给出一个字符出.
结果输出:将计算结果输出到文件output.txt.文件有k行,每行对应一个字符串的编码.
A.工厂的生产规模
B.工人数量
C.附近地形
D.有害物质的排放量和高度
E.当地风向频率
规则I:每次只能移动1个圆盘:
规则II:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则III:任何时刻都不允许将同色圆盘叠放在一起:
规则IV:在满足移动规则I~III的前提下,可将圆盘移至A、B、C中任一塔座上.
试设计一个算法,用最少的移动次数将塔座A上的n个圆盘移到塔座B上,并仍按同样顺序叠置.
算法设计:对于给定的正整数n,计算最优移动方案.
数据输入:由文件input.txt给出输入数据.第1行是给定的正整数no.
结果输出:将计算出的最优移动方案输出到文件output.txt.文件的每行由一个正整数k
和2个字符c1和c2组成,表示将第k个圆盘从塔座c1移到塔座c2上.
问题描述:给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下:
(1)n∈set(m);
(2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半:
(3)按此规则进行处理,直到不能再添加自然数为止.
例如,set(6)={6,16,26,126,36,136}.半数集set(6)中有6个元素.注意,该半数集是多重集.
算法设计:对于给定的自然数n,计算半数集set(n)中的元素个数.
数据输入:输入数据由文件名为input.txt的文本文件提供.每个文件只有一行,给出整数n(0<n<1000).
结果输出:将计算结果输出到文件output.txt.输出文件只有一行,给出半数集set(n)中的元素个数.
算法设计:对于给定的仓库布局,以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置,设计一个解推箱子问题的分支限界法,计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数.
数据输入:由文件input.txt提供输入数据.输入文件第1行有2个正整数n和m(1≤n,m≤100).表示仓库是n×m个格子的矩形阵列.接下来有n行,每行有m个字符,表示格子的状态.
S——格子上放了不可移动的沉重货物;P——箱子的初始位置;
W——格子空闲:K——箱子的目标位置.
M——仓库管理员的初始位置:
结果输出:将计算的最少推动次数输出到文件output.txt.如果仓库管理员无法将箱子从开始位置推到目标位置则输出“NoSolution!".
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".