设C={0,1,…,n-1}是n个字符的集合.证明关于C的任何最优前缀码可以表示为长度为2-1+n[logn]位的编码序列（用2n-1位描述树结构).

设α₀，α₁，…，α_n-r为Ax=b(b≠0)的n-r+1个线性无关的解向量，A的秩为r，证明：

α₁-α₀，α₂-α₀，…，α_n-r-α₀是对应的齐次线性方程组Ax=0的基础解系

问题描述:定义于字母表上的乘法表如表3-1所示.对任一定义于Σ上的字符串,适当加括号后,得到,个表达式.例如,对于字符串x=bbba,它的一个加括号表达式为(b(bb)(ba).依乘法表,该表达式的值为a试设计一个动态规划算法,对任一定义于Σ上的字符串 计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a.

算法设计:对于给定的字符串,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出一个字符串.

结果输出;将计算结果输出到文件output.txt文件的第1行中的数是计算出的加括号方式数.

问题描述:在一台超级计算机上,编号为1、2、...、n的n个作业等待批处理.批处理的任务就是将这n个作业分成若于批,每批包含相邻的若干作业.从时刻0开始,分批加工这些作业.在每批作业开始前,机器需要启动时间S,而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和.单独完成第i个作业所需的时间是ti,所需的费用是它的完成时刻乘以一个费用系数fi.同批作业将在同一时刻完成.例如,如果在时刻T开始一批作业.则这批作业的完成时刻均为T+S+最优批处理问题就是要确定总费用最小的批处理方案.例如,假定有5个作业等待批处理,且

如果采用批处理方案{,2},{3},{4,5},则各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56),因此,这个批处理方案总费用是153.

算法设计:对于给定的待批处理的n个作业,计算其总费用最小的批处理方案.

数据输入:由文件input.txt提供输入数据.文件的第1行是待批处理的作业数n,第2行是启动时间S.接下来每行有2个数,分别为单独完成第i个作业所需的时间是1和所需的费用系数.

结果输出:将计算出的最小总费用输出到文件output.txt中.

对任何非零偶数n,总可以找到奇数m和正整数k,使得n=m2^k.为了求出两个n阶矩阵的乘积,可以把一个n阶矩阵分成m×m个子矩阵,每个子矩阵有2^k×2^k个元素.当需要求2^k×2^k的子矩阵的积时,使用Strassen算法.设计一个传统方法与Strassen算法相结合的矩阵相乘算法,对任何偶数n,都可以求出两个n阶矩阵的乘积.并分析算法的计算时间复杂性.

下面的7个算法与本章中的二分搜索算法BinarySearch略有不同.如果算法不正确,请说明产生错误的原因.如果算法正确,请给出算法的正确性证明.

(2)

(3)

(4)

(5)

(6)

(7)

问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数.多重集S中重数最大的元素称为众数.例如,S={1,2,2,2,3,5}.多重集s的众数是2,其重数为3.

算法设计:对于给定的由n个自然数组成的多重集s,计算s的众数及其重数.

数据输入:输入数据由文件名为input.txt的文本文件提供.文件的第1行为多重集S中元素个数n;在接下来的n行中,每行有一个自然数.

结果输出:将计算结果输出到文件outputxt.输出文件有2行,第1行是众数,第2行是重数.

问题描述:大于1的正整数n可以分解为例如,当n=12时,有8种不同的分解式:

算法设计:对于给定的正整数n,计算n共有多少种不同的分解式.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n

结果输出:将计算出的不同的分解式数输出到文件output.txt.