算法合集之猜數(shù)問題的研究(參考版)
2024-10-19 20:33本頁面
【正文】 從基本的例子入手分析 → 考慮問題的本質(zhì) → 從本質(zhì)入手分析矛盾 → 考慮何種情形為“終結(jié)情形” → 考慮何種情形能歸結(jié)到“終結(jié)情形” → 分情況討論并加以證明 → 得出結(jié)論并形成算法 相信對(duì)這樣一道問題的解決，對(duì)處理繁瑣的“思維嵌套”問題提供了一種可以借鑒的方法。 綜合兩方面的優(yōu)化，我們已經(jīng)較為圓滿的解決了這個(gè)問題。所以推理已不像 《 聰明的學(xué)生 》 那樣是一個(gè)線性結(jié)構(gòu)的推理，整個(gè)推理過程將成為樹狀結(jié)構(gòu)。 IOI2021國家集訓(xùn)隊(duì)論文 猜數(shù)問題的研究 由于關(guān)于這一部分的證明極其繁瑣，考慮到時(shí)間關(guān)系，下面只能給出一些結(jié)論 ?若 n個(gè)學(xué)生頭上的數(shù)都相等，則第一位學(xué)生可以猜出頭上的數(shù)。由于證明過程非常繁瑣，考慮到時(shí)間關(guān)系，這里將不給出詳細(xì)的證明過程。 ?當(dāng) 時(shí)，可以得到 ，且 。 。 由于 ， 因此 。因此，若 ， 不可能為終結(jié)情形 .。 考慮“終結(jié)情形”的條件： ? ? knk AAtAAAA ???? 121 ,m a x ??當(dāng) 為“一類情形 ” ),(21 kAAA n??當(dāng) 為“二類情形 ” ),(21 kAAA n?kk AA ?? ????? miimii AtAb11)()( TGBG ?),( 21 kAAA n?顯然 ，在此條件下，若存在可能的分組 C滿足 ， 。 若不存在可能的分組 C滿足 ，即任意分組 即 要使得 為終結(jié)情形 ，必然要滿足在分組 T的情況下 。 考慮在分組 T的情況下 這種情況不同于實(shí)際情況，需要進(jìn)行推理。 IOI2021國家集訓(xùn)隊(duì)論文 猜數(shù)問題的研究 而我們之所以在定義中將所有學(xué)生分成了兩類考慮：“一類情形”及“二類情形”，是受到原問題 《 聰明的學(xué)生 》 的啟發(fā)，雖然在推廣的問題中，頭上數(shù)最大的學(xué)生不再處于十分特殊的地位，即頭上數(shù)為其余學(xué)生頭上數(shù)的和，并且可能有不止一人頭上的數(shù)為最大數(shù)。而對(duì)于不是“終結(jié)情形”的情況，則需要進(jìn)行推理。 IOI2021國家集訓(xùn)隊(duì)論文 猜數(shù)問題的研究 IOI2021國家集訓(xùn)隊(duì)論文 猜數(shù)問題的研究 我們已在定義中將能夠不通過推理直接猜出頭上的數(shù)的情況，稱之為“終結(jié)情形”。顯然只有通過推理導(dǎo)出矛盾，才能夠得到有用的信息，排除某些可能情況。 注意到 m≥n/2，因此 knmiimii AAtAtTG ???? ??????111)(1111AtAtAtAnmiimiik ???? ??????對(duì)于 任意一個(gè)分組 X，設(shè) ),( 21 kAAA n?? ? ? ?knxxx n \},2,1{, 121 ?? ??G(T)=2+2=4 =2+21=3 ≥2 kA?顯然有 )()( XGTG ?MXGA k ??? )(2????????nki
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1