はじめに
この記事は以下の記事の続きです。
Project EulerでF#の勉強をしました(Problem1~3編)
手元でしか動かしていないので、間違いがあったら指摘を頂けると喜びます。
Problem 4
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
let collect pred xs =
let rec inCollect xs =
match xs with
| [] -> []
| y::ys -> pred y @ inCollect ys
inCollect xs
let ketaCount n = n |> abs |> float |> (+) 1.0 |> log10 |> Math.Ceiling |> int
let listReverse ns =
let rec inListReverse reverse = function
| [] -> reverse
| n::ns -> inListReverse (n::reverse) ns
inListReverse [] ns
let checkPalindromic n =
let rec numToList num ketasu nlist =
match (ketasu - 1) with
| k when k < 0 -> nlist
| k -> numToList (num % (pown 10 k)) k nlist@[num / (pown 10 k)]
let numL = (numToList n (ketaCount n) [])
numL = listReverse numL
let Problem4 = collect (fun x -> [for i in 1..999 -> x*i]) [1..999]
|> filter checkPalindromic
|> List.max //906609
//filter,maxの中身は前回参照(といっても名前の通りです)
実はウソがあります。(!?)
作業時にはリスト生成を[900..999]として横着をしていたんですが、
今回投稿用に[1..999]としたところ、最終的な値が変化し、"Problem4 = 90909"となりました・・・。
([900..999]の時の回答は906609)
少し試行錯誤したもののロジック側に変なことは無いような気がするので、
「要素数が多すぎると切り取られる部分がある・・・?」くらいに思っています。
また調べようと思います。今回は投稿を優先してしまいました。すみません。
自作max関数が原因だったようです。List.maxを使用して解決しました。自作関数のほうはまた見直しておきます。
ともかくロジック側ですが、
① 値xに対してリストxsの各要素の値を用いた処理をするcollect関数(とfor文)を用いて
[1..999]と[1..999]を相互にかけ合わせたリスト(要素数1000000個ということ)を作り、
② filterとcheckPalindromicで回文数だけを抽出し、
②-1 10底のlogを用いて、対象の値のケタを数える(ketaCount)
②-2 対象の値を1ケタずつリスト化する(checkPalindromic内、numToList)
②-3 そのリストと、そのリストの並びを反転したもの(listReverse)を比較して成否を返す
③ maxで最大値を抽出しています。
回文判定の実装方法で各人の個性が出る問題だと思いますが、自分の方法がスマートなのかは不明です・・・。
Problem 5
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
//この辺りからfunctionキーワードに抵抗が無くなってきて、多用しているようです(余談)
let rec euclideanAlgorithm a = function
| 0 -> a
| b -> euclideanAlgorithm b (a % b)
let lcm a b =
(a / (euclideanAlgorithm a b)) * b
let allNumLcm xs =
let rec inAllNumLcm n = function
| [] -> n
| y::ys -> inAllNumLcm (lcm n y) ys
inAllNumLcm 1 xs
let Problem5 = allNumLcm [1..20] //232792560
数学らしさがあって嬉しい問題でした。コードも短めです。(Problem4比)
ユークリッドの互除法(euclideanAlgorithm)を使用しました。最大公約数がわかるやつです。関数名は"gcd"でもよかったですね。
それを用いて最小公倍数lcmを求める関数を用意して、
あとは1から順に先頭の値との最小公倍数を求め続けます。
1と1なら1、1と2なら2、2と3なら6、6と4なら12で、無駄は出ません。
おわり
今回は2問になりましたがここまでにしておきます。
Problem10まで続きます。(投稿したらリンクを貼りに来ます。→来ました)
(Problem6~7編)
(Problem8~10編)
ご指導してくださる方がいらっしゃれば、よろしくお願い致します。