[b][size=150][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][br]＜factorial＞[br][/size][/b][br]フィボナッチ数列の一般項は、意外なことに、[br]黄金比にかかわる無理数を使った式になる。[br]くわしい計算はしませんが、[br]漸化式から特性方程式を作り一般項を作ると無理数が残るんだ。[br][br]それに対してNの階乗fact(N)は１からNまでの積だから、一般項は単純だ。[br]だから、再帰関数でも表せるけど、forで十分かけるね。

[color=#0000ff]#再帰を使うならキャッシュを使おう。[br]#==================[br][/color][color=#ff00ff]from functools import cache[br]@cache[br][/color][color=#0000ff]def factorial(n):[br] return n * factorial(n-1) if n else 1[br][br]factorial(100)[br][br]#再帰なしなら、どんどんかけ算して上書きしよう。[br]#==================[br]def fact(n):[br] res=1[br] for i in range(1,n+1):[br] res *=i[br] return res[br]fact(100)[br]#==================[br][br][/color][OUT][br]93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000[br][br][br][br]

geogbraでは[br]fibを再帰を使わずに素早く求めることができた。そのときの手段がIterationListだった。[br]同じようにIterationListやIterationでfactも再帰を使わず求めることができる。[br][br]geogebraにはProductというコマンドがあったね。[br]1から100までの数列をlst=Sequence(100)で作っておき、[br]それの積をProduct(lst)するとfactorial(100)が計算できる。[br][br]でも、有効数字には課題が残った。

pythonにはmathパッケージの関数一覧をリスト表示すると、factorialという関数がすでにありました。[br][b][color=#0000ff][IN][br]#===========[br][/color][/b][b][color=#0000ff]import math[br]print(dir(math))[br]#============[br][/color][/b][OUT][br]['__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'cbrt', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'exp2', 'expm1', 'fabs', '[b]factorial[/b]', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'lcm', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'nextafter', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'sumprod', 'tan', 'tanh', 'tau', 'trunc', 'ulp'][br][br][IN][br]#===========[br]from math import factorial as fact[br]fact(100)[br]#============[br]factorial関数だけを factという別名をつけて、簡単に使えます。[br]パッケージがあるときは、何でも自力で作るのではなく、それに乗っかるというときもあってよいでしょう。[br][br]算数、数学と同じようにコード開発でも、[br]知識・技術に乗っかって秒殺する快感とかエレガントさというのもあるでしょう。[br]しかし、それで終わってしまうと、思考が深まりません。[br]フィボナッチ数列よりも扱いやすいということで、階乗計算を使って、[br]くり返し（反復iteration）と自分を呼び出す（再帰recurrsion）の関係をさぐってみましょう。[br]#[IN]C++[br]#=====================[br]int factorial(int n) {[br] int result = 1;[br] for (int i = 1; i <= n; ++i) {[br] result *= i; [br] } [br] return result;[br]}[br]C++でforで反復するとこんな風になるでしょう。[br]これはPythonでもjuliaでも同じようなものです。[br][b][size=150][br]＜productの中身＞[/size][/b][br]haskellでは[br]#=================[br]fact n = product [1..n][br]#=================[br]のように、product関数に１からｎのリストをわたすだけで終了です。[br]ではproduct関数ってどうなっているんでしょう。[br]リストが空なら１を返し、先頭に残りのproductをかければいいですね。[br]だから、再帰関数を使うと、[br][b]product [] =1[br]product (n: ns) = n * product ns[br][/b]と定義できます。[br]数であれば何でもproductできるという一般化をしましょう。[br][br]ghciに尋ねると[br][b]ghci>:info product[br][/b]type Foldable :: (* -> *) -> Constraint[br]class Foldable t where[br] ...[br] product :: Num a => t a -> a[br] -- Defined in ‘Data.Foldable’[br][br][b]ghci> :t product[br]product :: (Foldable t, Num a) => t a -> a[br][/b]と答えてきます。[br]tが畳み込みのできるクラス、aが数のクラスで、数リストt aから数aを返す。[br]だから、次のようにも定義できるのです。[br][b]product = foldl (*) 1[br][/b][br][b][size=150]＜foldlを使おう＞[br][/size][/b]haskellでは、foldlの中はどうなっているのでしょうか？[br]ghci> :t foldl[br]foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b[br]tが畳み込みのできるクラス、（）内は２項演算と数リストt aがあれば、[br]数aのうち演算やリストの左側をbとして、畳み込みを続ける。[br]という型の説明です。これを再帰でかくと次のようになります。[br]foldl f v [ ] = v [br]foldl f v (x: xs) = foldl f (f v x ) xs[br]vを初期値として、演算をｆとする。[br]リストが[ ]になったらｖを返す。（ベースケース）[br]リストの左をｘ、残りをxsとしたら、左ｘにｆをしたものをｖとして[br]残りxsをリストとする。 （再帰ケース）[br][br]foldlを使うと、２項演算をリストにくり返し適用するものなら、[br]簡単に関数定義できますね。[br]（例）[br]関数そのものの定義だから、引数としてのリストは省けます。[br]sum = foldl (+) 0[br]product = foldl (*) 1[br]or = foldl (∨) False[br]and = foldl (∧) True[br]legth = foldl (\n _ -> n+1) 0 [br][br][br][color=#9900ff][u][b][size=150]質問：ほかの言語でのfoldlの活用はどうでしょうか。[br][/size][/b][/u][/color][br]haskellとはちがって、引数はかっこで閉じる必要があるので、見かけは代わります。[br][color=#0000ff]#[IN] julia[br]#=======================[br]function sum(lst)[br] return foldl(+,lst)[br]end[br]function product(lst)[br] return foldl(*,lst)[br]end[br]lst=[1,2,3,4,5][br]println("lst=$lst, sum(lst)=$(sum(lst)),product(lst)=$(product(lst))")[br]#=====================================================[br][/color][OUT][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][/b][br]ちゃんと動きました。[br]次のように[b][color=#0000ff]juliaで数学の関数定義風にかいても動きました。[br][/color][/b]#[IN] julia[br]#=======================[br][b]Sum(lst) = foldl(+,lst)[br]Product(lst)= foldl(*,lst)[br][/b]lst=[1,2,3,4,5][br]println("lst=$lst, Sum(lst)=$(Sum(lst)),Product(lst)=$(Product(lst))")[br][color=#0000ff]#=====================================================[br][/color][OUT][br][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][/b][br]pythonにはfoldlという名前の関数はないが、実態がfoldlと同じreduce関数がある。[br]ただし、パッケージfunctoolsにあるからインポートする。別名foldlをつけてみた。[br][br]残念ながら、reduceの引数は（演算、リスト）ではなく（関数、リスト）だ。[br]だから、+,*のまま渡すのではなく、関数にして渡す。[br]わざわざそのために、関数を外に作るのも手間だから、中にラムダをつかった無名関数[br]にしている。[br]pythonは、ラムダ式の発想を忠実に再現しているが、[br]関数の関数を作ったりしようとすると、[color=#ff0000]簡単な内容なのに難解に見えてしまうのが難点だ。[br][/color][br]#[IN] python[br]#=======================[br][b]from functools import reduce as foldl[br]Sum =lambda lst: foldl(lambda x,y:x+y,lst)[br]Product = lambda lst: foldl(lambda x,y:x*y,lst)[br][/b]lst=[1,2,3,4,5][br]print(f"lst={lst}, Sum(lst)={Sum(lst)},Product(lst)={Product(lst)}")[br]lst=[1, 2, 3, 4, 5], Sum(lst)=15,Product(lst)=120[br][color=#0000ff]#=====================================================[br][/color][[OUT][br][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][br][/b]geogebraの数式、数式処理(CAS)には、関数を自作する機能はあるが、fold,reduceはない。[br]Iteration,IterationListはあくまでも初期値に対する反復計算なので、初期値以外を途中から渡すことはできない。漸化式の発想でしょうね。[br]しかし、sumも、productもすでにあるので、それを使えばよいでしょう。というところか。[br]また、[b]数式処理(CAS)を使うと、nPr,nCrがある[/b]ので、わざわざfactorialを作るところからやらなくても、[br]すぐに順列、組み合わせがすぐに使えるという実用性を重視している感があるね。[br]

[b][color=#9900ff][u][size=150]質問：rustでfactorialを計算するにはどうしますか。[br][/size][/u][/color][/b][br]もちろんC++のように反復計算できます。[br]多桁整数に対応できるように、[br]Cargo.tomlの[dependencies]に[br]num-bigint = "0.4"[br]を記入しておきます。[br]（今後0.5以上のバージョンになるかも）[br]１を多桁整数として扱うために、use std::str::FromStr;[br]も宣言しておきましょう。[br]階乗計算を順次表示するためにはfact関数の中にprintln!()をかきます。[br]最後の結果だけ表示するにはmain関数の中でprintln!()をかけばいいね。[br]ただ、rustの場合は変数を盗んではいけないので、&をつけて借用して[br]表示します。[br]基本型のデータは所有権は気にならないですが、構造体とかBigIntなど[br]メモリーを定型スタックするのではなく、ヒープメモリーの領域を[br]使う場合は、所有権を意識して代入や表示でも借用、参照にしましょう。[br]ansのように、入れ物として使ったけど、あと使わない変数は前に‗をつけます。[br]また、数の変換操作などのあとの[b].unwrap()[/b]は成功したらラップをはがす定型句です。[br]これで、その結果をエラーなしに代入できます。[br]また、for文のi は多桁整数ではないから、これを変換してからかけましょう。[br][br][color=#0000ff][IN]rust[br][b]use num_bigint::{BigInt, ToBigInt};[br]use std::str::FromStr;[br][br]fn main() {[br] let idx = 100;[br] let _ans = fact(idx);[br]}[br]fn fact(num:i64) -> BigInt {[br] let mut result = BigInt::from_str("1").unwrap();[br][br] for i in 1..=num {[br] result = result * i.to_bigint().unwrap();[br] println!("{}番目：{}",&i, &result);[br][br] } [br] result[br]}[br][/b][/color][OUT][br]1番目：1[br]2番目：2[br]3番目：6[br]4番目：24[br]5番目：120[br]6番目：720[br]7番目：5040[br]8番目：40320[br]9番目：362880[br]10番目：3628800[br]11番目：39916800[br]12番目：479001600[br]13番目：6227020800[br]14番目：87178291200[br]15番目：1307674368000[br]16番目：20922789888000[br]17番目：355687428096000[br]18番目：6402373705728000[br]19番目：121645100408832000[br]20番目：2432902008176640000[br]21番目：51090942171709440000[br]22番目：1124000727777607680000[br]23番目：25852016738884976640000[br]24番目：620448401733239439360000[br]25番目：15511210043330985984000000[br]26番目：403291461126605635584000000[br]27番目：10888869450418352160768000000[br]28番目：304888344611713860501504000000[br]29番目：8841761993739701954543616000000[br]30番目：265252859812191058636308480000000[br]31番目：8222838654177922817725562880000000[br]32番目：263130836933693530167218012160000000[br]33番目：8683317618811886495518194401280000000[br]34番目：295232799039604140847618609643520000000[br]35番目：10333147966386144929666651337523200000000[br]36番目：371993326789901217467999448150835200000000[br]37番目：13763753091226345046315979581580902400000000[br]38番目：523022617466601111760007224100074291200000000[br]39番目：20397882081197443358640281739902897356800000000[br]40番目：815915283247897734345611269596115894272000000000[br]41番目：33452526613163807108170062053440751665152000000000[br]42番目：1405006117752879898543142606244511569936384000000000[br]43番目：60415263063373835637355132068513997507264512000000000[br]44番目：2658271574788448768043625811014615890319638528000000000[br]45番目：119622220865480194561963161495657715064383733760000000000[br]46番目：5502622159812088949850305428800254892961651752960000000000[br]47番目：258623241511168180642964355153611979969197632389120000000000[br]48番目：12413915592536072670862289047373375038521486354677760000000000[br]49番目：608281864034267560872252163321295376887552831379210240000000000[br]50番目：30414093201713378043612608166064768844377641568960512000000000000[br]51番目：1551118753287382280224243016469303211063259720016986112000000000000[br]52番目：80658175170943878571660636856403766975289505440883277824000000000000[br]53番目：4274883284060025564298013753389399649690343788366813724672000000000000[br]54番目：230843697339241380472092742683027581083278564571807941132288000000000000[br]55番目：12696403353658275925965100847566516959580321051449436762275840000000000000[br]56番目：710998587804863451854045647463724949736497978881168458687447040000000000000[br]57番目：40526919504877216755680601905432322134980384796226602145184481280000000000000[br]58番目：2350561331282878571829474910515074683828862318181142924420699914240000000000000[br]59番目：138683118545689835737939019720389406345902876772687432540821294940160000000000000[br]60番目：8320987112741390144276341183223364380754172606361245952449277696409600000000000000[br]61番目：507580213877224798800856812176625227226004528988036003099405939480985600000000000000[br]62番目：31469973260387937525653122354950764088012280797258232192163168247821107200000000000000[br]63番目：1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000[br]64番目：126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000[br]65番目：8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000[br]66番目：544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000[br]67番目：36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000[br]68番目：2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000[br]69番目：171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000[br]70番目：11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000[br]71番目：850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000[br]72番目：61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000[br]73番目：4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000[br]74番目：330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000[br]75番目：24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000[br]76番目：1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000[br]77番目：145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000[br]78番目：11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000[br]79番目：894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000[br]80番目：71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000[br]81番目：5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000[br]82番目：475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000[br]83番目：39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000[br]84番目：3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000[br]85番目：281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000[br]86番目：24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000[br]87番目：2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000[br]88番目：185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000[br]89番目：16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000[br]90番目：1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000[br]91番目：135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000[br]92番目：12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000[br]93番目：1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000[br]94番目：108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000[br]95番目：10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000[br]96番目：991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000[br]97番目：96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000[br]98番目：9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000[br]99番目：933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000[br]100番目：93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[b][color=#9900ff][u][size=150]質問：rustでfactorialを計算するのにfoldなど使ってできますか。[br][/size][/u][/color][/b][br]もちろんhaskellのようにできます。[br]rustのイテレータクレートには[b]map, filterの他にfold,rfold,reduce[/b]などが[br]あります。これに乗っかる手もありますね。[br][br]多桁整数に対応できるように、[br]Cargo.tomlの[depetndencies]に[br]num-bigint = "0.4"[br]を記入しておきます。[br][br][b]対象から要素へという順番で、詳細化[/b]していきましょう。[br]階乗計算の基点になる１を多桁にしておきます。[br][b]let one = BigInt::from_str("1").unwrap();[br][/b]n!のnを100くらいにすると、[br]let n = 100;[br][br]ここからが本番です。[br]レンジ(1..=n)の要素を多桁整数リストに変換しましょう。[br][b](1..=n).map(|x| x.to_bigint().unwrap())[/b][br]そのリストから取り出した要素xと累積(accumlator)をaccumとして、[br]対象.Iter().fold(|対象たち|対象たちへの操作）という順に描きます。[br][b].fold(one, |accum, x| accum * x);[br][/b]その結果をresultに入れて表示します。[br][br][b][color=#0000ff]use num_bigint::{BigInt, ToBigInt};[br]use std::str::FromStr;[br][br]fn main() {[br] let n = 100;[br] let one = BigInt::from_str("1").unwrap();[br] [br] let result = (1..=n)[br] .map(|x| x.to_bigint().unwrap())[br] .fold(one, |accum, x| accum * x);[br] println!("{}", result);[br]}[br][/color][br][/b]

[u][b][color=#9900ff][size=150]質問：もっと手軽にrustでイテレーション関数を使えませんか。[/size][/color][/b][br][/u][br]使えます。多桁整数でないのなら、範囲のあとに.sum(), .product()をつけるだけで、[br]たし算やかけ算を繰り返した結果を返します。[br]だから、次のようにして計算ができますよ。[br][IN]rust[br]fn main() {[br]    let n:i64 = 20;[br][color=#0000ff][b]    let sum20:i64 = (1..n).sum();[br]    let fact20:i64 = (1..n).product();[br][/b][/color]    println!("1から20までの和＝{}", sum20);[br]    println!("1から20までの和＝{}", fact20);[br]}[br][OUT][br]1から20までの和＝190[br]1から20までの和＝121645100408832000[br]