算法设计:对于给定的k个待安排的活动,计算使用最少会场的时间表.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待安排的活动.接下来的k行中,每行有2个正整数,分别表示k个待安排的活动的开始时间和结束时间.时间以0点开始的分钟计.
结果输出:将计算的最少会场数输出到文件output.txt.
算法设计:对于给定的m和n,计算出不同的宝石排列方案数.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数m和n(0<m≤n<9).
结果输出:将计算的宝石排列方案数输出到文件output.txt.
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
问题描述:设p是奇素数,1≤x≤p-1,如果存在一个整数y(1≤y≤p-1),使得x=y2(modp),则称y是x的模p平方根.例如,63是55的模103平方根.试设计一个求整数x的模p平方根的拉斯维加斯算法.算法的计算时间应为logp的多项式.
算法设计:设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数p和x.
结果输出:将计算的x的模p平方根输出到文件output.txt.当不存在x的模p平方根时,输出0.
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.