1樓：ming
step(A,n)//find true chip of Aif n<=2
return A[n]
let J be a new [n/2]-length arrayJ=JUDGE(A)
k1=J(>1).length //J(>1)=if k1
let B be a new k1-length arrayfor i = 1 to [n/2]
if J[i]>1
B[i]=A[2*i]
if (!mod(k1,2))&&mod(n,2)B=[B,A[n]]
k1=k1+1
return step(B,k1)
else
return step(B,k1)
else
return A[n]
自己寫的演算法
2樓：小只南瓜
正好做到這道題，我覺得還可以這樣：（當n為奇數時）
考慮到「好壞」「壞壞」中壞的個數大於等於好的個數（因每對至少有乙個壞的），斷定「好好」+零頭中好大於壞，
若檢測為「好好」的對數為奇數，此時，全好的對數大於等於全壞的個數+1（若不然，全好的對數小於全壞的對數，加上零頭後仍不滿足好大於壞），因此每對捨棄乙個後，好的個數大於等於壞的個數+1，此時可以直接捨棄零頭。
而當檢測為「好好」的對數為偶數時，有兩種情況：
1. 全好的對數等於全壞的對數。此時因為在「好好」+零頭中，好大於壞，斷定零頭為好。必須留下以保證好大於壞。
2. 全好的對數大於等於全壞的對數加2（事實上一定等於全壞的對數加2k），每對捨棄乙個後，留下的部分中好仍大於等於壞加2，此時留下零頭也不影響好大於壞。
因此，每次迭代時只需考察每次當n為奇數時「好好」對數的奇偶性。零頭在「好好」對數為奇數時捨棄，偶數時留下即可。
3樓：牛肉豆腐乾
1.1假定剩下的零頭是x，
a的個數一定大於等於b的個數＋1
因為我們得保證 a*2 +c >= b*2 + c + 1 + 1
於是，我們選出裡面兩兩互相說對的配對，並且，減半，（ox不可能互相說對）
剩下了a個o ， d個x，還有乙個零頭 x，
其中 d <= b,
於是 a > d+1,
我們用這 a＋d個去檢測最後的零頭，發現，有超過一半以上（不含一半）的，說那個零頭晶元是壞的，於是，我們去掉零頭，於是，我們剩下a個o，d個x，其中a >= d+1..然後迭代。
1.2假定剩下的零頭是o，
於是a >= b.
於是我們也分別減半，於是
剩下 a個o，d個x，其中a>=b>=d,
在用這些減半的晶元去測那個零頭時，沒有超過一半（不含一半）的說那個晶元是壞的，於是，我們接受晶元。
於是，我們剩下 a＋1個好晶元，d個壞晶元，而且 a＋1 >= d+1..然後迭代。
2.如果沒有零頭，
那麼a >= b+1
於是減半，於是還是保證好的晶元a個大於壞的晶元b個，於是..迭代。
我不清楚題主是在什麼地方卡住了。。。希望在此按照上面的思路在試一下。
關於演算法導論定理3 1，為什麼感覺快速排序的時間複雜度不滿足這個定理？
猥瑣的民工 快排無論你用什麼方法選基點，在運氣最倒霉的情況下，也就是每次選基點都剛好碰上區間內的最大或最小值的時候，複雜度提高為O n 2 是必然會發生的。儘管這種情況發生的概率極低，大約是1 n 但在你重複測試了n 次之後很可能會發生一次。 TravorLZH 對於某一種情況下 好 壞 平均 的時...
實現《演算法導論》中的習題,用什麼語言比較好
姚鋼強 首先明確的是如果你還不熟悉任何一門程式語言，看這本書適不適合你的。因為演算法在沒有程式設計能力的前提下就是廢物。所以用你熟悉的語言去寫這些演算法，目的是學習演算法，而不是糾結於語言。 孫立 我當年是用Turbo Pascal練的，我覺得即使今天應該也還是乙個不錯的選擇。依我看用資料結構比較簡...
《演算法導論》有什麼好的學習心得？
某天 對於這種題，大佬們肯定這麼答 1.必須看原版！原版！原版都看不懂學個鳥程式設計！2.要有數學基礎！不去補基礎！這本書你看不了！3.做題！做題！題都做不明白就是你智商有問題！對於大佬來說，英文很簡單 數學基礎很紮實 智商也高，但不適合我們這種小渣渣 你聽大佬的話，一般都逃不出幾個結局 買來原版書...