1.
2.
3. 4.
5.
6. 7. 8. 9.
10.
算法 POWERSET(s.p) //计算集合s的幂集p PS1 [递归出口] IF s={} THEN (p←{}. RETURN. ) PS2 [递归调用] x←anyelement(s). POWERSET(s-{x}.q). p = q; FOR (y∈q) p=p∪(y∪{x}) . ▌
递归算法指的是包含递归过程的算法，递归过程指的是
调用自身的过程。 算法的有限性要求必须存在递归出口。 递归算法中通过对自身的调用，总能逐步逼近，直到满 足递归出口。
习题 2-1
观察幂集的性质
集合元素个数 S={a} S={a,b} S={a,b,c} 1 2 3
幂集元素个数 P(S)={{},{a}} P(S)={{},{a},{b},{a,b}} 2 4 21 22 23
习题 2-3
证明对正整数 n ≥ 3，算法BS的元素比较次数 T（n）
≤ 5n/3 - 2
0 T(n)= 1 T( n/2 )+T( n/2 )+2
数学归纳法证明
证明 n=3 时成立 假设3 n < k 时都成立 证明 n= k时也成立
习题 2-1
利用性质 | P(S) |=2n
集合S={ a , b , c }
A= {a, b, c,} 7= 1 1 1 A= { b c} 3= 0 1 1
a b c
1 1 1
b c
0 1 1
习题 2-1
P(S) = P(S-a) ∪ {x ∪ a |x ∈ P(S-a)}
习题 2-1
P(S)={{},{a},{b},{c},{a,b} 8 …{a,b,c}}
S={a,b,c,d} 4
P(S)={{},{a},{b},{c},{d}{a 16 24 b},{bc}…{a,b,c,d}}
习题 2-1
| P(S) | = | P(S-1) | * 2
| P(S) |=2n
P(S) = P(S-a) ∪ {P(S-a) ∪ a} /* S的幂集P(S)可以表示为S-a的幂集P(S-a)然后 再并上 P(S-a)中任意一个集合并上元素a */
n=1 n=2 n>2
习题 2-3
证明（数学归纳法）：
当n=3时，T（3）=T（2）+T（1）+2=3 （5*3）/3 - 2=3； 命题成立。
假设n<k时命题成立，即
T（i） ≤ 5i/3 – 2
i <k
当 n=k 时 T（k）=T( k/2 )+T( k / 2 )+2
。 。 。 。 。 （ 2） 。 。 。 。 。 （ 3）
命题得证
习题 2-4
算法 IBS(A,1,n.fmax,fmin) //计算最大最小元 IBS1 [初始化] fmin ← fmax ← A[1]. CREATS(S). S (1,n).
精品课件！
精品课件！
IBS2 [迭代过程] WHILE (S ≠ NULL) （ （l,r） S. IF r-l =0 THEN ( fmax ← max(fmax, A[r]). fmin ← min(fmin, A[r]). ) IF r – l =1 THEN (IF A[l] < A[r] THEN ( fmax ← max(fmax, A[r]). fmin ← min(fmin, A[l]). ) ELSE ( fmax ← max(fmax, A[l]). fmin ← min(fmin, A[r]). ) ) mid ← (l r ) / 2 S (1,mid). S (mid+1,n). ) ▌
k / 2 ≥ k/2 来自成立 当 k≥3 时，k>
。 。 。 。 。 （ 1）
k/2 )≤5*( k/2 )/3-2 T( k / 2 )≤5*( k / 2 )/3-2 T( k / 2 + k/2 = k k / 2 k / 2 )+2 T（k） =T( )+T( k / 2 k / 2 ≤ [5*( )/3-2]＋[5*( )/3-2]+2 k / 2 k / 2 = 5*( + ) / 3 - 2 = 5*k / 3 – 2


习题 2-1
若S是n个元素的集合，则S的幂集是S的所有可能
子集的集合。例如，若S = {a,b,c}，则Powerset (S) = { {} , {a} , {b} , {c} , {a , b} , {a , c} , {b , c} , {a , b , c} } 请给出一个计算幂集Powerset (S) 的递归算法。 递归算法的思想