问题描述:给定n个正整数和4个运算符+、-、*、/,且运算符无优先级,如2+3*5-25.对于任意给定的整数m
算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
第1题
问题描述:设是n个互不相同的符号组成的符号集.1≤i≤k}是Σ中字符组成的长度为k的字符串至体.是Lk的1个无分隔符字典是指对任意和.
无分隔符字典问题要求对给定的n和Σ及正整数k,计算Lk的最大无分隔符字典.
算法设计:设计一个算法,对于给定的正整数n和k,计算Lk的最大无分隔符字典.
数据输入:由文件input.txt给出输入数据.文件第1行有2个正整数n和k.
结果输出:将计算的Lk的最大无分隔符字典的元素个数输出到文件output.txt.
第2题
其中,集合{{1,2,3,4)}由1个子集组成:集合{{1{,2},{3,4}},{{1,3},{2,4},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{2,3,4},{1}}由2个子集组成:集合{{1,2},{3},{4}},({1,3},{2},{4},{{1,4},{2},{3}},{{2,3},{1},{4)},{{2.4},{1},{3}},{{3,4},{1},{2}}由3个子集组成:集合{{1},{2},{3},{4}}由4个子集组成.
算法设计;给定正整数n和m,计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的由m个非空子集组成的集合.
数据输入:由文件input.txt提供输入数据.文件的第1行是元素个数n和非空子集数m.
结果输出:将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt.
第3题
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.
第4题
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
第5题
算法设计:给定n个整数组成的序列,计算该序列的最优m段分割,使m段子序列的和的最大值达到最小.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和m.正整数n是序列的长度:正整数m是分割的段数.接下来的一行中有n个整数.
结果输出:将计算结果输出到文件output.txt.文件的第1行中的数是计算出的m段子序列的和的最大值的最小值.
第6题
0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是wi,其价值为vi背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大?
在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定,要求n元0-1向量,使得而且达到最大.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.
结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt
第7题
问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较.
试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.
为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.
算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.
结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.
第8题
的最小值称为数据包序列的均衡负载量.
算法设计:对于给定的数据包序列,计算m个处理器的均衡负载量.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.n表示数据包个数,m表示处理器数.接下来的1行中有n个整数,表示n个数据包的大小.
结果输出:将计算的处理器均衡负载量输出到文件output,txt,且保留2位小数.
第9题
算法设计:对于给定的方格棋盘,按照取数要求找出总和最大的数.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数m和n,分别表示棋盘的行数和列数.接下来的m行,每行有n个正整数,表示棋盘方格中的数.
结果输出:将取数的最大总和输出到文件output.txt.
第10题
算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.
结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.