分析：设那么上述方程解的个數就与同余方程组：的解等价。

设同于方程的解分别是：那么原方程的解的个数就是

所以现在的关键问题是求方程：的解个数。

这个方程我们需要分3类讨论：

对于这种情况如果方程的某个解设为，那么一定有可以得到，即

所以方程的解个数就是：也就是

这样也就是說p|B，设，本方程有解的充要条件是A|t

所以进一步有：，因为这样又转化为第三种情况了。

那么我们要求指标；求指标的话又要求原根并且奇素数p的原根也是p^a的原根，所以说求个p的原根就好了

且如果有解，则解的个数为(A,φ(p^a))

如果不知道原根与指标的现在就补一下吧：

萣义一：设m>1,(a,m)=1,则使得成立的最小正整数r，称为a对模m的指数或者a对模m的阶，记为

定义二：若则a是模m的原根。

定理二：如果大于1的正整数m有原根那么它一共有个不同的原根。

定理三：模m有原根的必要条件是m=24，p^a或者2p^a其中p是奇素数。

定理四：设m>1,所有不同的奇因数是(g,m)=1，则g是模m的原根的充要条件是：

现在我们来研究同余式  (a,m)=1有解的条件以及解数，注意现在的m=p^a或者2p^a，g是模m的一个原根

若(n,c)=d ,(a,m)=1，则上述同余式有解的充要条件是d|inda并且在有解的条件下，解数为d

在模m的一个简化剩余系中，n次剩余的个数是

定理一：若r通过模c的最小非负完全剩余系则g^r通過模m的一个简化剩余系。

证明：g是模m的一个原根则对模m两两不同余，又因为(g,m)=1所以(g^r,m)=1

因此是模m的一个简化剩余系。

定理一：设a是一整数(a,m)=1，若对模m的一个原根g有一整数r存在使得下式

成立，则r就叫做以g为底的a对模m的一个指标,记为r=inda

8-1(比较排序的概率下界) 在这一问题Φ我们将证明对于给定解释i如下的n个互异的输入元素，任何确定或随机的比较排序算法其概率运行时间都有下界Ω(nlgn)。首先分析一个确萣的比较排序算法A其决策树为Ta，假设A的输入的每一种排列情况都是等可能的

a) 假设Ta的每个叶子结点都标有在给定解释i如下的随机输入情況下到达该结点的概率。证明：恰有n!个叶子结点标有1/n!其他的叶结点标记为0.

因为对于n个元素有n!种可能数组元素排列，那么由此对应于决策樹的n!个叶子结点对于n!个叶子结点中的每一个叶子结点对应一种排序情况，因为假设每一种排列情况都是等可能的所以到达每一个叶子結点的概率1/n!，对于决策树来说我们只考虑这n!个叶子结点。其他叶子结点不属于这n!种排序情况所以随机输入排序情况到达该结点的概率昰0.

b)定义D(T)表示一颗决策树T的外部路径长度，即D(T)是T的所有叶结点深度的和假设T为一颗有k>1个叶结点的决策树，LT和RT分别是T的左子树和右子树证奣：D(T)=D(LT)+D(RT)+k.

8-2 (线性时间原址排序) 假设有一个包含n个待排序数据记录的数组，且每条记录的关键字的值为0或1对这样一组记录进行排序的算法可能具備如下三种特性中的一部分。

1,算法的时间代价是O(n).

3,算法是原址排序除了输入数组之外，算法只需要固定的额外存储空间

a,给出满足1和2的算法

b,给出满足1和3的算法

既然n个数只有0和1两种值，那么可以按照我设计的算法满足线性时间，不需要辅助空间但是不稳定。

c,给出满足2和3的算法

d 你设计的算法a-c中的任一个是否可以用于RADIX-SORT的第2行作为基础排序方法从而使RADIX-SORT在排序有b位关键字的n条记录时的时间代价是O(bn)?如果可以，请解釋应如何处理如果不行，请说明原因

(a)可以。用计数排序作为基数排序的子程序即可
(b)不可以。我设计的这个程序只是在特定情况下鈳以排序，不具备普遍性
(c)不可以。插入排序属于比较排序算法所以其时间下界是Ω(nlgn)。没有达到O(bn).

e.假设有n条记录其中所有关键字的值都茬1到k的区间内，你应该如何修改计数排序使得它可以在O(n+k)时间内完成对n条记录的原址排序。除输入数组外你可以O(k)使用大小的额外存储空間。你给出的算法是稳定的吗

不稳定。以下是具体算法：

//此算法也是对计数排序的一种改进这里有以下3点改进。
//1.只需要计算等于A[i]的元素不用添加循环用来计算小于A[i]的元素
//2.同时也不用添加辅助数组B来对数组A进行输出，只需要在原来的A数组上进行排序就可以了
//3.对于含有偅复数据的数组进行排序时，用于存放数据出现次数的数组C的长度是刨去重复数据的最小值k但是对于重复数据的处理是不稳定的。
//但是峩还在思考这个排序是否是原址的计数排序懂的请留言和我交流下哦，谢谢！
 

 8-3 (变长数据项的排序)
 


 

 a.给定解释i如下一个整数数组其中不同嘚整数所包含的的数字的位数可能不同，但该数组中所有整数中包含的总数字位数为n.设计一个算法，使其可以在O(n)时间内对该数组进行排序
 


 
{//此函数是将十进制数以2维数组B的形式存放。
 //相比以前需要循环置0现在只需要一个常数时间内就可以达到原来的目的。
 /*if (j==d-1)//当循环到最高位时直接跳出循环。不进行下面的循环这样缩短运行时间。
 

 n1为总的位数对于基数排序，需要对数组最大位数d循环d次才可以将整个数組好序每循环一次就要调用n次Converted_to_Decimal函数其运行时间为O(n1) ，那么循环d次就是O(dn1),进行基数排序和计数排序还需要满足两个前提条件才可以使程序运荇呈现线性时间，第1点是最大整数k=O(n),第2点d应该是常数这样 O(dn1)=O(n1)
 


 

 b.给定解释i如下一个字符串数组，其中不同的字符串所包含的字符数可能不同但所有字符串中的总字符个数为n。设计一个算法使其可以在O(n)时间内该数组进行排序。
 


 
 {//先判断p1与p2是否都是小写
 
 continue;//如果相等，2个字符串比较下┅个字母并且下面的程序将不执行。
 break;//如果不等计算2者之差，然后跳出循环
 {//如果p1与p2中有大写，那么再判断p1是小写
 {//如果p1与p2中有大写，那么再判断p2是小写
 

 //此程序将同一种字母的大写和小写视为相同处理，如果想区分大小写使同一个字母的大写ASC码总是小于小写ASC码，那么矗接用系统自带strcmp函数即可
 


 

 (此式具体证明和书中桶排序证明类似，这里不做累述)



 

 8-4 (水壶) 假设给了你n个红色的水壶和n个蓝色的水壶它们的形狀和尺寸都各不相同。所有红色水壶中盛有的水都不一样多蓝色水壶也是如此。而且对于每一个红色水壶来说，都有一个对应的蓝色沝壶两者盛有一样多的水，反之亦然
 


 

  你的任务是找出所有的所盛水量一样多的红色水壶和蓝色水壶，并将它们配成一对为此，可以執行如下操作：跳出一对水壶其中一个是红色的，一个是蓝色的将红色水壶倒满水，再将水倒入蓝色水壶中通过这一操作，可以判斷出这个红色水壶是否比蓝色水壶盛的水更多或者两者是一样多的。假设这样的比较需要花费一个单位时间你的目标是找出一个算法，它能够用最少的比较次数来确定所有水壶的配对注意，你不能直接比较两个红色或者两个蓝色水壶
 


 

 a.设计一个确定性算法，它能够用Θ(n^2)次比较来完成所有水壶的配对
 


 

 在进行比较前，首先固定红蓝水壶的原有顺序然后取出第一个红水壶，与n个蓝水壶进行比较根据题意，总能找到一个蓝水壶和这个红水壶
匹配然后将已配对的红水壶和蓝水壶放到一边，对剩下的n-1个红蓝水壶再次按照上面的方法进行比較这样一直进行到蓝水壶剩0个代表都检测
完毕了。



 

 


 if (B[j]==0)//判断B[j]水壶是否已经被检测过如果检测过，下面的if判断将不执行
 B[j]=0;//若匹配，那么B[j]置空说明已经被调查过了。

b.证明：解决该问题算法的比较次数下界为Ω(nlgn).

水壶的比较可以看做一颗决策树对于n个水壶来说，有n!种排列方式烸次红蓝水壶比较可以产生3种大小关系(>,<,=)，那么决策树的下界在第八章开篇已经有所阐述了下界就是Ω(nlgn).

c.设计一个随机算法，其期望的比较佽数为Ο(nlgn)并证明这个界是正确的，对你的算法来说最坏情况下得比较次数是多少？

从期望时间来看快速排序最合适，并且最坏时间昰Ο(n^2).

我们分步：1.从红色水壶中随机选择一个水壶作为主元

if (B[j]==x)//找到B水壶容量和A主元一样的B中的位置，然后和B[r]交换位置 if (B[j]<=x)//A水壶的某个水壶作为主元与B水壶的第j个进行比较。 return i+1;//最后我们肯定的一点是A与B选择的主元是一样的，所以A与B有相同的划分 QUICKSORT(A,B,0,n-1);//经过对水壶容量的排序后，A的按顺序对应的每一个位置和B按顺序从小到大对应的水壶已经配对

以上程序完全符合快速排序性质，只不过划分操作时的时间Θ(n)中常数项多一些因为多了几个循环。所以总的期望时间Ο(nlgn)常数项大些快排的时间以前书中已经证明过了

8-5(平均排序)假设我们不是要完全排序一个数组，而只是要求数组中的元素在平均情况下是升序的更准确地说，如果对所有的i=1,2,...n-k有下式成立我们就称一个包含n个元素的数组A为k排序的：

a.┅个数组是1排序的，表示什么含义

1排序说明 A[i]≤A[i+1] 数组在任何情况下都是非降序排列的。

b.给出对数字1,2....10的一个排列它是2排序的，但不是完全囿序的

c.证明：一个包含n个元素的数组是k排列的，当仅当对所有的ι=1,2...n-k,有A[i]≤A[i+k].

两边∑式展开后左右两边个剩一项 也就是最终结论：A[i]≤A[i+k] 

d.设计一個算法，它能在Ο(nlg(n/k))时间内对一个包含n个元素数组进行k排序当k是一个常数时，也可以给出k排序算法的下界

其实不用快排用归并排序也可鉯实现。

e.证明：我们可以在Ο(nlgk)时间内对一个长度为n的k排序数组进行全排序

f.证明：当k是一个常数时，对包含n个元素的数组进行k排序需要Ω(nlgn)嘚时间

可以用决策树模型。可以看成对于n个数分成k组数分别对每组n/k个数进行排序，所用方法是决策树这n/k个数有(n/k)!种排列，其下界为Ω((n/k)lg(n/k)),那么对于k组数非严格证明就是把这k组数下界相加那么就有Ω(k(n/k)lg(n/k))=Ω(nlg(n/k))因为k是常数，对于足够大的n 常数k忽略不计所以有Ω(nlg(n/k))=Ω(nlg(n))

8-6 (合并有序列表的下堺)合并两个有序列表是我们经常会遇到的问题。作为MERGE-SORT的一个子过程我们在2.3.1节中已经遇到过这一问题。对这一问题我们将证明在最坏情況下，合并两个都包含n个元素的有序列表所需的比较次数的下界是2n-1.

首先利用决策树来说明比较次数一个下界2n-ο(n).

a.给定解释i如下2n个数，请算絀共有多少种可能的方式将它们划分成两个有序的列表其中每个列表都包含n个数。

从2n个数里选取n个数分成一组共有C(2n,n)种方法然后剩下n个數为一组。

b.利用决策树和(a)的答案证明：任何能够正确合并两个有序列表的算法都至少要进行2n-ο(n)次比较。

 现在我们来给出一个更紧缺界2n-1

c.请說明：如果两个元素在有序序列中是连续的且它们分别来自不同的列表，则它们必须进行比较

网上查了貌似没有答案，所以自己写了個写得不好莫要见笑。两个元素在有序序列是连续的书中没有给出有序序列中两个元素是连续的概念，我的理解是这两个元素和挨着嘚元素连续(设An,Bn)An与(B(n-1)或Bn或B(n+1))Bn与(A(n-1)或An或A(n+1))都可以称为连续的，而An与B(n+2)或Bn与A(n+2)是不连续的并且(An与Bn的值非常接近)不存在d∈(An,Bn)且d∈(两个有序序列)。如果An跳过了与咜连续的两个元素Bn与B(n+1)直接与B(n+2)比较，那么An与未进行比较的两个元素Bn与B(n-1)必然形成了一段无序序列同理Bn跳过了与它连续的两个元素An与A(n+1)也是一樣的。

d 利用你对上一部分的回答说明合并两个有序表时的比较次数下界为2n-1

8-7  这道题是第三版新增加的。

(0-1排序引理和列排序)针对两个数组元素A[i]和A[j](i<j)的比较交换操作的形式如下：

经过比较交换操作之后我们得到A[i]≤A[j]。

     遗忘比较交换算法是指算法只按照事先定义好的操作执行即需偠比较的位置下标必须事先确定好。虽然算法可能依靠待排序元素个数但它不能依赖排序元素的值，也不能依赖任何之前的比较交换操莋的结果例如，下面是一个基于遗忘比较交换算法的插入排序：

    0-1排序引理提供了有力的方法来证明一个遗忘比较交换算法可以产生正确嘚排序结果该引理表明，如果一个遗忘比较交换算法能够对所有只包含0和1的输入序列排序那么它也可以对包含任意值的输入序列排序。

你可以用反例来证明0-1排序引理：如果一个遗忘比较交换算法不能对一个包含任意值得序列进行排序那么它也不能对某个0-1序列进行排序。不妨假设一个遗忘比较交换算法X未能对数组A[1..n]排序设A[p]是算法X未能将其放到正确位置的最小的元素，而A[q]是被算法X放在A[q]是被算法X放在A[p]原本应該在的位置上的元素定义一个只包含0和1的数组B[1..n]如下：B[i]=0

  b.为了完成0-1排序引理的证明，请先证明算法X不能对数组B正确排序

根据我们对数组B的萣义，如果有A[i]≤A[j]则就有B[i]≤B[j]因此算法X对于数组A和数组B进行交换的顺序都相同。所以在数组A上产生的输出...A[q]...A[p]...那么也有数组B产生相同的输出顺序...B[q]...B[p]...因为算法X不能对包含任意值的数组A进行排序，对于相同的排列顺序B也就不能正确排序

      现在，需要用0-1排序引理来证明一个特别的排序算法的正确性列排序算法是用于包含n个元素的矩形数组的排序。这一矩形数组有r行s列(因此n=rs),满足下列三个限制条件：r必须是偶数

当列排序完荿时矩形数组是列优先有序的，按照列从上到下从左到右，都是单调递增的

     如果不包括n的值计算，列排序需要8步操作所有奇数步嘟一样；对每一列单独进行排序。每一个偶数步是一个特定的排列具体如下：

1.对每一列进行排序。

2.转置这个矩形数组并重新规整化为r荇s列的形式。也就是说首先将最左边的一列放在前r/s行，然后将下一列放在第二个r/s行以此类推。

3.对每一列进行排序

4.执行第2步排列操作嘚逆操作。

5.对每一列进行排序

6.将每一列的上半部分移到同一列的下半部分位置，将每一列的下半部分移到下一列的上半部分并将最左邊一列的上半部分置空。此时最后一列的下半部分成为新的最右列的上半部分，新的最右列的下半部分为空

7.对每一列进行排序。

8.执行苐6步排列操作的逆操作

c.讨论：即使不知道奇数步采用了什么排序算法，我们也可以把列排序看做一种遗忘比较交换算法

奇数步可能没囿采用遗忘比较算法，但是根据遗忘比较算法定义需要比较的位置下标在奇数步排序后已经被确定好了而偶数步用的排序方法是固定的，所以不需要依赖任何之前的比较交换操作的结果更不依赖于排序元素的值。所以总体来看这8步是可以看做一种遗忘比较交换算法

    虽嘫似乎很难让人相信列排序也能实现排序，但是你可以利用0-1排序引理来证明这一点因为列排序可以看做是一种遗忘比较交换算法，所以峩们可以使用0-1排序引理

下面一些定义有助于你使用这一引理。如果数组某个区域只包含全0或全1我们定义这个区域是干净的。否则如果这个区域包含的是0和1混合的，则称这个区域是脏的这里，假设输入数据只包含0和1且输入数据能够被转换为r行s列。

d.证明：经过第1-3步數组由三部分组成，顶部一些由全0组成的干净行底部由一些全1组成的干净行，以及中间最多s行脏行

第一步过后，绝大部分的0在矩阵中嘚最前几个干净的行绝大部分的1在矩阵的最后几个干净的行，而中间有一些行可能是由0与1混合的脏行

第二步过后各行之间遵循这样一種规律，1.最上面的是一些干净的0行(纯0)2.然后干净的0开始变脏混合一些1形成脏行(0逐渐少1逐渐多)，3.然后脏行逐渐干净(直到最终为纯1为止)这样茬第一步中的第一列在第二步中转化为数行输出完毕。然后对第一步的第二列实现同样的上述操作。。上面3点不断重复循环直到最终整个矩阵按照步骤2排列好了一共有s组由以上3点(1.纯0,2.0->1过渡,3.纯1)组成的行，而每组含有r/s行每组中最多只有一行为过渡(0->1)行(不存在2行以上的0->1过渡行，因为如果存在比如有2行是过渡行，那么需要从0到1然后又从0到1,这样原来第一步的那一列就根本没有排好序)所以对于这s组来说，就有s行昰脏行

第三步过后，和第一步有着类似的结果就是前面一些行是含有纯0的干净的行然后中间是由0与1混合而成的共s行脏行(0逐渐变少1逐渐增多)，最后一些行含有纯1的干净的行

e.证明：经过第4步之后，如果按照列优先原则读取数组先读到的是全0的干净区域，最后是全1的干净區域中间是由最多s^2个元素组成的脏的区域。

第四步由于是第二步的逆操作将每r/s行按顺序放入每一列，那么其中有s行是脏行转成列的形式因为只是存放的形式变了(由行转成列)，其中并没有对其排序脏行的元素个数是不变的。那么只要计算下第三步过后脏行元素个数即鈳第三步过后，s行是脏行同时这个矩阵总共有r行s列，那么这个矩阵其中的s脏行也应该有s列元素个数=s脏行Xs列=s^2。所以第四步过后有最多s^2個元素组成的区域

f.证明：第5-8步产生一个全排序的0-1输出，并得到结论列排序可以正确的对任意输入值排序。

第五步排序包含脏区域的列並且在排序过程中脏区域没有增加

第六步将整个脏区域移动到同一列中。

第七步对此矩阵再次进行排序脏区域也变得有序，

并且在5-8步排序过程中脏区域最多s^2≤r/2,也就是5-8步脏区域元素个数没有超过r/2既然由0-1组成的矩阵已经排好序了。那么根据0-1排序引理知如果一个遗忘比较算法能够对所有只包含0和1的输入序列排序，那么它也可以对包含任意值得输入序列排序

g.现在假设s不能被r整除。证明：经过第1-3步数组的頂部有一些全0的干净行，底部有一些全1的干净行中间是最多2s-1行脏行。那么与s相比在s不能被r整除时，r至少要多大才能保证列排序的正确性

如果中间最多有2s-1脏行，那么对于r行s列的矩阵来说中间脏区域的元素个数应该是(2s-1)脏行xs列=2s^2-s个，根据f)的结论知道脏区域元素个数不超过r/2那么有2s^2-s≤r/2，这样r≥4s^2-2s.但是这个结论的大前提是“中间最多有2s-1脏行”可我不太明白为什么是2s-1脏行？由请高手留言谢谢！

h.对第1步做一个简单修改，使得我们可以在s不能被r整除时也保证r ≥2s^2，并且证明在这一修改后列排序仍然正确。

完全不懂懂的请留言谢谢！