女兒：這個算法題是五六年前麵試者問我的，如今我也用它來問應聘者

前天晚上女兒在跟媽媽視頻閑聊時，得知我最近開始跟小朋友們玩起數據結構和算法了。就隨口告訴我她工作麵試中曾經遇到過的一個問題。這麽多年了還記得，想必比較經典。我一聽，果然挺有意思。

問題的描述很簡單：就是把分數精確表達出來，比如

1/3 = 0.(3)
10/3 = 3.(3)
2/5 = 0.4
1/7 = 0.(142857)

括號代表循環小數的循環部分。

鬼使神差，當我在白紙上隨便用一個分數找找感覺時，用的居然是 3/29。結果整張 A4 紙寫到邊了，還未見循環。到開始寫程序了，才看到循環部分有 28 位之多。

開始並不順利，特別想用字符串匹配的辦法入手，卻入不了手。結果在淋浴的時候計上心來，找到了問題的關鍵點，迎刃而解。後來女婿告訴我，他也曾被誤導到字符串匹配方向去過。感覺真像個陷阱。

我把算法思想（時間複雜度為O(n)，n是分母）提交給女兒。她說：“That’s the simplest solution”。

這是完整的c++程序：

下麵是一些測試結果：

$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 3
b: 29
0.(1034482758620689655172413793)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 3
b: 290
0.0(1034482758620689655172413793)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1
b: 7
0.(142857)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1
b: 13
0.(076923)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 10
b: 3
3.(3)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1000
b: 7
142.(857142)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1000
b: 13
76.(923076)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 2343
b: 34
68.9(1176470588235294)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 2343
b: 340
6.89(1176470588235294)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 4123513463463665646
b: 700000
5890733519233.80806(571428)
$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1
b: 331
0.(00302114803625377643504531722054380664652567975830815709969788519637462235649546827794561933534743202416918429)

$ g++ -std=c++11 -Wall gt.cpp && ./a.out
a: 1
b: 3331
0.(000300210147102972080456319423596517562293605523866706694686280396277394175923146202341639147403182227559291504052836985890123086160312218552987090963674572200540378264785349744821374962473731612128489942960072050435304713299309516661663164214950465325728009606724707295106574602221555088561993395376763734614229960972680876613629540678474932452716901831281897328129690783548483938757129990993695586910837586310417292104473131191834283998799159411588111678174722305613929750825577904533173221254878414890423296307415190633443410387271089762833983788652056439507655358751125788051636145301711197838486940858601020714500150105073551486040228159711798258781146802761933353347343140198138697087961573101170819573701591113779645752026418492945061543080156109276493545481837286100270189132392674872410687481236865806064244971480036025217652356649654758330831582107475232662864004803362353647553287301110777544280996697688381867307114980486340438306814770339237466226358450915640948664064845391774241969378564995496847793455418793155208646052236565595917141999399579705794055839087361152806964875412788952266586610627439207445211648153707595316721705193635544881416991894326028219753827679375562894025818072650855598919243470429300510357250075052536775743020114079855899129390573401380966676673671570099069348543980786550585409786850795556889822876013209246472530771540078054638246772740918643050135094566196337436205343740618432903032122485740018012608826178324827379165415791053737616331432002401681176823776643650555388772140498348844190933653557490243170219153407385169618733113179225457820474332032422695887120984689282497748423896727709396577604323026118282797958570999699789852897027919543680576403482437706394476133293305313719603722605824076853797658360852596817772440708495947163014109876913839687781447012909036325427799459621735214650255178625037526268387871510057039927949564695286700690483338336835785049534674271990393275292704893425397778444911438006604623236265385770039027319123386370459321525067547283098168718102671870309216451516061242870009006304413089162413689582707895526868808165716001200840588411888321825277694386070249174422095466826778745121585109576703692584809366556589612728910237166016211347943560492344641248874211948363854698288802161513059141398979285499849894926448513959771840288201741218853197238066646652656859801861302912038426898829180426298408886220354247973581507054938456919843890723506454518162713899729810867607325127589312518763134193935755028519963974782347643350345241669168417892524767337135995196637646352446712698889222455719003302311618132692885019513659561693185229660762533773641549084359051335935154608225758030621435004503152206544581206844791353947763434404082858000600420294205944160912638847193035124587211047733413389372560792554788351846292404683278294806364455118583008105673971780246172320624437105974181927349144401080756529570699489642749924947463224256979885920144100870609426598619033323326328429900930651456019213449414590213149204443110177123986790753527469228459921945361753227259081356949864905433803662563794656259381567096967877514259981987391173821675172620834584208946262383668567997598318823176223356349444611227859501651155809066346442509756829780846592614830381266886820774542179525667967577304112879015310717502251576103272290603422395676973881717202041429)

其實程序的空間複雜度也是 O(n) 。

兩天後，女兒發來一條信息：