集訓(xùn)隊作業(yè)孿生項鏈解題報告

1、孿生項鏈解題北江中學(xué)【正文】一、問題描述定義合法的項鏈為一個這樣的 01 串：一個長為 L 的 01 串，經(jīng)過 L-1次旋轉(zhuǎn)（即末尾一位移到開頭）一共可以得到 L 個 01 串，在這 L 個 01 串中，最小的 01 串只能有一個，那么這個最小的 01 串就是合法的項鏈。問題一：求出長度恰為 k 的合法項鏈的總數(shù)。問題二：給出一個長為 m 的合法項鏈 i，在所有長度小于等于 n 的合法且比 m 大的項鏈中找出一條最小的項鏈。二、問題分析這是一道數(shù)學(xué)題。第一個問可以用遞推來做。遞推式子如下：于n 顆珠子后不能得回自身的項鏈）。而這這 n 條項鏈中只有 1 條是最小的，因此 n 條項鏈只對應(yīng)到一條

2、合法的項鏈。所以 f(n)=m/n。再來計算通過旋轉(zhuǎn)小于 n 顆珠子可以得回自身的項鏈的條數(shù)。項鏈被分為 n/k 段，每段長度為 k 且完全相同。那么應(yīng)該就是有 2k 種了。但是，這 2k 里面又包含了通過旋轉(zhuǎn)小于 n 顆珠子可以得回自身的項鏈，這樣就可能出現(xiàn)重復(fù)。例如 n=8,k=4。把項鏈 01010101 去掉了，當(dāng)處理 n=8,k=2 時，又把項鏈 01010101 去掉了。這就重復(fù)計算了。因此理來解決，但還有一個更簡便的方法?？梢杂萌莩庠?2k 種項鏈中通過旋轉(zhuǎn)小于 n 顆珠子可以得回自身的項鏈去掉。例如上面那個例子，在 k=4 的時候，0101 旋轉(zhuǎn) 2 個珠子可以得回自身，所以

3、 并不計算它。但這樣絕不會漏情況，等到 k=2 的時候，01 就不是可以得回自身的項鏈了，這時就把這條項鏈減去了。因此2k，而是 f(k)*k。這時遞推式子就出來了。要減去的不是第二個問可以直接構(gòu)造出來。設(shè)輸入的長度為 m 的串為串 s，把珠子按 s 中的順序依次在后面循環(huán)加入，直到加滿 n 顆珠子為止。再把這個長度為 n 的二進制串加 1，去掉末尾的 0，就是了。例如：m=5，n=19，串 s 0為 01011 。 則按 照 上 面 的 方 法 ， 依 次 加 入 珠 子 ：。再加 1，去掉末尾的 0，得到 010110101101011011。由于構(gòu)造的串必須是原串的后繼合法串。最起碼要用

4、串 s 來填補后面的空位。因為用小于 s 的串來填的話會導(dǎo)致生成的串不合法（不是最小表示），用大于 s 的串來填會導(dǎo)致生成的串不是 s 的后繼。當(dāng) m|n 時，恰好填了 n/m 個串 s，這時的串是不合法的，因此必須加 1。當(dāng) m 不整除 n 時。設(shè) n=tm+k，其中 km。設(shè)串 s 的前 k 位的串為s1，剩下的位串 s2。則必有 s1s2。因為串 s 是一個合法串，它必定是最小表示的，所以把串 s 旋轉(zhuǎn) k 顆珠子后的到的新串 s2+s1 必定比 s1+s2 要大，所以 s1s2。若生成串的后 k 位是小于 s1 的。很明顯以后 k 位開頭才是最小表示，因此后 k 位不可能小于 s1。若

5、后 k 位等于 s1，則從后 k 位開始的串為 s1+s1+s2+，肯定比 s1+s2+要小（因為 s10 then inc(Long);End;Procedure Delete(Var a:Lion;b:Lion;VarLong:Long);Var i:longBegin;for i:=1 to Long do beginai:=ai-bi; if ai1) do dec(Long); End;Procedure Divide(Var a:Lion;Var Long:long;x:long);Var i,j,k:Long Begink:=0;for i:=Long downto 1 do b

6、eginj:=ai+k*10000; ai:=j div x; k:=j mod x;end;While (aLong=0)and(Long1)End;dodec(Long);Procedure Main1;Var i,j,Lbak:long bak:Lion;Begin;Fillchar(a,sizeof(a),0); a1:=1;L:=1;for i:=1 to k do BeginCheng(a,L,2);fi:=a;Longi:=L;for j:=1 to i shr 1 do if i mod j=0 then Beginbak:=fj; Lbak:=Longj; Cheng(bak,Lbak,j); Delete(fi,bak,Longi);End; Divide(fi,Longi,i);End; write(fk,Longk);for i:=Longk-1 downto 1 do beginif fk,i10 then write(000)else if fk,i100 then write(00) else if fk,i1 do beginck:=0;inc(ck-1); dec(k);end;for i:=1 to k do write(ci);wriEnd;n;Beginassign(input,Twi