最大公約数（除算禁止）
Posted feedbacks - Other
出題者です. 『The Art of Computer Programming』や, 参考ページに挙げたサーベイに歴史が載っていました.
二進互除法を考えたのは, SteinとSilver and Terzianです. Knuth先生曰く一番古いのは以下だそうです.
前漢の中国の数学書『九章算術』の第1章「方田」の第6問より引用.
> (6) 方田: 又有九十一分之四十九。問約之得幾何？
> 答曰：十三分之七。
> 約分術曰：可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也。以等數約之。
see: R. P. Brent “Twenty years' analysis of the binary Euclidean algorithm”
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]