ACM新生培訓(xùn)講座

1、ACM新生培訓(xùn)講座Flavius Josephus弗拉維奧約瑟夫(37-100)是第一世紀(jì)時(shí)的著名的猶太歷史學(xué)家，也是軍官及辯論家。猶太古史(The Antiquities of the Jews)：記錄了由圣經(jīng)創(chuàng)世記至公元66年的猶太人歷史，以舊約圣經(jīng)為藍(lán)圖以及古人的傳說(shuō)，編寫(xiě)而成的猶太巨著。由于當(dāng)時(shí)的猶太人散居各地，此書(shū)成為各地土生猶太人重要學(xué)習(xí)典籍，亦為當(dāng)代神學(xué)學(xué)者及歷史學(xué)者所采用。 Flavius Josephus猶太戰(zhàn)記(War of the Jews) 約瑟夫自傳(The Life of Flavius Josephus) 約瑟夫環(huán)問(wèn)題在猶太人和羅馬的戰(zhàn)爭(zhēng)期間，約瑟夫和其他40個(gè)猶

2、太反叛者被羅馬軍隊(duì)困在一個(gè)山洞中，這些猶太反叛者寧愿自殺也不想被羅馬軍隊(duì)抓住，于是他們就站成一個(gè)環(huán)，從其中某個(gè)人開(kāi)始數(shù)，每數(shù)到的第三個(gè)人就要被殺掉，直到所有人都死光了。但是約瑟夫和他的一個(gè)朋友覺(jué)得自殺是沒(méi)有意義的，他們并不想死，于是他很快就算出了他和他的朋友應(yīng)該站在什么位置，使他們兩個(gè)成為最后被殺的那兩個(gè)人，并最終活了下來(lái)。 約瑟夫環(huán)問(wèn)題一問(wèn)題描述：編號(hào)從1到n的n個(gè)人站成一個(gè)環(huán)，從第一個(gè)人開(kāi)始，每數(shù)到 2的時(shí)候，去除該位置上的人，直到只剩下一個(gè)人，求剩下的這個(gè)人的編號(hào)。我們用J(n)表示人數(shù)為n的時(shí)候的解。 約瑟夫環(huán)問(wèn)題一去掉的人的編號(hào)依次為2,4,6,8,10,3,7,1,9,最后只剩下5

3、，所以J(10)=5。 約瑟夫環(huán)問(wèn)題一 約瑟夫環(huán)問(wèn)題一當(dāng)有偶數(shù)個(gè)人的時(shí)候，我們假設(shè)為2n個(gè)人，經(jīng)過(guò)第一圈之后還剩下n個(gè)人。 約瑟夫環(huán)問(wèn)題一剩下的n個(gè)人又是一個(gè)新的約瑟夫環(huán)問(wèn)題。 1 2 3 4 n-1 n 1 3 5 7 2n-3 2n-1J(2n)=2*J(n)-1. 約瑟夫環(huán)問(wèn)題一當(dāng)有奇數(shù)個(gè)人的時(shí)候，我們假設(shè)為2n+1個(gè)人，經(jīng)過(guò)第一圈之后還剩下n+1個(gè)人。去掉2n之后，下一個(gè)要去掉的就是1，最后還是剩下n個(gè)人。 約瑟夫環(huán)問(wèn)題一剩下的n個(gè)人還是一個(gè)新的約瑟夫環(huán)問(wèn)題。 1 2 3 4 n-1 n 3 5 7 9 2n-1 2n+1J(2n+1)=2*J(n)-1 約瑟夫環(huán)問(wèn)題一綜上，我們可以得

4、到如下遞推公式：該問(wèn)題可以在O(n)的復(fù)雜度解決。 約瑟夫環(huán)問(wèn)題一 約瑟夫環(huán)問(wèn)題一由上圖可以看出如果n為2的冪次方的時(shí)候，J(n)=1，這是顯然的。而在此之后J(n)以2遞增，因此我們可以猜測(cè):而事實(shí)上J(n)確實(shí)滿足上述規(guī)律，這個(gè)可以通過(guò)歸納法得到證明，至此，約瑟夫環(huán)問(wèn)題一可以用O(lg(n)的算法很好地解決。 約瑟夫環(huán)問(wèn)題二問(wèn)題描述：編號(hào)從1到n的n個(gè)人站成一個(gè)環(huán)，從第一個(gè)人開(kāi)始，每數(shù)到 m的時(shí)候，去除該位置上的人，直到只剩下一個(gè)人，求剩下的這個(gè)人的編號(hào)。我們用J(n,m)表示人數(shù)為n，每次都去掉第m個(gè)人的時(shí)候的解。 約瑟夫環(huán)問(wèn)題二為了方便，在這里我們把這n個(gè)人的編號(hào)改為從0到n-1，第一

5、個(gè)去掉的人總是m%n-1，剩下n-1個(gè)人，這n-1個(gè)人又組成了一個(gè)從第m%n個(gè)人開(kāi)始的新的約瑟夫環(huán)問(wèn)題。 m%n m%n+1 n-1 0 m%n-2 0 1 n-m%n-1 n-m%n n-2J(1,m)=0;J(n,m)=(m%n+J(n-1,m)%n, n=2.最后的結(jié)果加1就OK了。 這個(gè)問(wèn)題可以用O(n)的算法去解決。 約瑟夫環(huán)問(wèn)題三問(wèn)題描述：編號(hào)從1到n的n個(gè)人，站成一個(gè)環(huán)，每個(gè)人手里拿著一個(gè)卡片，卡片上寫(xiě)著一個(gè)非零的數(shù)，首先去掉編號(hào)為k的人，然后看他手里的卡片上的數(shù)字mk，如果mk0，則去掉他左手邊的第mk個(gè)人，如果mk0，則去掉他右手邊的第mk個(gè)人。重復(fù)上述步驟，直至只剩下一個(gè)人，問(wèn)這個(gè)人的編號(hào)是多少。 約瑟夫環(huán)問(wèn)題三不要妄想再找到公式了，模擬是唯一的選擇，但是直接模擬的話，該算法的復(fù)雜度將達(dá)到O(n2).事實(shí)上，我們可以用線段數(shù)對(duì)此做