Applied Example II of Recursion in F#

原創(chuàng)：顧遠(yuǎn)山
著作權(quán)歸作者所有，轉(zhuǎn)載請標(biāo)明出處。

遞歸是一種直接或間接調(diào)用自身的計(jì)算過程项炼，無關(guān)計(jì)算機(jī)揭厚，也無關(guān)具體的編程語言，只是遞歸的嵌套特性不適合人腦計(jì)算救崔，通常會(huì)借助計(jì)算機(jī)等工具執(zhí)行罷了惶看，今時(shí)今日幾乎所有現(xiàn)代的編程語言都支持遞歸，本文使用的是函數(shù)式編程語言F#六孵。

遞歸小例（一）中筆者通過Excel列數(shù)轉(zhuǎn)列名對遞歸的應(yīng)用進(jìn)行了簡示纬黎。有偶無獨(dú)，最近還是處理超大Excel文件過程中狸臣，筆者又發(fā)現(xiàn)了一個(gè)場景莹桅， 也可以通過應(yīng)用遞歸實(shí)現(xiàn)解決方案。

問題描述

把漢字表述的數(shù)字轉(zhuǎn)換成阿拉伯?dāng)?shù)字烛亦。

問題分析

對Excel熟悉的同學(xué)應(yīng)該知道诈泼，有個(gè)函數(shù)叫numberstring，可以很方便地把阿拉伯?dāng)?shù)字轉(zhuǎn)換成漢字表述的數(shù)字煤禽，比如：

Excel中的numberstring函數(shù)

我們的問題正好是Excel中numberstring函數(shù)反過來的場景铐达，然而Excel并沒有提供現(xiàn)成的函數(shù)供大家直接使用。雖然網(wǎng)上也有一堆插件可以完成快速轉(zhuǎn)換檬果，但獨(dú)立思考加自己動(dòng)手瓮孙，是防止少年智障、青年孕傻和老年癡呆的必要操作选脊，建議大家多實(shí)踐杭抠。

動(dòng)手寫碼前，最好先分析一下漢字表述的數(shù)字都有哪些特點(diǎn)恳啥。假設(shè)待轉(zhuǎn)換的數(shù)字都是簡體中文漢字表述的整數(shù)（無小數(shù)點(diǎn)及小數(shù)部分）偏灿，則該數(shù)字可由兩種元素組合而成：

• 普通數(shù)字，如“五”钝的、“六”翁垂、“七”等；
• 量級(jí)單位硝桩，如“十”沿猜、“百”、“千”等碗脊。
  其中普通數(shù)字可以作為前綴修飾量級(jí)單位啼肩，比如“五十”、“六百”、“七千”等疟游；量級(jí)單位也可以作為前綴修飾量級(jí)單位呼畸，比如“八千萬”、“九萬億”等颁虐。根據(jù)實(shí)際應(yīng)用蛮原，我們不妨約定對于漢字表述的數(shù)字，有效的量級(jí)單位僅限于：
• 億
• 萬
• 千
• 百
• 十

為了避免不規(guī)范的表述另绩，我們可以進(jìn)一步約定：量級(jí)單位能且僅能被小于其自身的量級(jí)單位所修飾儒陨。比如，“六十萬”笋籽、“七百億”和“八千萬億”等蹦漠，這些都是有效的漢字?jǐn)?shù)字；但“六萬十”车海、“七億百”和“八億萬千”等笛园，這些并不是有效的漢字?jǐn)?shù)字；甚至類似“三千千”侍芝、“四萬萬”和“五億億”這種充滿年代感的漢字?jǐn)?shù)字研铆，也被排除在外。

約定好普通數(shù)字和量級(jí)單位的規(guī)則后州叠，問題突然就變得非常簡單棵红，我們同樣可以直接套用遞歸的思路求解：

• 欲求整體漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字，只要先求得“億”前的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字咧栗，乘以100000000再加上“億”后的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字即可
• 欲求“億”前(后)的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字逆甜，只要先求得“萬”前的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字，乘以10000再加上“萬”后的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字即可
• 欲求“萬”前(后)的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字致板，只要先求得“千”交煞、“百”、“十”前的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字斟或，分別乘以1000错敢、100、10再加上“十”后的漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字即可
• ……

上面這段文字略顯冗長不好理解缕粹，我們用符號(hào)把它簡化一下，其實(shí)就是以下過程：

• 轉(zhuǎn)換(整個(gè)數(shù)字) = 轉(zhuǎn)換((億前)+億+(億后))
• 轉(zhuǎn)換(億前) = 轉(zhuǎn)換((萬前)+萬+(萬后))
• 轉(zhuǎn)換(萬前) = 轉(zhuǎn)換((千前)+千+(百前)+百+(十前)+十+各位數(shù)字)
• ……

之所以說它是遞歸的思路纸淮，是因?yàn)?em>轉(zhuǎn)換這個(gè)過程一直都在一層一層地調(diào)用它自己平斩，只是被調(diào)用時(shí)傳入的對象不同罷了。

我們舉一個(gè)直觀的例子咽块，把漢字表述的數(shù)字“八千萬億”轉(zhuǎn)換成阿拉伯?dāng)?shù)字绘面，應(yīng)用遞歸的思路計(jì)算過程如下：

• 八千萬億 = (八千萬) 億 = (八千萬) x 100000000
• 八千萬 = (八千) 萬 = (八千) x 10000
• 八千 = (八) 千 = (八) x 1000
• 八 = 8

綜上，八千萬億 = 8 x 1000 x 10000 x 100000000 = 8000000000000000

換一個(gè)例子，從下面的圖示可以看得更清楚：

遞歸的轉(zhuǎn)換思路

分析到此揭璃，計(jì)算過程無非是：通過遞歸的方式可以很方便地求出各個(gè)量級(jí)前對應(yīng)的數(shù)字晚凿，乘以量級(jí)對應(yīng)的倍數(shù)再求和，便能得到整個(gè)漢字?jǐn)?shù)字對應(yīng)的阿拉伯?dāng)?shù)字瘦馍。

邏輯非常直接歼秽，但必須小心的是：并非每個(gè)漢字?jǐn)?shù)字包含所有量級(jí)，中間缺失若干量級(jí)是很常見的情组，比如一千二百零三萬就缺失了“億”及以上所有量級(jí)燥筷、“十(萬)”、“千”院崇、“百”肆氓、“十”和個(gè)位，而且根據(jù)實(shí)際情況底瓣，漢字?jǐn)?shù)字缺失量級(jí)的個(gè)數(shù)和位置都很靈活谢揪，所以準(zhǔn)確定位到量級(jí)關(guān)鍵字并切分其前后部分相當(dāng)關(guān)鍵，可以使用正則表達(dá)式處理（輔助函數(shù)R可參考筆者之前的文章活動(dòng)模式小例(二)中
RegexMatch活動(dòng)模式)捐凭。

解決方案

我們使用函數(shù)式編程語言F#實(shí)現(xiàn)拨扶。
首先，轉(zhuǎn)換普通數(shù)字柑营，如下：

let d v = 
    match "零一二三四五六七八九".ToCharArray() |> Array.tryFindIndex (fun e -> (e|>string)=v) with 
    | Some x -> x |> bigint 
    | None -> -1I

其次屈雄，漢字?jǐn)?shù)字去零（“零”在漢字?jǐn)?shù)字中用作缺失量級(jí)的補(bǔ)足，需要去掉官套，避免影響計(jì)算邏輯）酒奶，如下：

let z (s:string) = s.Replace("零","")

最后，結(jié)合正則表達(dá)式活動(dòng)模式易得遞歸的轉(zhuǎn)換函數(shù)p奶赔，如下：

let rec p c a =
    match z c with
    | "" -> a
    | R "^(.{1,})(億)(.*)$" [_;v;_;r]-> p r (a + (p v 0I)*100000000I)
    | R "^(.{1,})(萬)(.*)$" [_;v;_;r]-> p r (a + (p v 0I)*10000I)
    | R "^(.{1,})(千)(.*)$" [_;v;_;r]-> p r (a + (d v)*1000I)
    | R "^(.{1,})(百)(.*)$" [_;v;_;r]-> p r (a + (d v)*100I)
    | R "^(.{1,})(十)(.*)$" [_;v;_;r]-> p r (a + (d v)*10I)
    | R "^(十)(.*)$"        [_;_;r  ]-> p r (a + 1I*10I)
    | v -> a + (d v)

上述代碼中有個(gè)特殊處理的邏輯：在漢字?jǐn)?shù)字中“十”前面部分沒有數(shù)字時(shí)等價(jià)于“一十”惋嚎，需要與其他量級(jí)單位的匹配模式有所區(qū)分。

還有一個(gè)有趣的點(diǎn)——例子用到了大數(shù)類型站刑，其實(shí)用Int64類型也可以另伍，畢竟人最大值為9223372036854775807，遠(yuǎn)遠(yuǎn)夠用绞旅。若要換成Int64類型摆尝，那上面的F#的代碼中數(shù)字的后綴“I”改成“L”即可。

結(jié)果驗(yàn)證

隨意給定兩個(gè)測試用例因悲，調(diào)用上述轉(zhuǎn)換函數(shù)p堕汞，如下：

["一千二百三十四萬五千六百七十八億零九萬零一";"十六萬億"] |> List.iter (fun e -> printfn "%s:%A" e (p e 0I))

轉(zhuǎn)換結(jié)果為：
一千二百三十四萬五千六百七十八億零九萬零一: 1234567800090001
十六萬億: 16000000000000

符合預(yù)期，測試通過晃琳，解決方案可用讯检。

小結(jié)

本文通過把漢字表述的數(shù)字轉(zhuǎn)換成阿拉伯?dāng)?shù)字的小例琐鲁，演示了遞歸在日常數(shù)據(jù)處理中的應(yīng)用。F#作為函數(shù)式編程語言人灼，編寫遞歸函數(shù)解決問題围段，不但邏輯清晰，而且簡單易讀投放，事半功倍奈泪。