证明,对于任意正整数n都有(f,g)n=(fn,gn)。
第2题
问题描述;设S是正整数集合.S是一个无和集,当且仅当蕴含.对于任意正整数k,如果可将{1.2,...,k}划分为n个无和子集,则称正整数k是n可分的.记F(n)=max{k|k是n可分的}.试设计一个算法,对任意给定的n,计算F(n)的值.
算法设计:对任意给定的n,计算F(n)的值.
数据输入:由文件input.txt给出输入数据.第I行有1个正整数n.
结果输出:将计算的F(n)的值以及{1,2,F(n)}的一个n划分输出到文件output.txt.文件的第1行是F(n)的值.接下来的n行,每行是一个无和子集Si.
第3题
问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
第4题
算法设计:对于给定的n个正整数,设计一个算法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
第5题
算法设计:对于给定的n个环形排列的仓库的库存量,计算使n个仓库的库存数量相同的最少搬运量.
数据输入:由文件input.txt提供输入数据.文件的第1行中有1个正整数n,表示有n个仓库.第2行中有n个正整数,表示n个仓库的库存量.
结果输出:将计算的最少搬运量输出到文件output.txt.
第6题
上述最优求幂问题相应于正整数n的最短加法链问题,即求n的一个加法链,使其长度r达到最小.正整数n的最短加法链长度记为l(n).
算法设计:对于给定的正整数n,计算相应于正整数n的最短加法链.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.
结果输出:将计算的最短加法链长度l(n)和相应的最短加法链输出到文件output.txt.
第8题
批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.
算法设计:对于给定的n个作业,计算最佳作业调度方案.
数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.
结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.
第9题
算法设计:对于给定的n和k个加油站位置,计算最少加油次数.
数据输入:由文件input.tst给出输入数据.第1行有2个正整数n和k,表示汽车加满油后可行驶nkm,且旅途中有k个加油站.接下来的1行中有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离.第0个加油站表示出发地,汽车已加满油.第k+1个加油站表示目的地.
结果输出:将计算的最少加油次数输出到文件output.txt.如果无法到达目的地,则输出“NoSolution",
第10题
问题描述:大于1的正整数n可以分解为例如,当n=12时,有8种不同的分解式:
算法设计:对于给定的正整数n,计算n共有多少种不同的分解式.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n
结果输出:将计算出的不同的分解式数输出到文件output.txt.