女儿：这个算法题是五六年前面试者问我的，如今我也用它来问应聘者

前天晚上女儿在跟妈妈视频闲聊时，得知我最近开始跟小朋友们玩起数据结构和算法了。就随口告诉我她工作面试中曾经遇到过的一个问题。这么多年了还记得，想必比较经典。我一听，果然挺有意思。

问题的描述很简单：就是把分数精确表达出来，比如

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) 。

两天后，女儿发来一条信息：