算法合集之猜數(shù)問題的研究(編輯修改稿)
2024-11-12 20:33 本頁面
【文章內容簡介】 2 第一位學生 第二位學生 第三位學生 第四位學生 右面的例子中，對每位學生，都有三種不同的分組情況： ，三與四一組 ，二與四一組 ，二與三一組 當?shù)谝晃粚W生推測自己與第二位學生同一組時，可以計算出另一組學生頭上數(shù)的和 2+2=4，進而可以推測出在這種情況下自己頭上的數(shù)有可能為 41=3 有 4位學生，且每組有 2人 kA?定義 ，其中 定義分組 T：選取第 位學生為一組，剩下的學生為另一組（第k位學生在這一組）。則 mttt , 21 ???? miiAtTG1)(121 ???? nAtAtAt ?? ? ? ?knttt n \},2,1{, 121 ?? ??右面的例子中，對第一位學生，分組 T為，一與二一組，三與四一組。 注意到 m≥n/2，因此 knmiimii AAtAtTG ???? ??????111)(1111AtAtAtAnmiimiik ???? ??????對于 任意一個分組 X，設 ),( 21 kAAA n?? ? ? ?knxxx n \},2,1{, 121 ?? ??G(T)=2+2=4 =2+21=3 ≥2 kA?顯然有 )()( XGTG ?MXGA k ??? )(2????????nkiikii aaM111M=1+2+2=5 在上例中，考慮第一位學生 IOI2021國家集訓隊論文 猜數(shù)問題的研究 每位學生由于不能直接判斷頭上一定是某數(shù)，就只能采取排除法。由于他們不會猜錯，因此只需考慮他們如何能夠排除頭上數(shù)不同于實際的可能情況。顯然只有通過推理導出矛盾，才能夠得到有用的信息，排除某些可能情況。因此，問題的關鍵就在于分析如何導出矛盾。 IOI2021國家集訓隊論文 猜數(shù)問題的研究 IOI2021國家集訓隊論文 猜數(shù)問題的研究 我們已在定義中將能夠不通過推理直接猜出頭上的數(shù)的情況，稱之為“終結情形”?？紤]上面的分析，若某人處于“終結情形”，而他卻沒有猜出頭上的數(shù)，這顯然是一個矛盾。而對于不是“終結情形”的情況，則需要進行推理。因此問題轉變?yōu)榭紤]怎樣的情況為“終結情形”，以及怎樣的情況能夠通過推理轉變?yōu)椤敖K結情形”，可見解決問題的關鍵，在于深入分析“終結情形”。 IOI2021國家集訓隊論文 猜數(shù)問題的研究 而我們之所以在定義中將所有學生分成了兩類考慮：“一類情形”及“二類情形”，是受到原問題 《 聰明的學生 》 的啟發(fā)，雖然在推廣的問題中，頭上數(shù)最大的學生不再處于十分特殊的地位，即頭上數(shù)為其余學生頭上數(shù)的和，并且可能有不止一人頭上的數(shù)為最大數(shù)。但我們有理由相信這依然是解決問題的一個入手點。 考慮在分組 T的情況下 這種情況不同于實際情況，需要進行推理。得到結論：“一類情形”不可能為“終結情形”。 若不存在可能的分組 C滿足 ，即任意分組 即 要使得 為終結情形 ，必然要滿足在分組 T的情況下 。因此實際分組 B滿足 ，因此可得， 。 考慮“終結情形”的條件： ? ? knk AAtAAAA ???? 121 ,m a x ??當 為“一類情形 ” ),(21 kAAA n??當
教學課件相關推薦
鄂ICP備17016276號-1