計(jì)數(shù)器問題最優(yōu)解詳解
前幾天在專欄里看到一個(gè)有意思的問題：https://www.bilibili.com/read/cv682026
這個(gè)問題的最優(yōu)解是5次，當(dāng)然我是借助計(jì)算機(jī)來求解的。
首先這個(gè)問題可以化簡(jiǎn)成和數(shù)字無關(guān)的問題。我們把0到9看成一個(gè)環(huán)（不是抽象代數(shù)里的環(huán)），即0<1<2<3<4<5<6<7<8<9<0<1<……，并且以第1位數(shù)字為基準(zhǔn)，可以分別得到4個(gè)數(shù)字的大小次序，這里就用字母次序來表示大小次序。例如數(shù)字“1044”，因?yàn)?<4<0，可以表示成“ACBB”；數(shù)字“2018”，2<8<0<1，表示成“ACDB”。很容易發(fā)現(xiàn)，開頭字母永遠(yuǎn)是A，因?yàn)槲覀兪且缘?位數(shù)字為基準(zhǔn)。
對(duì)于1個(gè)4位數(shù)，轉(zhuǎn)換后得到的字母，稱為類型。
對(duì)于2個(gè)4位數(shù)，轉(zhuǎn)換后得到相同字母的，我們稱它們?yōu)橥悺?/strong>
在0000~9999這1萬個(gè)數(shù)字中，一共有26種類型，分別是：
ABCD ABDC ACBD ACDB ADBC ADCB
AABC AACB ABAC ACAB ABCA ACBA ABBC ABCB ACBB ABCC ACBC ACCB
AABB ABBA ABAB AAAB
AABA ABAA ABBB
AAAA
為什么表示成類型？因?yàn)閷?duì)于同類，很容易就能找到0代價(jià)（不按按鈕）的互轉(zhuǎn)方法，相當(dāng)于把10000種可能化簡(jiǎn)到26種可能。
先看轉(zhuǎn)輪，如果只轉(zhuǎn)一格，那么對(duì)于所有類型可能的結(jié)果是：
上面的結(jié)果排除了轉(zhuǎn)到自身類型的情況（已經(jīng)知道同類之間可以互轉(zhuǎn)，沒有討論的意義）。
只轉(zhuǎn)一格的話，可能會(huì)把當(dāng)前字母轉(zhuǎn)成下一個(gè)字母。例如ABAC，轉(zhuǎn)動(dòng)A，A可能會(huì)變成B，但絕不可能變成C，如果A要到達(dá)C，必定會(huì)經(jīng)過B。特殊的：C可能會(huì)變成A，因?yàn)镃到A中間沒有其他數(shù)字。ABAC轉(zhuǎn)動(dòng)A變成B后，就變成了BBBC，但是我們不會(huì)這樣寫，還要將它標(biāo)準(zhǔn)化成AAAB，即ABAC→AAAB。根據(jù)這些規(guī)則，我們可以枚舉轉(zhuǎn)輪對(duì)類型的全部變換結(jié)果。
再看按鈕，可以先將1萬個(gè)數(shù)字都轉(zhuǎn)成類型，并且將數(shù)字自增1的結(jié)果也轉(zhuǎn)成類型，這樣我們就得到了所有類型按了按鈕后的結(jié)果。如果結(jié)果可以用轉(zhuǎn)輪得到的話，或者結(jié)果是自身，那么排除這個(gè)結(jié)果。結(jié)合上面轉(zhuǎn)輪的結(jié)果，來個(gè)總的輸出：
有了這個(gè)轉(zhuǎn)換關(guān)系后，可以看出其實(shí)這就是個(gè)圖，而且是最短路徑問題。起點(diǎn)是AAAA(0000)，終點(diǎn)是ACDB(2018)，可以用Dijkstra算法之類的求出最短路徑，結(jié)果是5，路徑：AAAA * AAAB * AABC AABB * ABCC * ABCA * ACDB（*表示按了按鈕）。
畫張圖表示的話就是這樣：
