第一章
Procedure F(A,n)
i←n;
count←0;m←0;
while i≥0 do
if A[i] =1 then count←count + 1;
else if count mod 2 ≠ 0 then
m←m+1;
endif
count←0;
endif
i←i -1;
repeat
if m＞ 0 then return(false)
else return(true)
endif
End F
int judge(int A[ ],int n)
{
int I,flag = 0;
for(i=1;i≤n;i++) {
while(A[i]== 1 && i≤n)
flag =(flag + A[i++])%2;
if(flag) return(false);
}
return(true); //如果没有任何连续为 1的序列？
}
int check(int a[ ],int n)
{
int i=0,k=0,flag = 1;
while(i＜ n) {
k=0;
while(A[i]== 0) i++; //&&i<n
while(A[i]== 1) k++; // i++ && i<n
if(k%2) {
flag = 0;
break;
}
return(flag); //如果没有任何连续为 1的序列？
}
第二章
2,化简递推关系式
∵ g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(n)
∴ 可令 f(n)=c2n(或简单令 f(n)=n，或 f(n)=c2n＋ b),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+cn
=4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn
=…
=2kT(n/2k)+kcn
若 n=2k,则 k=logn
∴T(n)=cn+cnlogn=O(nlogn)
当 n∈[2 k,2k+1),T(n)=cn+cnlogn=Θ(nlogn)
∵g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(1)
∴ 可令 f(n)=c2(或简单令 f(n)=1),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+c
=4T(n/4)+2c+c
=8T(n/8)+22c+2c+c=…
=2kT(n/2k)+(1+2+22+…+2 k-1)c=cn+(2k-1)c
=2cn-c=O(n)
典型错误令 g(n)=a,f(n)=bn+c(a,b,c为常数）
则 T(n)=2T(n/2)+bn+c
=4T(n/4)+2bn+2c+bn+c
=…
=2kT(n/2k)+bn(1+2+…+2 k-1)
+c(1+2+…+2 k-1)
=2kT(n/2k)+(bn+c)(2k-1)
故得,T(n)=Θ(n2)
5.三分法
low highmid1 mid2
mid1=low +
mid2=high -
3/)( lo wh ig h?
3/)( lo wh ig h?
3/)(22
3/)(1
l o wh i g hm i d
l o wh i g hm i d
E=2I+3n
二元比较树＝ >三元比较树？
第三章
9,
① 若 k个作业可以按照题目中给出的方法安排执行时间又不违反任何作业的期限要求，显然 J可行。
②若 J可行，则对 J应该存在一个题目中所说的处理序列。设这一序列是 δ =i1i2…i k
序列的特点是：若作业 ij在 j时刻执行,ij不违反期限要求，且其后的 k-j个作业也不违反各自的期限。 ij是按照从后往前找其执行时间 j：后边的 k-j个执行单元或者不满足其期限要求，或已经为先前考虑的其它作业占用，而这些作业是不能被推迟执行的。
证 1：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k
现设按题目要求调整序列 δ ’ 。
在 δ ’ 的调度序列中任取 1个作业 ri(1≤i≤k)
● 若 i=dri，则 ri的位置不变
●若 i＜ dri且 dri=j，则将 ri调整到 j处，原 ri+1,ri+2,…,r j向前移一位，可保持调整后的 drj≥j （ 1≤j≤k ）
每做一次调整后，调整的元素固定下来。若调整过程中,ri要调的地方的作业 rj已被固定,则继续往前寻找，直到找到没有被固定的作业处。
每次在 δ ’ 中选取 1个没有固定下位置的作业做上述调整,k次后作业顺序定下来，且能保持作业的执行时间不不违反作业期限，故 J可行时，
用题中给出的方法可以解决作业排序。
存在的问题：调整后得到的调度序列可能不等于题目中给出的调度序列。
证 2：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k 。作业 i在时间片 [α i-1,α i]被调度,α i≤d i。
设其中任两个作业 i,j，若 α i≤d j且 di≥d j，可将 i,j互换。互换后仍为可行解。
如此循环得一新序列，对任两个作业 i,j均有 α i≤ α j且 di≤d j。
设新得可行解序列为 i1,i2,…,i k，则有 di1≤ d i2≤…≤ d ik。对这样得一个新得序列，再进行调度,
从作业 ik开始，若其分配得时间片为 [α ’ -1,α ]，将 α ’ 变为 α,
使 α 是满足 1≤ α ≤ dik得最大整数，且 [α -1,α ]是 空的 。这样依次调度
ik-1,ik-2,…,i 1，得到的新的调度序列不变，仍为 J的一个可行解序列。
问题：后半部分没有说清楚。
最后的序列有可能就是按仅 di1≤ d i2≤…≤ d ik的顺序定的次序。
证 3：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k 。若 δ ’ 不符合题目要求的规则。
设按照题目要求给出的调度序列是,δ =i1i2…i k，使得 1≤r≤d i的最大整数，且时间片 [rj-1,rj]只为作业 i占用。
δ ’≠ δ 。
设 a是使得 ra≠i a的最大下标。由规则，设 rb＝ ia,b＜ a，
将 δ ’ 中 ra与 rb互换，则产生的新序列 δ,=s 1s2…s k能满足规则。
重复上述步骤，就能将 δ ’ 转换成 δ 而又不违反任何一个期限。
问题：预先假设 δ 是可行的。
证 4：证明在对 J按照题目要求的处理方式安排执行时间时，空白时间片 [α-1,α]一定存在。
设考察 J中作业的顺序是 j1,j2,…j k：
第一个考察的作业是 j1，则 j1被安排在时间片 [dj1-1,dj1]
处执行，不违反 j1的期限要求。
第二个考察的作业是 j2，若 dj2≠d j1，则 j2可被安排在时间片 [dj2-1,dj2]处执行，该时间片为空，且序列可行。否则，
j2可被安排在时间片 [dj1-2,dj1-1]处执行，该时间片为空，序列也可行。
假设已经考察了 l－ 1个作业，这些作业均被安排至合适的时间片处理。其特点是，这 l-1个作业均被安排至可能的最晚执行时间：对其中的任意作业 i的执行时间片 [α-1,α]，或者
α=di，或者 α是题目要求的最大时间片，而 α之后的任何作业不能因为作业 i而移动，否则不能正常执行。
设现在最新考察的作业是 jl。
若 [djl-1,djl]空，则 jl即可安排至该时间片执行，满足题目要求。否则，从 djl-1开始，从后往前考察各时间片，找到第一个可用的空时间片 [α-1,α],jl即可安排在该时间片执行，该时间片必存在。
反证。如果不存在这样的时间片，则在先前考察的 l-1个作业中恰好有 djl个作业被分配到 1～ djl时间片上。对于这些作业，或者执行期限小于等于 djl，或者其所处时间片以后的有效执行时间已经为其它作业占用，且不能推迟其中任何作业的执行 —— 这些作业已经被分配到最迟可能执行的时间片。不论哪种情况，作业 jl都不能如期被执行，这与 J是可行解相矛盾。
包含 jl的序列是当前的一个可行调度序列。重复上述过程，
J中的 k个 可以按照题目要求的方式安排好所有 k个作业。
11,
① 证明思路,设内结点数为 m，则总的结点数为 m+n。
又每个内结点的度为 k，所以有 n+m=mk+1
∴n=m(k -1)+1
证 1：设内结点数为 m，则树中有 mk条边，其中 m-1条通向内结点（根除外），则剩余的 mk-m+1条边通向外部结点，则有,n＝ m(k-1)+1
证 2：设内部结点数为 m，则总的度数为 mk。将 mk个度分为两类：
仅与内部结点相联的度,m-1个与一个内结点和一个外部结点相联的度,mk-(m-1)
则外部结点的个数为 n＝ mk－ (m-1)＝ m(k-1)+1
② 证明：当 n mod(k-1)＝ 1时，一棵 k元树存在的可能性，且证明这颗树的内结点度都为 k。
∵ n mod(k-1)＝ 1
∴ 可设 n=m(k-1)+1
有①可知这颗 k元树存在的可能性关于结点度的证明：
证 1：假设存在一个度不为 k的结点，其度设为 k’,k’ ＜ k.
则外部结点数,n=(m-1)k+k’ -(m-1)=(m-1)(k-1)+k’
与 n mod(k-1)=1(k’≠1) 矛盾故，这颗树中所有内结点的度均为 k。
问题：若 k’=1? （将度为 1的内结点和其子树合并，不影响树的基本形态）
证 2：构造方法开始时设 n个已知外部结点集合为 J,|J|=n
从 J中取出 k个结点，创建一个根结点 T，将取出的 k个结点作为 T的子结点，构造一棵 k元的子树。将 T加入 J中。则 J
中元素总数减少 k-1.
重复上述过程，即可得到一棵 k元树：
在过程的每一步，使 J中结点数减少 k-1个，设经过 m’
步,J中的结点数减少为 n－ m’(k -1).
又,n＝ m(k-1)+1
所以，剩余结点数,(m-m’)(k -1)+1
若 m=m’,最后 J中仅剩 1个结点，即为整棵 k元树的根结点。
证 3：（不完备）
令 n=m(k-1)+1
设有一棵树，其外部结点数为 n，外部结点数为 m，并设每个内部结点的度分别为 d1,d2,…,d m。
若 di＞ k(i=1,2,…,m),则该树的结点总数为,
又树中的结点总数为 m＋ n，故 m+n>mk+1，
所以,n>(k-1)m+1，与假设矛盾同理可设，若 di＜ k(i=1,2,…,m),则该树的结点总数为
，又树中的结点总数为 m＋ n，故 m+n<mk+1，
所以,n<(k-1)m+1，与假设也矛盾。
所以该树中结点的度应该为 k。
问题：没有说明为什么不能有不同的度。
m
i
i mkd
1
11
m
i
i mkd
1
11
证 4：（没有说明问题）
由 ①可 令 n=m(k-1)+1
∴ k+m(k-1)(k-1)=m+n
∴ 存在这样的树 T，其内部结点数为 m，度为 k，外部结点数为 n
问题：没有说明当 n mod (k-1)=1时，若存在这样一棵 k元树，则其内部结点均为 k。
Procedure F(A,n)
i←n;
count←0;m←0;
while i≥0 do
if A[i] =1 then count←count + 1;
else if count mod 2 ≠ 0 then
m←m+1;
endif
count←0;
endif
i←i -1;
repeat
if m＞ 0 then return(false)
else return(true)
endif
End F
int judge(int A[ ],int n)
{
int I,flag = 0;
for(i=1;i≤n;i++) {
while(A[i]== 1 && i≤n)
flag =(flag + A[i++])%2;
if(flag) return(false);
}
return(true); //如果没有任何连续为 1的序列？
}
int check(int a[ ],int n)
{
int i=0,k=0,flag = 1;
while(i＜ n) {
k=0;
while(A[i]== 0) i++; //&&i<n
while(A[i]== 1) k++; // i++ && i<n
if(k%2) {
flag = 0;
break;
}
return(flag); //如果没有任何连续为 1的序列？
}
第二章
2,化简递推关系式
∵ g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(n)
∴ 可令 f(n)=c2n(或简单令 f(n)=n，或 f(n)=c2n＋ b),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+cn
=4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn
=…
=2kT(n/2k)+kcn
若 n=2k,则 k=logn
∴T(n)=cn+cnlogn=O(nlogn)
当 n∈[2 k,2k+1),T(n)=cn+cnlogn=Θ(nlogn)
∵g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(1)
∴ 可令 f(n)=c2(或简单令 f(n)=1),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+c
=4T(n/4)+2c+c
=8T(n/8)+22c+2c+c=…
=2kT(n/2k)+(1+2+22+…+2 k-1)c=cn+(2k-1)c
=2cn-c=O(n)
典型错误令 g(n)=a,f(n)=bn+c(a,b,c为常数）
则 T(n)=2T(n/2)+bn+c
=4T(n/4)+2bn+2c+bn+c
=…
=2kT(n/2k)+bn(1+2+…+2 k-1)
+c(1+2+…+2 k-1)
=2kT(n/2k)+(bn+c)(2k-1)
故得,T(n)=Θ(n2)
5.三分法
low highmid1 mid2
mid1=low +
mid2=high -
3/)( lo wh ig h?
3/)( lo wh ig h?
3/)(22
3/)(1
l o wh i g hm i d
l o wh i g hm i d
E=2I+3n
二元比较树＝ >三元比较树？
第三章
9,
① 若 k个作业可以按照题目中给出的方法安排执行时间又不违反任何作业的期限要求，显然 J可行。
②若 J可行，则对 J应该存在一个题目中所说的处理序列。设这一序列是 δ =i1i2…i k
序列的特点是：若作业 ij在 j时刻执行,ij不违反期限要求，且其后的 k-j个作业也不违反各自的期限。 ij是按照从后往前找其执行时间 j：后边的 k-j个执行单元或者不满足其期限要求，或已经为先前考虑的其它作业占用，而这些作业是不能被推迟执行的。
证 1：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k
现设按题目要求调整序列 δ ’ 。
在 δ ’ 的调度序列中任取 1个作业 ri(1≤i≤k)
● 若 i=dri，则 ri的位置不变
●若 i＜ dri且 dri=j，则将 ri调整到 j处，原 ri+1,ri+2,…,r j向前移一位，可保持调整后的 drj≥j （ 1≤j≤k ）
每做一次调整后，调整的元素固定下来。若调整过程中,ri要调的地方的作业 rj已被固定,则继续往前寻找，直到找到没有被固定的作业处。
每次在 δ ’ 中选取 1个没有固定下位置的作业做上述调整,k次后作业顺序定下来，且能保持作业的执行时间不不违反作业期限，故 J可行时，
用题中给出的方法可以解决作业排序。
存在的问题：调整后得到的调度序列可能不等于题目中给出的调度序列。
证 2：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k 。作业 i在时间片 [α i-1,α i]被调度,α i≤d i。
设其中任两个作业 i,j，若 α i≤d j且 di≥d j，可将 i,j互换。互换后仍为可行解。
如此循环得一新序列，对任两个作业 i,j均有 α i≤ α j且 di≤d j。
设新得可行解序列为 i1,i2,…,i k，则有 di1≤ d i2≤…≤ d ik。对这样得一个新得序列，再进行调度,
从作业 ik开始，若其分配得时间片为 [α ’ -1,α ]，将 α ’ 变为 α,
使 α 是满足 1≤ α ≤ dik得最大整数，且 [α -1,α ]是 空的 。这样依次调度
ik-1,ik-2,…,i 1，得到的新的调度序列不变，仍为 J的一个可行解序列。
问题：后半部分没有说清楚。
最后的序列有可能就是按仅 di1≤ d i2≤…≤ d ik的顺序定的次序。
证 3：
若 J是可行解，则必存在调度序列 δ ’=r 1r2…r k，使得
drj≥j,1≤j≤k 。若 δ ’ 不符合题目要求的规则。
设按照题目要求给出的调度序列是,δ =i1i2…i k，使得 1≤r≤d i的最大整数，且时间片 [rj-1,rj]只为作业 i占用。
δ ’≠ δ 。
设 a是使得 ra≠i a的最大下标。由规则，设 rb＝ ia,b＜ a，
将 δ ’ 中 ra与 rb互换，则产生的新序列 δ,=s 1s2…s k能满足规则。
重复上述步骤，就能将 δ ’ 转换成 δ 而又不违反任何一个期限。
问题：预先假设 δ 是可行的。
证 4：证明在对 J按照题目要求的处理方式安排执行时间时，空白时间片 [α-1,α]一定存在。
设考察 J中作业的顺序是 j1,j2,…j k：
第一个考察的作业是 j1，则 j1被安排在时间片 [dj1-1,dj1]
处执行，不违反 j1的期限要求。
第二个考察的作业是 j2，若 dj2≠d j1，则 j2可被安排在时间片 [dj2-1,dj2]处执行，该时间片为空，且序列可行。否则，
j2可被安排在时间片 [dj1-2,dj1-1]处执行，该时间片为空，序列也可行。
假设已经考察了 l－ 1个作业，这些作业均被安排至合适的时间片处理。其特点是，这 l-1个作业均被安排至可能的最晚执行时间：对其中的任意作业 i的执行时间片 [α-1,α]，或者
α=di，或者 α是题目要求的最大时间片，而 α之后的任何作业不能因为作业 i而移动，否则不能正常执行。
设现在最新考察的作业是 jl。
若 [djl-1,djl]空，则 jl即可安排至该时间片执行，满足题目要求。否则，从 djl-1开始，从后往前考察各时间片，找到第一个可用的空时间片 [α-1,α],jl即可安排在该时间片执行，该时间片必存在。
反证。如果不存在这样的时间片，则在先前考察的 l-1个作业中恰好有 djl个作业被分配到 1～ djl时间片上。对于这些作业，或者执行期限小于等于 djl，或者其所处时间片以后的有效执行时间已经为其它作业占用，且不能推迟其中任何作业的执行 —— 这些作业已经被分配到最迟可能执行的时间片。不论哪种情况，作业 jl都不能如期被执行，这与 J是可行解相矛盾。
包含 jl的序列是当前的一个可行调度序列。重复上述过程，
J中的 k个 可以按照题目要求的方式安排好所有 k个作业。
11,
① 证明思路,设内结点数为 m，则总的结点数为 m+n。
又每个内结点的度为 k，所以有 n+m=mk+1
∴n=m(k -1)+1
证 1：设内结点数为 m，则树中有 mk条边，其中 m-1条通向内结点（根除外），则剩余的 mk-m+1条边通向外部结点，则有,n＝ m(k-1)+1
证 2：设内部结点数为 m，则总的度数为 mk。将 mk个度分为两类：
仅与内部结点相联的度,m-1个与一个内结点和一个外部结点相联的度,mk-(m-1)
则外部结点的个数为 n＝ mk－ (m-1)＝ m(k-1)+1
② 证明：当 n mod(k-1)＝ 1时，一棵 k元树存在的可能性，且证明这颗树的内结点度都为 k。
∵ n mod(k-1)＝ 1
∴ 可设 n=m(k-1)+1
有①可知这颗 k元树存在的可能性关于结点度的证明：
证 1：假设存在一个度不为 k的结点，其度设为 k’,k’ ＜ k.
则外部结点数,n=(m-1)k+k’ -(m-1)=(m-1)(k-1)+k’
与 n mod(k-1)=1(k’≠1) 矛盾故，这颗树中所有内结点的度均为 k。
问题：若 k’=1? （将度为 1的内结点和其子树合并，不影响树的基本形态）
证 2：构造方法开始时设 n个已知外部结点集合为 J,|J|=n
从 J中取出 k个结点，创建一个根结点 T，将取出的 k个结点作为 T的子结点，构造一棵 k元的子树。将 T加入 J中。则 J
中元素总数减少 k-1.
重复上述过程，即可得到一棵 k元树：
在过程的每一步，使 J中结点数减少 k-1个，设经过 m’
步,J中的结点数减少为 n－ m’(k -1).
又,n＝ m(k-1)+1
所以，剩余结点数,(m-m’)(k -1)+1
若 m=m’,最后 J中仅剩 1个结点，即为整棵 k元树的根结点。
证 3：（不完备）
令 n=m(k-1)+1
设有一棵树，其外部结点数为 n，外部结点数为 m，并设每个内部结点的度分别为 d1,d2,…,d m。
若 di＞ k(i=1,2,…,m),则该树的结点总数为,
又树中的结点总数为 m＋ n，故 m+n>mk+1，
所以,n>(k-1)m+1，与假设矛盾同理可设，若 di＜ k(i=1,2,…,m),则该树的结点总数为
，又树中的结点总数为 m＋ n，故 m+n<mk+1，
所以,n<(k-1)m+1，与假设也矛盾。
所以该树中结点的度应该为 k。
问题：没有说明为什么不能有不同的度。
m
i
i mkd
1
11
m
i
i mkd
1
11
证 4：（没有说明问题）
由 ①可 令 n=m(k-1)+1
∴ k+m(k-1)(k-1)=m+n
∴ 存在这样的树 T，其内部结点数为 m，度为 k，外部结点数为 n
问题：没有说明当 n mod (k-1)=1时，若存在这样一棵 k元树，则其内部结点均为 k。
