fu7mu4’s diary

はてなダイアリーから移転しました。

エジプト式分数を計算する

エジプト式分数を計算してみよう。
分数を分子が1の単位分数の和であらわすのだ。

どうしても再帰で考えてしまう。しかたないんよ。

(defun egyptian-fraction (n m)
  (labels ((iter (n m k aux)
	     (if (= n 0)
		 (reverse aux)
		 (if (< (/ n m) (/ 1 k))
		     (iter n
			   m
			   (1+ k)
			   aux)
		     (iter (- (* n k ) m)
			   (* m k)
			   (1+ k)
			   (cons k aux))))))
    ;driver
    (if (= n 1)
	(iter n m (1+ m) nil )
	(iter n m 2 nil))))
(egyptian-fraction 1 3) ;-> (4 12) ;;;1/3 = 1/4 + 1/12