求最后推 出圈子的那個人原來的編號。約瑟夫算法可以用循環(huán)鏈表和數(shù)組來解(這兩個我會),下面2個程序 都是用來解決該算法的,其中第(2)直接給出答案,每個程序都有 證明和講解,程序1(遞歸法):#include #include int main(void) { int n; int m; int i = 0; int p; scanf("%d%d", &n, &m); while (++i n) { p = p - n + (p-n-1) / (m-1); } printf("%d\n", p); } return 0; } 程序2(遞推法):#include int main(void) { int i; int s = 0; int n; int m; scanf("%d%d", &n, &m); for (i = 2; i <= n; i++) { s = (s + m) % i; } printf("最后的獲勝者是: %d\n", s + 1); return 0; } 程序1證明:假設(shè)數(shù)到第p個數(shù)時遇到的數(shù),和數(shù)到第x個數(shù)到遇到的數(shù)一樣,且p - n < x < p,而且x % m != 0, 否則會被跳過和第個p數(shù)遇到的數(shù)肯定 不一樣,那么說明數(shù)了x個數(shù)之后再數(shù)一圈就數(shù)到了第p個數(shù),而數(shù)一圈 數(shù)過的數(shù)應(yīng)該是n減去要跳過的數(shù),因為已經(jīng)數(shù)過了x個數(shù),所以要跳過 [x / m]個數(shù)( []表示取整數(shù)部分 ),所以x + n - [x / m] = p 問題轉(zhuǎn)化為: p - n = x - [x / m]。
(1),且 x % m != 0, p - n < x
x / m - 1 < [x / m] x - x / m + 1 > x - [x / m] > x - x / m => [x - x / m + 1] >= x - [x / m] > [x - x / m] => [x - x / m] + 1 >= x - [x / m] > [x - x / m] => [x - x / m] + 1 >= x - [x / m] >= [x - x / m] + 1 => [x - x / m] + 1 = x - [x / m]( 代入(1)式 )=> p - n - 1 = [x - x / m] = [x * ( m - 1 ) / m] 。 (2) 因為x % m !=0 且 ( m - 1 ) % m != 0 => ( x * ( m - 1 ) ) % m != 0 由(2)式 => 0 < x * ( m - 1 ) - m * ( p - n - 1 ) m * ( p - n - 1 ) m * ( p - n - 1 ) / ( m - 1 ) [m * ( p - n - 1 ) / ( m - 1 )] [m * ( p - n - 1 ) / ( m - 1 )] + 1 <= x 。
(3) 由右邊: => x * ( m - 1 ) - ( m - 1 ) ( x - 1 ) * ( m - 1 ) x - 1 x - 1 x x = [m * ( p - n - 1 ) / ( m - 1 )] + 1 = [ p - n - 1 + ( p - n - 1 ) / ( m - 1 )] + 1 = p - n - 1 + [( p - n - 1 ) / ( m - 1 )] + 1 = p - n + [( p - n - 1 ) / ( m - 1 )] 由于計算機算整數(shù)除法直接就取整了,所以遞歸時就寫成 p = p - n + ( p - n - 1 ) / ( m - 1 ) 程序2證明:Josephus(約瑟夫)問題的數(shù)學方法(轉(zhuǎn))約瑟夫 (轉(zhuǎn)) 無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點:要模擬整個 游戲過程,不僅程序?qū)懫饋肀容^煩,而且時間復雜度高達O(nm),當n ,m非常大(例如上百萬,上千萬)的時候,幾乎是沒有辦法在短時間 內(nèi)出結(jié)果的。
愛德華·墨菲(Edward A. Murphy)是一名工程師,他曾參加美國空軍于 1949年進行的MX981實驗。這個實驗的目的是為了測定人類對加速度的承受極限。其中有一個實驗項目是將16個火箭加速度計懸空裝置在受試者上方,當時有兩種方法可以將加速度計固定在支架上,而不可思議的是,竟然有人有條不紊地將16個加速度計全部裝在錯誤的位置。于是墨菲作出了這一著名的論斷,并被那個受試者在幾天后的記者招待會上引用。
幾個月后這一“墨菲定律”被廣泛引用在與航天機械相關(guān)的領(lǐng)域。經(jīng)過多年,這一“定律”逐漸進入習語范疇,其內(nèi)涵被賦予無窮的創(chuàng)意,出現(xiàn)了眾多的變體,其中最著名的一條也被稱為 Finagle's Law(菲納格定律),具體內(nèi)容為:If anything can go wrong, it will.(會出錯的,終將會出錯。)。這一定律被認為是對"墨菲定律"最好的模仿和闡述。 墨菲定律(Murphy's Law)緣于美國一位名叫墨菲的上尉。他認為他的某位同事是個倒霉蛋,不經(jīng)意說了句笑話:“如果一件事情有可能被弄糟,讓他去做就一定會弄糟?!?/p>
這句話迅速流傳。經(jīng)過多年,這一“定律”逐漸進入習語范疇,其內(nèi)涵被賦予無窮的創(chuàng)意,出現(xiàn)了眾多的變體,“如果壞事有可能發(fā)生,不管這種可能性多么小,它總會發(fā)生,并引起最大可能的損失”、“If anything can go wrong, it will.(會出錯的,終將會出錯)”、“笑一笑,明天未必比今天好。”“東西越好,越不中用”、“別試圖教豬唱歌,這樣不但不會有結(jié)果,還會惹豬不高興!”
墨菲定律的原句是這樣的:If there are two or more ways to do something, and one of those ways can result in a catastrophe, then someone will do it.(如果有兩種選擇,其中一種將導致災(zāi)難,則必定有人會作出這種選擇。)
求最后推出圈子的那個人原來的編號。約瑟夫算法可以用循環(huán)鏈表和數(shù)組來解(這兩個我會),下面2個程序都是用來解決該算法的,其中第(2)直接給出答案,每個程序都有證明和講解,程序1(遞歸法):#include #include int main(void){int n;int m;int i = 0;int p; scanf("%d%d", &n, &m); while (++i n){ p = p - n + (p-n-1) / (m-1);} printf("%d\n", p); } return 0;}程序2(遞推法):#include int main(void){int i;int s = 0;int n;int m;scanf("%d%d", &n, &m);for (i = 2; i <= n; i++){s = (s + m) % i;}printf("最后的獲勝者是: %d\n", s + 1);return 0;}程序1證明:假設(shè)數(shù)到第p個數(shù)時遇到的數(shù),和數(shù)到第x個數(shù)到遇到的數(shù)一樣,且p - n < x < p,而且x % m != 0, 否則會被跳過和第個p數(shù)遇到的數(shù)肯定不一樣,那么說明數(shù)了x個數(shù)之后再數(shù)一圈就數(shù)到了第p個數(shù),而數(shù)一圈數(shù)過的數(shù)應(yīng)該是n減去要跳過的數(shù),因為已經(jīng)數(shù)過了x個數(shù),所以要跳過[x / m]個數(shù)( []表示取整數(shù)部分 ),所以x + n - [x / m] = p問題轉(zhuǎn)化為: p - n = x - [x / m]。
(1),且 x % m != 0, p - n < x
x / m - 1 < [x / m] x - x / m + 1 > x - [x / m] > x - x / m => [x - x / m + 1] >= x - [x / m] > [x - x / m] => [x - x / m] + 1 >= x - [x / m] > [x - x / m] => [x - x / m] + 1 >= x - [x / m] >= [x - x / m] + 1 => [x - x / m] + 1 = x - [x / m]( 代入(1)式 )=> p - n - 1 = [x - x / m] = [x * ( m - 1 ) / m] 。 (2)因為x % m !=0 且 ( m - 1 ) % m != 0 => ( x * ( m - 1 ) ) % m != 0由(2)式 => 0 < x * ( m - 1 ) - m * ( p - n - 1 ) m * ( p - n - 1 ) m * ( p - n - 1 ) / ( m - 1 ) [m * ( p - n - 1 ) / ( m - 1 )] [m * ( p - n - 1 ) / ( m - 1 )] + 1 <= x 。
(3)由右邊: => x * ( m - 1 ) - ( m - 1 ) ( x - 1 ) * ( m - 1 ) x - 1 x - 1 x x = [m * ( p - n - 1 ) / ( m - 1 )] + 1 = [ p - n - 1 + ( p - n - 1 ) / ( m - 1 )] + 1 = p - n - 1 + [( p - n - 1 ) / ( m - 1 )] + 1 = p - n + [( p - n - 1 ) / ( m - 1 )]由于計算機算整數(shù)除法直接就取整了,所以遞歸時就寫成 p = p - n + ( p - n - 1 ) / ( m - 1 )程序2證明:Josephus(約瑟夫)問題的數(shù)學方法(轉(zhuǎn))約瑟夫 (轉(zhuǎn))無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點:要模擬整個游戲過程,不僅程序?qū)懫饋肀容^煩,而且時間復雜度高達O(nm),當n,m非常大(例如上百萬,上千萬)的時候,幾乎是沒有辦法在短時間內(nèi)出結(jié)果的。