當前位置:編程學習大全網 - 編程軟體 - 編程:兩人輪流說數,每說壹個數x,就把x和x的因子拿出去;證明,先說的人壹定會贏。

編程:兩人輪流說數,每說壹個數x,就把x和x的因子拿出去;證明,先說的人壹定會贏。

C語言神馬的太復雜了。我從數學上給妳壹個證明吧:對於1~N這N個數,用以上遊戲規則,先行者必勝。

因為1是壹個很特殊的數,它是任何數的因子,所以1只能在壹開始寫下。

所以,我們可以先把1放壹邊,用剩下的2~N這N-1個數來進行這個遊戲(不妨叫做“新遊戲”),如果在“新遊戲”中是先行者必勝,那麽在原遊戲中先行者就按照“新遊戲”中的策略來寫就行;如果在“新遊戲”中是後行者必勝,那麽在原遊戲中先行者就先寫下1,然後按照“新遊戲”中後行者的策略來寫,即通過先寫下1來“讓先”。

綜合起來,先行者必勝。

接下來需要證明,對於任意k個數,按照以上遊戲規則,先行者要麽必勝,要麽必敗。

用數學歸納法證明:k=1時,對於先行者而言,當然是必勝局,結論成立。

假設對於1~n的所有自然數,結論都成立。當k=n+1時,先行者可以選擇寫下這n+1個數中的任意壹個數,有n+1種選擇。不管做哪種選擇,還剩下的可寫的數都小於或等於n,對於後行者來說,要麽是必勝局,要麽是必敗局。如果對於後行者來說全部是必勝局,那麽初始情況對於先行者來說是個必敗局;如果至少有壹種情況對於後行者來說是必敗局,那麽初始情況下先行者就可以做這種選擇,初始情況對於先行者來說是個必勝局。所以結論也成立。

綜上所述,任意k個數按照以上遊戲規則,對於先行者而言,都要麽是必勝局,要麽是必敗局。

歡迎提問。

  • 上一篇:C語言 如何實現返回主菜單
  • 下一篇:請問誰有用555定時器制作打鈴器的電路?
  • copyright 2024編程學習大全網