11
＜＜
＜
＞
＞＞
1/1
-
1 ななしのよっしん
2008/11/07(金) 11:33:29 ID: L/0Dq1/Pvz
int G(a,b){return b>0?G(b,a%b):a;}
で動くと思うが -
👍0👎0
-
2 ななしのよっしん
2008/11/07(金) 12:13:19 ID: wftDL6fIj8
最古のアルゴリズムだって事も書いた方がいいのでは。
その所為かアルゴリズムの本では最初に出てくる事が多いし。 -
👍0👎0
-
3 ななしのよっしん
2010/06/12(土) 19:54:35 ID: VWRwrNm8p6
-
👍0👎0
-
4 ななしのよっしん
2010/12/09(木) 23:07:57 ID: M1hNrt49qx
エラトステネスの篩の記事もほしいな
-
👍0👎0
-
5 ななしのよっしん
2013/12/02(月) 21:21:49 ID: SckFaMGQ5w
しかし互除法の記事あるのにユークリッド先生の記事がないのは台パンものですわぁ…
-
👍0👎0
-
6 ななしのよっしん
2013/12/02(月) 21:34:45 ID: gIxAxwRytZ
DとCでまったく同じことやってて、どちらも同じ書き方できるのに
わざわざ違う書き方で並べるのは何の嫌がらせかとｗ -
👍0👎0
-
7 ななしのよっしん
2014/06/08(日) 23:18:41 ID: DR4S8nSeqy
>>1
すげー綺麗だな
引数に型だけ足そう
int GetGcd(int a, int b){return a<b?GetGcd(b,a):(b>0?GetGcd(b,a%b):a);} -
👍0👎0
-
8 ななしのよっしん
2016/04/03(日) 20:04:13 ID: zMqL4A08ZL
>>7
>>1が言いたいのは「aとbの大小比較をする必要が無い」ってことでは？
（b>0 よりも b!=0 か単に b の方が良いとは思うが） -
👍0👎0
-
9 ななしのよっしん
2016/11/10(木) 00:30:48 ID: jvIkoIKVD4
>>8
最初の一回だけ必要なんだよな。
（前提として、最初に与えられる値が a ≧ b としてるから）
まあ、実際に実装する場合はラッパー関数で最初だけ大小比較するんだろうが。 -
👍0👎0
-
10 ななしのよっしん
2017/10/03(火) 21:14:19 ID: zMqL4A08ZL
>>9
その前提、本当に必要？
記事の例を逆さにして、「693と728の最大公約数」を求めてみよう。
0. 693 ÷ 728 → 0 あまり 693
1. 728 ÷ 693 → 1 あまり 35
2. 693 ÷ 35 → 19 あまり 28
3. 35 ÷ 28 → 1 あまり 7
4. 28 ÷ 7 → 4 あまり 0
よって、693と728の最大公約数は7。
大小比較によって手順を1回だけ減らせはするけど、果たしてコードが増える苦労に見合うか… -
👍0👎0
-
11 ななしのよっしん
2019/10/12(土) 19:57:42 ID: R5MLGVvsQz
互除法の拡張（改造物）っていろいろあるけど
この記事の拡張ユークリッド互除法は「互除法の逆行」という名前で呼んでいるpdfがあってなかなかよかった
台風ひまひま -
👍0👎0
＜＜
＜
＞
＞＞
1/1