%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv%3E%0A%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv
ID: 3553481 • Letter: #
Question
%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv%3E%0A%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv%3E%0A%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv%3E%0A%3Cdiv%20class%3D%22c1%22%3E%3C%2Fdiv%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EWrite%20a%20C%20program%20(care%20should%20be%20taken%20to%20not%0Ause%20the%20extensions%20of%20C%2B%2B%20)%20that%20calculates%20the%20first%2099%20Catalan%0Anumbers%20%3Cb%3Ewith%20all%20significant%20digits%3C%2Fb%3E.%20We%20will%20use%20the%0Arecursion%20formula%20defined%20as%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EC(1)%3D1%20%3Cspan%20class%3D%22finalized_jax%22%3E%5C(C(n)%20%3D%0A%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D%20C(i)C(n-1)%5C)%3C%2Fspan%3E%20n%26gt%3B0%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EOf%20course%2C%20we%20will%20not%20calculate%20this%20formula%0Awith%20a%20recursive%20function%20because%20we%20know%20that%20this%20is%20not%20very%0Aeffective.%20Rather%20we%20will%20store%20each%20Catalan%20number%20in%20a%20table%20and%0Ause%20this%20table%20for%20us%20to%20program%20the%20formula%20iteratively%2C%20while%0Aavoiding%20unnecessary%20calculations.%20For%20example%2C%20with%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EC(5)%20%3D%20C(1)C(4)%20%2B%20C(2)C(3)%20%2B%20C(3)C(2)%20%2B%0AC(4)C(1)%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eit%20is%20clear%20that%20C(1)C(4)%20%3D%20C(4)C(1)%20and%0AC(2)C(3)%20%3D%20C(3)C(2)%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EThe%20Catalan%20numbers%20are%20numbers%20that%20grow%20very%0Aquickly%20.%20For%20example%20%2C%20the%2015th%20number%20C%20(%2015%20)%20%3D%202674440%20and%20the%0A35th%20number%20has%2019%20significant%20digits%20%2C%20which%20exceeds%20the%20precision%0Aof%20a%20real%20long%2C%20precision%20limited%20to%2015%20significant%20digits.We%20must%0Afind%20a%20method%20that%20allow%20to%20represent%20an%20integer%20whatever%20its%0Anumber%20of%20digits.%20To%20do%20this%2Cwe%20will%20use%20arrays%20of%20integers%20.%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EA%20number%20%3Ci%3Eu%3C%2Fi%3E%20of%20%3Ci%3Em%3C%2Fi%3E%20digits%20will%20be%0Arepresented%20by%20u%3Csub%3Em%20%20%20%26nbsp%3B%3C%2Fsub%3Eu%3Csub%3E2%3C%2Fsub%3E%0Au%3Csub%3E1%3C%2Fsub%3E%20where%20each%20u%3Csub%3Ei%3C%2Fsub%3E%20occupies%20the%20(%20i-%201%20)%20th%0Aelement%20of%20the%20array%20.%20Similarly%20%2C%20a%20number%20%3Ci%3Ev%3C%2Fi%3E%20of%20%3Ci%3En%3C%2Fi%3E%0Adigits%20will%20be%20represented%20by%20v%3Csub%3En%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%26nbsp%3B%3C%2Fsub%3Ev%3Csub%3E2%3C%2Fsub%3E%20v%3Csub%3E1%3C%2Fsub%3E%20where%20each%0Av%3Csub%3Ei%3C%2Fsub%3E%20%26nbsp%3Boccupies%20the%20(%20i-%201%20)%20th%20element%20of%20the%20array%0A.%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3BHere%20is%20an%20algorithm%20to%20add%20these%20two%0Anumbers%20%3Ci%3Eu%3C%2Fi%3E%20and%20%3Ci%3Ev%3C%2Fi%3E%20and%20obtain%20a%20number%20%3Ci%3Ew%3C%2Fi%3E%20of%0A%3Ci%3Ep%3C%2Fi%3E%20digits%20represented%20by%20w%3Csub%3Ep%3C%2Fsub%3E%20w%3Csub%3Ep-1%20%26nbsp%3B%0A%26nbsp%3B%3C%2Fsub%3E%26nbsp%3Bw%3Csub%3E2%3C%2Fsub%3E%20w%3Csub%3E1%3C%2Fsub%3E%20.%20In%20this%20algorithm%20%2C%0Ar%20represents%20the%20retainer%20%2C%20m%20represents%20the%20minimum%20between%0A%3Ci%3Em%3C%2Fi%3E%20and%20%3Ci%3En%3C%2Fi%3E%20%2C%20n'%20represents%20the%20maximum%20between%20%3Ci%3Em%3C%2Fi%3E%0Aand%20%3Ci%3En%3C%2Fi%3E%2C%20and%20finally%20%2C%20u'%20is%20u%20if%20n'%20is%20m%20or%20v%20if%20n'%20is%20n.%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Er%20%26nbsp%3B%26lt%3B--%200%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Efor%20i%20from%201%20to%20m'%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Et%0A%26lt%3B--%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Eu%3Csub%3Ei%3C%2Fsub%3E%20%2B%0Av%3Csub%3Ei%3C%2Fsub%3E%20%2B%20r%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Ew%3Csub%3Ei%0A%26nbsp%3B%3C%2Fsub%3E%3C%2Fspan%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3E%26lt%3B--%0A%3Ci%3Et%3C%2Fi%3Emod10%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Er%3C%2Fspan%3E%0A%26lt%3B--%20floor(t%2F10)%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%0A%22FR-CA%22%3Eendfor%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Efor%20i%20from%20m'%2B1%20to%20n'%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Et%0A%26lt%3B--%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Eu'i%26nbsp%3B%2B%0Ar%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Ew%3Csub%3Ei%0A%26nbsp%3B%3C%2Fsub%3E%3C%2Fspan%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3E%26lt%3B--%0A%3Ci%3Et%3C%2Fi%3Emod10%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Er%3C%2Fspan%3E%0A%26lt%3B--%20floor(t%2F10)%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%0A%22FR-CA%22%3Eendfor%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eif%20r%26gt%3B0%20w%3Csub%3En'%2B1%3C%2Fsub%3E%26lt%3B--%26nbsp%3Br%20%26nbsp%3B%0A%26nbsp%3B%20p%26lt%3B--%20n'%2B1%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eotherwise%20p%26lt%3B--%20n%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EThis%20algorithm%20should%20be%20encoded%20in%20a%0A%3Cspan%20class%3D%22c2%22%3Efunction%3C%2Fspan%3E.%20Here%20is%20another%20algorithm%20that%0Aallows%20to%20multiply%20a%20number%20%3Ci%3Eu%3C%2Fi%3E%20of%20%3Ci%3Em%3C%2Fi%3E%20digits%20and%20a%0Anumber%20%3Ci%3Ev%3C%2Fi%3E%20of%20%3Ci%3En%3C%2Fi%3E%20digits%20in%20order%20to%20obtain%20a%20number%0A%3Ci%3Ew%3C%2Fi%3E%20of%20at%20most%20m%20%2B%20n%20counts%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Efor%20i%20from%201%20to%20n%3A%20w%3Csub%3Ei%3C%2Fsub%3E%20%26lt%3B--%200%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Efor%20i%20from%201%20to%20m%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eif%20u%3Csub%3Ej%3C%2Fsub%3E%20%3D%200%20then%20w%3Csub%3En%2Bj%0A%26nbsp%3B%26nbsp%3B%3C%2Fsub%3E%26lt%3B--%200%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eotherwise%20%26nbsp%3Br%20%3Csub%3E%26nbsp%3B%3C%2Fsub%3E%26lt%3B--%0A0%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Efor%20i%20from%201%20to%20n%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Et%0A%26lt%3B--%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Eu%3Csub%3Ej%3C%2Fsub%3E%20x%0A%26nbsp%3Bv%3Csub%3Ei%3C%2Fsub%3E%20%2B%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%0A%22FR-CA%22%3Ew%3Csub%3Ei%2Bj%20%26nbsp%3B%26nbsp%3B%3C%2Fsub%3E%2B%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%0Axml%3Alang%3D%22FR-CA%22%3Er%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Ew%3Csub%3Ei%0A%2Bj%3C%2Fsub%3E%3C%2Fspan%3E%20%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3E%26lt%3B--%0A%3Ci%3Et%3C%2Fi%3Emod10%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Er%3C%2Fspan%3E%0A%26lt%3B--%20floor(t%2F10)%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eendfor%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eif%26nbsp%3B%20w%3Csub%3En%2Bj%3C%2Fsub%3E%20%26lt%3B--%200%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eendif%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eendfor%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eif%20w%3Csub%3Em%2Bn%3C%2Fsub%3E%20%3D%200%20then%20p%20%26lt%3B--%20m%2Bn-1%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eotherwise%20p%20%26lt%3B--%20m%2Bn%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3EThis%20algorithm%20will%20also%20be%20encoded%20in%20a%0Afunction.%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3ENote%3A%20The%20pseudo-code%20can%20express%20succinctly%0Athe%20description%20of%20an%20algorithm%3A%20it%20does%20not%20depend%20on%20the%0Aprogramming%20language%20used.%20It%20is%20therefore%20necessary%20to%20adapt%0Aduring%20translation%20in%20the%20chosen%20programming%20language.%20In%20this%0Aalgorithm%2C%20the%20indices%20used%20follow%20the%20usual%20mathematical%0Aconvention%2C%20%26nbsp%3Bthat%20is%20to%20say%20that%20the%20figures%20numbers%20are%0Anumbered%20from%201%20to%20n.%20In%20C%2C%20the%20array%20elements%20are%20numbered%20from%200%0Ato%20n-1%2C%20so%20you%20have%20to%20make%20sure%20to%20modify%20the%20terminals%20of%20the%0Aloops%20and%20change%20some%20indices%20used%20outside%20the%20loops.%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3ENote%3A%20Replace%20the%20symbols%20used%20in%20the%0Aalgorithms%20with%20more%20meaningful%20names.%20For%20example%2C%20the%20variable%0A%3Ci%3Er%3C%2Fi%3E%20could%20be%20called%20%3Ci%3Eretainer%3C%2Fi%3E%2C%20the%20table%20%3Ci%3Eu%3C%2Fi%3E%20could%0Abe%20called%20%3Ci%3Eoperand1%3C%2Fi%3E%2C%20etc..%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c1%22%3EThe%20outputs%20of%20the%20program%0Awill%20be%20sent%20in%20catalan.txt%20file.%20These%20are%20expected%20by%20your%0Aprogram%20outputs%3A%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%201%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B1%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%202%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B1%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%203%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B2%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%204%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B5%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%205%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B14%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%206%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B42%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%207%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A132%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%208%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A429%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B%209%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B1%0A430%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B10%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B4%0A862%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B11%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B16%20796%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B12%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B58%20786%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3E...%20%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B75%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B311%20496%20878%20311%20103%20321%20137%20536%20291%20518%0A809%20134%20027%20240%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B76%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%201%20221%20395%20654%20430%20378%20811%20828%20760%20722%20007%20962%20130%20791%0A020%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B77%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%204%20790%20408%20930%20363%20303%20911%20328%20386%20208%20394%20864%20461%20024%0A520%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B78%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%2018%20793%20142%20726%20809%20884%20575%20211%20361%20279%20087%20545%20193%20250%0A040%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B79%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%2073%20745%20243%20611%20532%20458%20459%20690%20151%20854%20647%20329%20239%20335%0A600%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3ECatalan%5B80%5D%20%3D%20%26nbsp%3B%20%26nbsp%3B%0A%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20289%0A450%20081%20175%20264%20899%20454%20283%20846%20029%20490%20767%20264%20392%0A230%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20class%3D%22c2%22%3E...%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3ETo%20print%20a%20line%20results%20%2C%20you%20must%20write%20a%0Afunction%20that%20will%20do%20the%20job.%20Here%20is%20the%20header%20for%20this%0Afunction%3A%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3Cspan%20lang%3D%22FR-CA%22%20xml%3Alang%3D%22FR-CA%22%3Evoid%0A%26nbsp%3BPrintNumber%20(FILE%20*%20%26nbsp%3Bfich%2C%20%26nbsp%3Bint%20res%20%5B%20%5D%20%2C%20%26nbsp%3Bint%0An%2C%20%26nbsp%3Bint%20noCat%20)%26nbsp%3B%3C%2Fspan%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3ENumbers%20are%20right%20justified%20in%20a%20field%20of%20size%0A75%20.%20In%20addition%20%2C%20leave%20a%20space%20between%20each%20group%20of%203%20digits%20as%0Ashown%20above.%20To%20determine%20the%20number%20of%20spaces%20to%20print%20before%20the%0Astart%20of%20printing%20numbers%2C%20you%20can%20use%20the%20following%20formula%0A%3A%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E75%20-%20n%20-%20(%20n-%201%20)%20%2F%203%20.%20Do%20not%20forget%20to%20print%0Ain%20reverse%20order%20as%20the%20number%20at%20the%20position%200%20in%20the%20array%0A%3Ci%3Eres%3C%2Fi%3E%20is%20the%20last%20digit%20of%20the%20number%20(which%20represents%20the%0Aunits).%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3BNote%3A%20For%20output%20%2C%20we%20suggest%20the%0Aconversion%20specification%20%252d%20for%20the%20number%20of%20Catalan%20(%0A%3Ci%3EnoCat%3C%2Fi%3E%20)%20.%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3BNote%3A%20In%20the%20development%20phase%20of%20the%0Aprogram%2C%20we%20suggest%20you%20print%20to%20%3Ci%3Estdout%3C%2Fi%3E%20%2C%20thus%20it%20will%0Afacilitate%20debugging%20your%20program%20(otherwise%20you%20will%20spend%20your%0Atime%20opening%20the%20file%20catalan.txt%20to%20check%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3Eresults).%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E%26nbsp%3BThe%20role%20of%20the%20%3Ci%3Emain%3C%2Fi%3E%20function%20is%0Aa%20conductor%20%3A%20it%20takes%20care%20of%20opening%20and%20closing%20the%20files%0Arequired%20%2C%20it%20calls%20various%20functions%20necessary%20to%20carry%20out%20the%0Atask%20of%20the%20program.%20In%20addition%2C%20it%20reports%20data%20needed%20to%20solve%0Athe%20problem.%20Here%2C%20we%20have%20a%26nbsp%3B%3C%2Fp%3E%0A%3Cp%20class%3D%22MsoNormal%22%3E2-dimensional%20array%20for%20Catalan%20numbers%20%3A%20the%0Afirst%20dimension%20reserved%20for%20the%20number%20of%20Catalan%20number%20and%0A%26nbsp%3Blimited%20to%2099%20and%20the%20second%20dimension%20reserved%20for%20storing%0Athe%20digits%20of%20a%20Catalan%20number%20and%20limited%20to%2075%20.%20This%20table%0Ashould%20be%20initialized%20to%200%20.%20There%20should%20also%20be%20a%201-dimensional%0Aarray%20of%20capacity%2099%20to%20store%20the%20number%20of%20digits%20for%20each%20number%0Aof%20Catalan%20and%20another%20array%20with%201%20dimension%20of%20capacity%2075%0Astoring%20intermediate%20results.%20You%20can%20write%20other%20functions%20as%20you%0Asee%20fit.%3C%2Fp%3E%0AExplanation / Answer
#include typedef unsigned long long ull; ull binomial(ull m, ull n) { ull r = 1, d = m - n; if (d > n) { n = d; d = m - n; } while (m > n) { r *= m--; while (d > 1 && ! (r%d) ) r /= d--; } return r; } ull catalanMethod1(int n) { return binomial(2 * n, n) / (1 + n); } ull catalanMethod2(int n) { int i; ull r = !n; for (i = 0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.