[topic] 分数の発見
Posted feedbacks - Common Lisp
ytakenaka
#6305()
[
Common Lisp
]
表示が不完全だけど、リストを取り出すだけならば >(rationalize-list 1.732051) (12/7 7/4 16/9 5/3 9/5 3/2 2) 分数の時が不完全な表示になります。 >(print-rationalize-list 1920/1080 ) 16/9 => 16/9 9/5 7/4 11/6 12/7 5/3 2/1 NIL 単にニュートン法の応用です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | (defun check (given fraction min max)
(let ((center (floor (/ (+ min max) 2))))
(if (or (equal center min) (equal center max))
(/ (check-near given fraction (cons min max)) fraction)
(if (> (* given fraction) center)
(check given fraction center max)
(check given fraction min center)))))
(defun check-near (given fraction list)
(if (> (- given (/ (car list) fraction))
(- (/ (cdr list) fraction) given))
(cdr list)
(car list)))
(defun rationalize-list (given)
(let (list)
(loop for i from 1 to 9 do
(let ((ans (check given i 0 (* (1+ i) given))))
(and (not (find ans list))
(push ans list))))
(sort list
#'(lambda(x y)(< (abs (- x given))
(abs (- given y)))))))
(defun print-rationalize-list (given)
(let ((list (rationalize-list given)))
(format t "~s => " given)
(loop for v in list do
(multiple-value-bind (f r) (floor v)
(if (zerop r)
(format t "~d/1 " v)
(format t "~d " v))))
(format t "~%")))
|
gandalf #6278() Rating1/1=1.00
schemeにはrationalizeという手続きがありますが、これは結果を一つしか返しません。そして、複数の結果が欲しい場合も稀にあります。
そこで、非負の実数aが一つ与えられたときに、以下の条件を満たす分数b/cをaに近い順に全て表示する手続きを考えてみてください。条件は、 1. 分数b/cよりaに近い分数d/cは存在しない 2. 分数b/cは既約 3. cは1桁の整数 です。
例をいくつかあげます(あってると思うけど...)。
a = 1.732051 12/7 7/4 16/9 5/3 9/5 3/2 2/1
a = 3.141593 22/7 25/8 19/6 28/9 16/5 13/4 3/1
a = 1920 / 1080 16/9 9/5 7/4 11/6 12/7 5/3 2/1
[ reply ]