最接近点对问题将合并的时间从n^2减少为n，从而将算法的时间复杂度由n^减少为nlogn。

问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较.

试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.

为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.

算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.

结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.

石子合并

问题描述:在一个圆形操场的四周摆放着n堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分.试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.

算法设计:对于给定n堆石子,计算合并成一堆的最小得分和最大得分.

数据输入:由文件input.txt提供输入数据.文件的第1行是正整数n(1≤n≤100),表示有n堆石子.第2行有n个数,分别表示每堆石子的个数.

结果输出:将计算结果输出到文件outpur.txt.文件第1行的数是最小得分,第2行中的数是最大得分.

A、自底向上计算

B、最优子结构

C、从大到小计算

D、重叠子问题

A、正推

B、反推

C、枚举

D、迭代