分数のクラスとかあったら便利じゃねと考えて、標準にあるだろうと思ったら無かった。
演算子をオーバーライドしたので構造体
分子・分母共に BigInteger を使う。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace Charlotte.Tools { public struct Fraction { public BigInteger Numer; public BigInteger Denom; public Fraction(BigInteger numer, BigInteger denom) { this.Numer = numer; this.Denom = denom; } public static implicit operator Fraction(long value) { return new Fraction(value, 1); } public static Fraction operator ++(Fraction instance) { return instance + new Fraction(1, 1); } public static Fraction operator --(Fraction instance) { return instance - new Fraction(1, 1); } public static Fraction operator +(Fraction a, Fraction b) { Reduction(ref a, ref b); return new Fraction(a.Numer + b.Numer, b.Denom); } public static Fraction operator -(Fraction a, Fraction b) { Reduction(ref a, ref b); return new Fraction(a.Numer - b.Numer, b.Denom); } public static Fraction operator *(Fraction a, Fraction b) { return new Fraction(a.Numer * b.Numer, a.Denom * b.Denom); } public static Fraction operator /(Fraction a, Fraction b) { return new Fraction(a.Numer * b.Denom, a.Denom * b.Numer); } public static bool operator ==(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer == b.Numer; } public static bool operator !=(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer != b.Numer; } public override bool Equals(object another) { return another is Fraction && this == (Fraction)another; } public override int GetHashCode() { //return this.Numer.GetHashCode() ^ this.Denom.GetHashCode(); return (this.Numer.GetHashCode() + ":" + this.Denom.GetHashCode()).GetHashCode(); } public static bool operator <(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer < b.Numer; } public static bool operator >(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer > b.Numer; } public static bool operator <=(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer <= b.Numer; } public static bool operator >=(Fraction a, Fraction b) { Reduction(ref a, ref b); return a.Numer >= b.Numer; } public static void Reduction(ref Fraction a, ref Fraction b) // 通分 { BigInteger d = a.Denom * b.Denom; a.Numer *= b.Denom; b.Numer *= a.Denom; a.Denom = d; b.Denom = d; } public void Simplify() // 約分とか { if (this.Denom == 0) throw new Exception("Bad fraction"); if (this.Numer == 0) { this.Denom = 1; return; } if (this.Numer < 0) { this.Numer *= -1; this.Denom *= -1; } int sign = 1; if (this.Denom < 0) { sign = -1; this.Denom = BigInteger.Abs(this.Denom); } if (this.Numer == this.Denom) { this.Numer = sign; this.Denom = 1; return; } BigInteger d = GetGCD(this.Numer, this.Denom); this.Numer /= d; this.Denom /= d; this.Numer *= sign; } private static BigInteger GetGCD(BigInteger a, BigInteger b) { if (a < b) { BigInteger t = a; a = b; b = t; } while (b != 0) { BigInteger r = a % b; a = b; b = r; } return a; } } }
で、これを使って...
www.youtube.com
...この問題を解いてみる。
source:
public void Test01() { const int MURABITO_NUM = 100; List<Murabito_t> murabitoList = new List<Murabito_t>(); Fraction rem = 1; for (int n = 1; n <= MURABITO_NUM; n++) { Fraction area = rem * new Fraction(n, MURABITO_NUM); rem -= area; area.Simplify(); rem.Simplify(); murabitoList.Add(new Murabito_t() { No = n, Area = area, }); } murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。"); } private class Murabito_t { public int No; public Fraction Area; }
output:
最も広い土地を貰ったのは 10 番目の村人です。
それぞれの村人が貰った土地の面積を出力してみる。
source:
public void Test01() { const int MURABITO_NUM = 100; List<Murabito_t> murabitoList = new List<Murabito_t>(); Fraction rem = 1; for (int n = 1; n <= MURABITO_NUM; n++) { Fraction area = rem * new Fraction(n, MURABITO_NUM); rem -= area; area.Simplify(); rem.Simplify(); murabitoList.Add(new Murabito_t() { No = n, Area = area, }); } murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC //Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。"); foreach (Murabito_t x in murabitoList) Console.WriteLine(string.Join("\t", x.No, x.Area.Numer, x.Area.Denom)); } private class Murabito_t { public int No; public Fraction Area; }
output:
面積の広い順
各行：村人番号 \t 面積の分子 \t 面積の分母
10 245373636545037 3906250000000000 11 24291990017958663 390625000000000000 9 24267722295663 390625000000000 12 589632848617723911 9765625000000000000 8 117235373409 1953125000000 13 28105832450778173091 488281250000000000000 7 8824167891 156250000000 14 1316650150963377493263 24414062500000000000000 6 80463537 1562500000 15 24263981353467956661561 488281250000000000000000 5 1411641 31250000 16 137495894336318421082179 3051757812500000000000000 17 49086034278065676326337903 1220703125000000000000000000 4 470547 12500000 18 2156898094453827071516141973 61035156250000000000000000000 19 186691512842170143190119399663 6103515625000000000000000000000 3 14553 500000 20 795895396853462189389456388037 30517578125000000000000000000000 21 16713803333922705977178584148777 762939453125000000000000000000000 2 99 5000 22 691633099865658642579437601204153 38146972656250000000000000000000000 23 56399535507226891126705048025465931 3814697265625000000000000000000000000 24 566447508789974428272559395386201307 47683715820312500000000000000000000000 1 1 100 25 3587500889003171379059542837445941611 381469726562500000000000000000000000000 26 139912534671123683783322170660391722829 19073486328125000000000000000000000000000 27 10751740164342504623041449883825487008167 1907348632812500000000000000000000000000000 28 203486637925148883791636329282771254117531 47683715820312500000000000000000000000000000 29 7587144642637694095659583134686185332096513 2384185791015625000000000000000000000000000000 30 55726269271787201461223834747867499163329561 23841857910156250000000000000000000000000000000 31 4030866810659274239028524046762415772814171579 2384185791015625000000000000000000000000000000000 32 8971929352757739435257037394406667365296059321 7450580596923828125000000000000000000000000000000 33 5033252366897091823179197978262140391931089279081 5960464477539062500000000000000000000000000000000000 34 173723468057448108684882015067896300194227596632523 298023223876953125000000000000000000000000000000000000 35 2360595360074736065071043851804943843815680871888989 5960464477539062500000000000000000000000000000000000000 36 39455665304106302801901732951596918532347808858715959 149011611938476562500000000000000000000000000000000000000 37 162206624027992578185596013245453998410763214196943387 931322574615478515625000000000000000000000000000000000000 38 5247603485446138272652930482562390164802258578209222547 46566128730773925781250000000000000000000000000000000000000 39 333913295468651640612494365969364721539259506371313161017 4656612873077392578125000000000000000000000000000000000000000 40 522274641630455130188773239080288410612687945862823149283 11641532182693481445312500000000000000000000000000000000000000 41 64239780920545981013219108406875474505360617341127247361809 2328306436538696289062500000000000000000000000000000000000000000 42 1941294842940401718911670129661432022247361094772113645884911 116415321826934814453125000000000000000000000000000000000000000000 43 115275936626032425880135840556562177702021870722896462686594477 11641532182693481445312500000000000000000000000000000000000000000000 44 1680884006151682116903376093696848498120179370773397258244063653 291038304567337036132812500000000000000000000000000000000000000000000 45 9626881126141452124082972172991041398324663668974911569943273649 2910383045673370361328125000000000000000000000000000000000000000000000 46 270622324990420820821443551085192608197348878694516958577294248133 145519152283668518066406250000000000000000000000000000000000000000000000 47 14931292626645392244452689840309105208801553350580087844982017429599 14551915228366851806640625000000000000000000000000000000000000000000000000 48 50512245268864199295063354991683994217009510271111361007492356836303 90949470177292823791503906250000000000000000000000000000000000000000000000 49 10725433412088831650318452376567568105411686014232645653924210434908337 36379788070917129516601562500000000000000000000000000000000000000000000000000 50 11163206204418988044209001453162162721959101769915610782655810860822963 72759576141834259033203125000000000000000000000000000000000000000000000000000 51 569323516425368390254659074111270298819914190265696149915446353901971113 7275957614183425903320312500000000000000000000000000000000000000000000000000000 52 7110962352214895384161133925664297653887947827436244068551751518344227431 181898940354585647583007812500000000000000000000000000000000000000000000000000000 53 86972539538628335852432330321586409766783361889412523607671422416671704733 4547473508864641189575195312500000000000000000000000000000000000000000000000000000 54 2082417974990931286730879758077229320642416721465367782228962925410497986909 227373675443232059478759765625000000000000000000000000000000000000000000000000000000 55 19513027691581689464552317733094037708241904834471779589034356301068740395851 4547473508864641189575195312500000000000000000000000000000000000000000000000000000000 56 111756431324513312387890547016811306874476364051974737646287676997030058630783 56843418860808014869689941406250000000000000000000000000000000000000000000000000000000 57 10010183205781406695315338997077241344328097180084022929174624782448263823071563 11368683772161602973937988281250000000000000000000000000000000000000000000000000000000000 58 218994709782621300860670661918514385199598897957276782327732580766894473462635773 568434188608080148696899414062500000000000000000000000000000000000000000000000000000000000 59 9356360186919579026426584486794459422838035674795377010484850605868353538627783543 56843418860808014869689941406250000000000000000000000000000000000000000000000000000000000000 60 19505632254086580004245252404673195067950481152539514784570112280030635343240972471 284217094304040074348449707031250000000000000000000000000000000000000000000000000000000000000 61 396614522499760460086320132228354966381659783434970133952925616360622918645899773577 14210854715202003717422485351562500000000000000000000000000000000000000000000000000000000000000 62 7860769798396891741710836719083297612384043904473424458181755248852346043326111905813 710542735760100185871124267578125000000000000000000000000000000000000000000000000000000000000000 63 303527143505841271446060372669119588452377437214667389562695517189556716576172772621231 71054273576010018587112426757812500000000000000000000000000000000000000000000000000000000000000000 64 178261973170097254658797361726308329725999447253058625616186256127199976401879247412469 111022302462515654042363166809082031250000000000000000000000000000000000000000000000000000000000000 65 20856650860901378795079291321978074577941935328607859197093791966882397239019871947258873 35527136788005009293556213378906250000000000000000000000000000000000000000000000000000000000000000000 66 370606642220632192435639715028995017500352850839108882656051226488448750939506955370523051 1776356839400250464677810668945312500000000000000000000000000000000000000000000000000000000000000000000 67 12791544408766668702551322285394706816148542336537727798340677180919488706669649156576538033 177635683940025046467781066894531250000000000000000000000000000000000000000000000000000000000000000000000 68 107105319601762703613899877643379560057601973892502467087598804455161689021517510102081161739 4440892098500626161694526672363281250000000000000000000000000000000000000000000000000000000000000000000000 69 434721591324801561727005385729011155527913894034274719355548088670950384852041658649623538823 55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000 70 1367167903151912157895074908741962619558801666745472668118172974515887442215841158361859535139 555111512312578270211815834045410156250000000000000000000000000000000000000000000000000000000000000000000000 71 41600966195908184233092993651719719709432107859540811187024406224554860741710595247296582997801 55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000000 72 152927495452563888518834807649279533016363100723100728448075634149419981036429089571048002287691 693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000 73 8682883352917794114791620745420204596817949385500496915218516561150401145512807196756169907667789 138777878078144567552953958511352539062500000000000000000000000000000000000000000000000000000000000000000000000000 74 118824663966642141379134645543490197153714129261849266004154767734099325265305402596704297777535907 6938893903907228377647697925567626953125000000000000000000000000000000000000000000000000000000000000000000000000000 75 125247618775649824696925707464759937540401379492219496598973944368374964468835424358688313873618929 27755575615628913510590791702270507812500000000000000000000000000000000000000000000000000000000000000000000000000000 76 793234918912448889747196147276812937755875403450723478460168314333041441635957687605025987866253217 693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000000000 77 9644066645725036501663279474786515190610906220900901238120993716364872264100327675619000168268657533 34694469519536141888238489627838134765625000000000000000000000000000000000000000000000000000000000000000000000000000000 78 112347114041757892753142359595889663973740037404520888449279628098432343128545375649743417544636179313 1734723475976807094411924481391906738281250000000000000000000000000000000000000000000000000000000000000000000000000000000 79 2503324156468913046217454115098156871620002371910991078523692226090710414838613626657103329392021533923 173472347597680709441192448139190673828125000000000000000000000000000000000000000000000000000000000000000000000000000000000 80 665440598555027518614766283760269548152152529242162185430348566429176186222922609617711011610537369777 216840434497100886801490560173988342285156250000000000000000000000000000000000000000000000000000000000000000000000000000000 81 53900688482957229007796068984581833400324354868615137019858233880763271084056731379034591940453526951937 86736173798840354720596224069595336914062500000000000000000000000000000000000000000000000000000000000000000000000000000000000 82 518378226274366437000902935049249978010526820279644342450241533248328249067656712892196878044608611056283 4336808689942017736029811203479766845703125000000000000000000000000000000000000000000000000000000000000000000000000000000000000 83 9444598415291505571699377865409505696923500847534007897812937203329297611061940598304172387788356889244961 433680868994201773602981120347976684570312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 84 40623152219988764928875637324713175106044455452646274933966488934801918640350756549332404125788474812776519 10842021724855044340074528008699417114257812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 85 32885408939990904942423134977148760800131225842618413041782395804363457946950612444697660482781146277009563 54210108624275221700372640043497085571289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 86 249542220779930984563093200708952361365701654923398546022937003456640357362154647374470482486986345278484331 2710505431213761085018632002174854278564453125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 87 3534214243139022548812180447250046234225867624380225919255084537327766921710515819791919158943597308711557153 271050543121376108501863200217485427856445312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 88 5809110767458393384829216137433984040164357129728417315557207917676674365570158186554533789987751898227042217 3388131789017201356273290002718567848205566406250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 89 141002961355581003068127337154079430793080304876135220295797683092697459600657475982732774720611796075147297449 677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 90 156845990721376621390388835710717569084437642502667267520044613777270207870394271036972412329669301252130139859 6776263578034402712546580005437135696411132812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 91 1585887239516141394058376005519477642964869496415857927147117761525732101800653184929387724666656268215982525241 677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 92 3607457786591662291978943221346504088942065777561347152961026116877214781019068233850365483582393928798993216757 16940658945086006781366450013592839241027832031250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 93 14586677137088025789306161721096733924852700752748055879364149081286129331946667206438434346659245016448103006887 847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 94 51602330947332908437437926948826080228779984383377531014094677932721898389359715171163923656461200111950816013611 42351647362715016953416125033982098102569580078125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 95 62581550297829271934765145448576310064690619358564239740497800897130812940287314143751992519538051199599925803741 847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 96 9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117 2646977960169688559588507814623881131410598754882812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 97 319495283099444177772222058342731688224999477777933223938330878264299413431993130102312803915536366650589094892783 2117582368135750847670806251699104905128479003906250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 98 484183573356889630232130335838985135763659002405733854834377722730433131695907114691133836861689132965325741744733 105879118406787542383540312584955245256423950195312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 99 978248444129225987611855168327745478379637576289135747522518256128834286487649068457596935700147431909535682300583 10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100 9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117 10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
グラフにしてみる。
しゃらくせえのでエクセルで、、、
↑の source:
public void Test01() { const int MURABITO_NUM = 100; List<Murabito_t> murabitoList = new List<Murabito_t>(); Fraction rem = 1; for (int n = 1; n <= MURABITO_NUM; n++) { Fraction area = rem * new Fraction(n, MURABITO_NUM); rem -= area; area.Simplify(); rem.Simplify(); murabitoList.Add(new Murabito_t() { No = n, Area = area, }); } //murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC //Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。"); //foreach (Murabito_t x in murabitoList) //Console.WriteLine(string.Join("\t", x.No, x.Area.Numer, x.Area.Denom)); using (CsvFileWriter writer = new CsvFileWriter(SCommon.NextOutputPath() + ".csv")) { foreach (Murabito_t x in murabitoList) { const int GAISANCHI_SEIDO = 1000000000; double gaisanchi = (double)((x.Area.Numer * GAISANCHI_SEIDO) / x.Area.Denom) / GAISANCHI_SEIDO; writer.WriteCell(x.No.ToString()); // 村人番号 writer.WriteCell(gaisanchi.ToString("F9")); // 面積の概算値 writer.EndRow(); } } } private class Murabito_t { public int No; public Fraction Area; }
