Archive for the ‘while’ Tag

projecteuler14...または、再帰か繰り返しか

 projecteuler問題14 は、コラッツの問題から、百万以下で最も長い数列をもたらす数値を求めるもの。
 数値を与えて、コラッツの数列を求める関数は、再帰を使うと簡単に定義できます。

(define (collatz n lst)
  (push n lst -1)
  (if (even? n) (collatz (/ n 2) lst)
      (and (odd? n) (> n 1)) (collatz (++ (* 3 n)) lst)
      lst))

 newLISP の ifcond 的な記述ができるので、楽です(笑)。

> (collatz 13)
(13 40 20 10 5 16 8 4 2 1)
> 

 再帰を使うと見通しはいいですが、難点は速度。
 そこで、newLISP には豊富にある繰り返し関数から while を使って、再度定義してみます。

(define (Collatz n)
  (let (lst (list n))
    (while (> n 1)
      (if (even? n) (setq n (/ n 2)) (setq n (++ (* n 3))))
      (push n lst -1))
    lst))

 この程度なら、再帰と比べて見通しも悪くありませんし、早さは 5 ~ 6 倍違います。

> (Collatz 13)
(13 40 20 10 5 16 8 4 2 1)
> 

 これで、コラッツの数列を求める関数はできました。
 後は、百万回繰り返して、最長のリストを求めるだけ。

> [cmd]
(let (res)
  (for (i 1 1000000)
    (let (x (Collatz i)) (if (> (length x) (length res)) (setq res x))))
  res)
[/cmd]
(837799 2513398 1256699 3770098 1885049 5655148 2827574 1413787 4241362 2120681 6362044 
 3181022 1590511 4771534 2385767 7157302 3578651 10735954 5367977 16103932 8051966 
 :
 :
 4025983 12077950 6038975 18116926 9058463 27175390 13587695 40763086 20381543  911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 
 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1)
> 

 最長の数列の長さは 525 。繰り返し関数 for も newLISP では標準です。
 さて、問題の要求しているのは、数列の最初の数値 837799 だけですから、もう少し工夫して、

> [cmd]
(let (res '(0 0))
  (for (i 1 1000000)
    (let (x (length (Collatz i))) (if (> x (res 1)) (setq res (list i x)))))
  (res 0))
[/cmd]
837799
> 

 こんな感じ。

 以上、如何でしょうか?

広告

projecteuler2...または、newLISP リストのインデックス操作

 projecteuler も2回目。
 問題2は 1, 2 から始まるフィボナッチ(Fibonacci)数列で四百万を超えない偶数値の和。
 まずは、フィボナッチ数列を求めます。

> [cmd]
(let (fibo '(1 2))
  (while (< (fibo -1) 4000000)
    (push (apply + (-2 2 fibo)) fibo -1))
 (chop fibo))
[/cmd]
(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 
 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578)
> 

 こんな感じ。ここで、関数chop は組込関数で Common Lisp の butlast に相当します。つまり、リストの最後の要素を削除するもの。また Common Lisp では自分で定義する必要のある while も newLISP では組込です。動作は、、、説明いりませんね(笑)。
 今回のもう一つの主題、リストのインデックス操作。そのための関数(nthslice)もありますが、インデックス数を使って直接操作するのが newLISP 流(笑)。暗黙のインデックス機能(Implicit indexing)です。
 上記の中では、リストから最後の要素を取り出す

(fibo -1)

 や最後から二つの要素の部分リストを作る

(-2 2 fibo)

 がそれに相当します。
 そして、本題。求めたフィボナッチ数列から偶数を取り出すのに前回の select-numbers を使ってもよいのですが、述語(条件式)が一つですから、ここは newLISP組込filter を使います。この関数は、リストから述語(条件式)で真(true)になるものだけ返します。

> (filter even? (sequence 1 10))
(2 4 6 8 10)
> 

 もちろん、この関数とは逆に、述語(条件式)で真(true)になるものだけリストから削除する関数clean もあります。
 さてと、問題2の解答は、

> [cmd]
(let (fibo '(1 2))
  (while (< (fibo -1) 4000000)
    (push (apply + (-2 2 fibo)) fibo -1))
  (apply + (filter even? (chop fibo))))
[/cmd]
4613732
> 

 となります。
 あっ、述語(条件式)even? も組込です。説明、、、いりませんね(笑)。

 以上、如何でしょうか?