算法合集之組合游戲略述——淺談SG游戲的若干拓展及PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 算法合集之組合游戲略述算法合集之組合游戲略述淺談淺談SG游游 戲的若干拓展及戲的若干拓展及 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2 2頁頁 每一個(gè)可移動(dòng)的棋子都要移動(dòng)每一個(gè)可移動(dòng)的棋子都要移動(dòng)Every-SG游游 戲戲 無向圖刪邊游戲無向圖刪邊游戲 第1頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第3 3頁頁 怎么辦？怎么辦？ 怎么辦？怎么辦？ 怎么辦？怎么辦？ 第2頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第4 4頁頁 第3頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第5 5頁頁 的后繼狀

2、態(tài)為 的后繼狀態(tài)為 為終止?fàn)顟B(tài) vuvSGustep uSGvuvSGustep v vstep 0)(1)(min 0)(0)(1)(max 0 )( 第4頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第6 6頁頁 所有先手必勝的游戲的所有先手必勝的游戲的step值為奇數(shù)！值為奇數(shù)！ 所有先手必?cái)〉挠螒虻乃邢仁直財(cái)〉挠螒虻膕tep值為偶數(shù)！值為偶數(shù)！ 第5頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第7 7頁頁 輸 贏 長(zhǎng) 短 第6頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第8 8頁頁 如何做？如何做？ 如何做？如何做

3、？ 如何做？如何做？ 第7頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第9 9頁頁 第8頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1010頁頁 考慮：已知左圖的考慮：已知左圖的SG值，如何求右圖的值，如何求右圖的SG值值 根節(jié) 點(diǎn) GG G G圖圖 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) GG G G圖圖 由特殊例子給出猜想：由特殊例子給出猜想： SG( G )=SG( G )+1 第9頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1111頁頁 點(diǎn)相連的邊點(diǎn)相連的邊 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) GG G G圖圖 第10頁/共34頁 7/20/20

4、21石家莊二中石家莊二中 賈志豪賈志豪第第1212頁頁 GG 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) GG 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) SG值為值為0 第11頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1313頁頁 第12頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1414頁頁 GG 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) 根節(jié) 點(diǎn) 中間節(jié)點(diǎn) GG SG值不確值不確 定定 第13頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1515頁頁 根節(jié)點(diǎn) GG SG值為值為0到到SG( G G )-1， 取不到取不到SG( G G ) 至多有至多有N-1N-1個(gè)點(diǎn)個(gè)點(diǎn)根節(jié) 點(diǎn)

5、 中間節(jié)點(diǎn) GG 至多有至多有N N個(gè)點(diǎn)個(gè)點(diǎn) SG值為值為1到到SG(G G )，取不取不 到到SG(G G )+1 由歸納假設(shè)由歸納假設(shè) 定理：定理：SG(G)=SG(G)+1 第14頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1616頁頁 GG1 1 GG2 2 GGT T 根節(jié) 點(diǎn) 第15頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1717頁頁 GG1 1 GG2 2 GGT T GG1 1GG2 2GGT T 不夠本質(zhì)！ 第16頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1818頁頁 GG1 1 GG2 2

6、GGT T GG1 1GG2 2GGT T 十分完美！ 第17頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第1919頁頁 GG1 1 GG2 2 GGT T GG1 1GG2 2GGT T 十分完美！ ) 1) (.) 1) ()( 1 T GSGGSGGSG 第18頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2020頁頁 謝謝觀看！ Thanks for watching ！ 歡迎提問歡迎提問！ Question Time ！ 第19頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2121頁頁 不要慌！不要慌！ 不要慌！

7、不要慌！ 不要慌！不要慌！ 第20頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2222頁頁 根節(jié) 點(diǎn) 根節(jié) 點(diǎn) 奇環(huán)刪邊后，左右兩個(gè)分奇環(huán)刪邊后，左右兩個(gè)分 支的邊數(shù)同奇偶，異或值支的邊數(shù)同奇偶，異或值 不可能為不可能為1 1 第21頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2323頁頁 根節(jié) 點(diǎn) 根節(jié) 點(diǎn) 偶環(huán)刪邊后，左右兩個(gè)分偶環(huán)刪邊后，左右兩個(gè)分 支的邊數(shù)異奇偶，異或值支的邊數(shù)異奇偶，異或值 不可能為不可能為1 1 第22頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2424頁頁 第23頁/共34頁 7/20/

8、2021石家莊二中石家莊二中 賈志豪賈志豪第第2525頁頁 第24頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2626頁頁 轉(zhuǎn)換成功！ 變成了樹！變成了樹！ 第25頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2727頁頁 謝謝觀看！ Thanks for watching ！ 歡迎提問歡迎提問！ Question Time ！ 第26頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2828頁頁 好難！好難！ 好難！好難！ 好難！好難！ 第27頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第2929頁

9、頁 第28頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第3030頁頁 GG1 1GG2 2 GG3 3 GG4 4 GG5 5 GG6 6 縮成一個(gè)點(diǎn)！ 第29頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第3131頁頁 GG1 1 GG2 2 GG3 3 GG4 4 GG5 5 GG6 6 縮成一個(gè)點(diǎn)！ 第30頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第3232頁頁 GG1 1 GG2 2 GG3 3 GG4 4 GG5 5 縮成點(diǎn)加邊！ 第31頁/共34頁 7/20/2021石家莊二中石家莊二中 賈志豪賈志豪第第3333頁頁 GG1