亚洲天堂一级片-亚洲天堂三区-亚洲天堂久久精品成人-亚洲天堂毛片-久久国产欧美日韩高清专区-久久国产欧美日韩精品免费

由0和1構成的蟲子

有一條蟲子,它的整個身體由 n 節構成,每一節要么是有瑕疵的 1 ,要么是沒有瑕疵的 0 ,因而整個蟲子的身體結構就可以用一個 n 位 01 串來表示。你的目標是把整個蟲子變成 000...00 的完美形式。每一次,你可以砍掉蟲子最右側的一節,同時蟲子會在最左側長出新的一節,以保持蟲子的總長度不變。如果你砍掉的是一個 1 ,那么你可以指定蟲子在最左側長出的是 1 還是 0 ;但如果你砍掉的是一個 0 ,那么你無法控制蟲子會在最左側長出什么——它可能會長出 0 ,也可能會長出 1 ,因而你不得不假定,概率總是會和你做對,上天會竭盡全力地阻撓你。我們的問題是:不管蟲子的初始狀態是什么,你總能保證在有限步之內讓蟲子變成 000...00 嗎?
注意,這個問題可能沒有你想的那么簡單。顯然,我們必須得把一些 1 變成 0 ,這樣才能讓 1 的數目逐漸減少并最終消失。但是,如果只是簡單地每次都把 1 變成 0 ,最終也不見得就一定能取勝。比如,如果這條蟲子是 101 ,那么去掉最右邊的 1 并選擇在左邊長出一個 0 ,蟲子會變成 010 ;再把 010 右邊的 0 去掉后,如果不巧左邊長出的是 1 ,那么整條蟲子又會回到 101 的狀態。如此反復,將永遠也不能得到 000 。而更加聰明的方法則是先把 101 變成 110 ,下一步蟲子將會變成 111 或者 011 ,不管是哪種情況,接下來只需要逐個把 1 變成 0 就能獲勝了。運用恰當的策略才能走到終點,這無疑讓問題變得更加有趣。
不管蟲子一開始是什么樣子的,我們總能夠在有限步之內獲勝。下面是 Peter Winkler 給出的證明。讓我們把連續 n 次操作視為一輪操作,因而完成一輪操作正好讓蟲子的整個身體更新一次。于是,每一輪操作實際上相當于是從右到左依次考慮蟲子的每一位,每遇到一個 1 時你都可以選擇是否把它修改成 0 ,每遇到一個 0 時它都會隨機地被修改成 1 。我們一輪一輪地改造蟲子的身體,并且每一輪都采取這樣的策略:從最右端開始,每次遇到 1 都把它改成 0 ,直到第一次有 0 被改成 1 ;在此之后,不管新遇到的 0 變沒變,都保留所有的 1 不變。如果這一輪下來后,沒有 0 被改成 1 ,那么我們將會把所有的 1 都替換成 0 ,從而得到 000...00 的形式,直接獲得勝利;如果途中有 0 被改成了 1 ,那么整個蟲子作為一個二進制數將會嚴格增加。每經過一輪后,只要蟲子沒有變成 000...00 ,整個二進制數都會變得更大,最終將會變成 111...11 的形式,此時再也不會有 0 變成 1 了,于是按照我們的策略,在下一輪中,所有的 1 都會變成 0 ,從而獲得勝利。
北大青鳥網上報名
北大青鳥招生簡章
主站蜘蛛池模板: 免费看欧美一级特黄a毛片 免费看片aⅴ免费大片 | 99精品国产免费久久国语 | 高清在线观看自拍视频 | 国产成人精品aaaa视频一区 | 91色老99久久九九爱精品 | 色偷偷88欧美精品久久久 | 日韩精品视频免费在线观看 | 亚洲免费网 | 亚洲1314 | 免费一级特黄 欧美大片 | 黄a视频 | 亚洲精品国产一区二区在线 | 夜夜骚视频 | 久色乳综合思思在线视频 | 国产精品视频一区二区三区 | 思思久热re6这里有精品 | 在线播放第一页 | 国内精品久久影视 | 在线播放国产一区二区三区 | 欧美影院网站视频观看 | 手机看片国产日韩 | 国产成人精品亚洲 | 手机看片日韩高清国产欧美 | 国产在线精品一区二区三区 | 91免费视 | 99色播| 毛片1级 | 狠狠色婷婷丁香综合久久韩国 | 亚洲精品国产成人99久久 | 国产精品国产亚洲精品不卡 | 亚洲免费在线视频 | 精品亚洲大全 | 黄色成人免费观看 | 欧美高清一区 | 精品国产欧美精品v | 欧美一级毛片日韩一级 | 毛片高清 | 三级全黄的全黄三级三级播放 | 亚洲福利视频一区二区三区 | 中国老妇色xxxxx | 国产香蕉成人综合精品视频 |