質問編集履歴
5
意図的に削除された質問であったため元に戻しました。
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
|
|
1
|
+
剰余演算を使わずに最大公約数を求めるには
|
body
CHANGED
|
@@ -1,1 +1,43 @@
|
|
|
1
|
+
### 前提・実現したいこと
|
|
2
|
+
プログラミング超初心者で初めて質問させていただきました。
|
|
3
|
+
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
4
|
+
最大公約数をgcd(x,y)とし、
|
|
5
|
+
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
|
|
6
|
+
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
|
|
7
|
+
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
|
|
8
|
+
という要領で計算します。
|
|
9
|
+
できれば演算子％を使わずにお願いします。
|
|
10
|
+
ここに質問の内容を詳しく書いてください。
|
|
11
|
+
### 発生している問題・エラーメッセージ
|
|
12
|
+
```
|
|
13
|
+
def gcd(x, y):
|
|
14
|
+
if y==0:
|
|
15
|
+
return x
|
|
16
|
+
elif x&1==0 and y&1==0 and y!=0:
|
|
17
|
+
x, y=x//2, y//2
|
|
18
|
+
return 2*gcd(x, y)
|
|
19
|
+
elif x&1==0 and y&1==1 and y!=0:
|
|
20
|
+
x=x//2
|
|
21
|
+
return gcd(x, y)
|
|
22
|
+
elif x&1==1 and y&1==0 and y!=0:
|
|
23
|
+
y=y//2
|
|
24
|
+
return gcd(x, y)
|
|
25
|
+
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
26
|
+
x, y=x, (y-x)//2
|
|
27
|
+
return gcd(x, y)
|
|
28
|
+
else:
|
|
29
|
+
x, y=(x-y)//2, y
|
|
30
|
+
return gcd(x, y)
|
|
1
|
-
|
|
31
|
+
print(f'gcd(123456, 65432)={gcd(123456, 65432)}')
|
|
32
|
+
に対してエラーが出ます。
|
|
33
|
+
```
|
|
34
|
+
### 該当のソースコード
|
|
35
|
+
```ここに言語名を入力
|
|
36
|
+
python
|
|
37
|
+
```
|
|
38
|
+
### 試したこと
|
|
39
|
+
自分なりにコードを書いたのですが初歩的なところでつまずいているのかもしれずエラーコードを見ても分かりません。
|
|
40
|
+
とてもレベルの低い質問かもしれませんが、回答してくださればと思います。
|
|
41
|
+
ここに問題に対して試したことを記載してください。
|
|
42
|
+
### 補足情報（FW/ツールのバージョンなど）
|
|
43
|
+
ここにより詳細な情報を記載してください。
|
4
,
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
|
|
1
|
+
####################
|
body
CHANGED
|
File without changes
|
3
、
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,52 +1,1 @@
|
|
|
1
|
-
### 前提・実現したいこと
|
|
2
|
-
プログラミング超初心者で初めて質問させていただきました。
|
|
3
|
-
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
4
|
-
最大公約数をgcd(x,y)とし、
|
|
5
|
-
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
|
|
6
|
-
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
|
|
7
|
-
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
|
|
8
|
-
という要領で計算します。
|
|
9
|
-
できれば演算子％を使わずにお願いします。
|
|
10
|
-
ここに質問の内容を詳しく書いてください。
|
|
11
|
-
|
|
12
|
-
|
|
13
|
-
### 発生している問題・エラーメッセージ
|
|
14
|
-
|
|
15
|
-
```
|
|
16
|
-
def gcd(x, y):
|
|
17
|
-
if y==0:
|
|
18
|
-
return x
|
|
19
|
-
elif x&1==0 and y&1==0 and y!=0:
|
|
20
|
-
x, y=x//2, y//2
|
|
21
|
-
return 2*gcd(x, y)
|
|
22
|
-
elif x&1==0 and y&1==1 and y!=0:
|
|
23
|
-
x=x//2
|
|
24
|
-
return gcd(x, y)
|
|
25
|
-
elif x&1==1 and y&1==0 and y!=0:
|
|
26
|
-
y=y//2
|
|
27
|
-
return gcd(x, y)
|
|
28
|
-
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
29
|
-
x, y=x, (y-x)//2
|
|
30
|
-
return gcd(x, y)
|
|
31
|
-
else:
|
|
32
|
-
x, y=(x-y)//2, y
|
|
33
|
-
return gcd(x, y)
|
|
34
|
-
|
|
35
|
-
|
|
1
|
+
#####################################################################
|
|
36
|
-
に対してエラーが出ます。
|
|
37
|
-
```
|
|
38
|
-
|
|
39
|
-
### 該当のソースコード
|
|
40
|
-
|
|
41
|
-
```ここに言語名を入力
|
|
42
|
-
python
|
|
43
|
-
```
|
|
44
|
-
|
|
45
|
-
### 試したこと
|
|
46
|
-
自分なりにコードを書いたのですが初歩的なところでつまずいているのかもしれずエラーコードを見ても分かりません。
|
|
47
|
-
とてもレベルの低い質問かもしれませんが、回答してくださればと思います。
|
|
48
|
-
ここに問題に対して試したことを記載してください。
|
|
49
|
-
|
|
50
|
-
### 補足情報（FW/ツールのバージョンなど）
|
|
51
|
-
|
|
52
|
-
ここにより詳細な情報を記載してください。
|
2
/→//
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -17,19 +17,19 @@
|
|
|
17
17
|
if y==0:
|
|
18
18
|
return x
|
|
19
19
|
elif x&1==0 and y&1==0 and y!=0:
|
|
20
|
-
x, y=x/2, y/2
|
|
20
|
+
x, y=x//2, y//2
|
|
21
21
|
return 2*gcd(x, y)
|
|
22
22
|
elif x&1==0 and y&1==1 and y!=0:
|
|
23
|
-
x=x/2
|
|
23
|
+
x=x//2
|
|
24
24
|
return gcd(x, y)
|
|
25
25
|
elif x&1==1 and y&1==0 and y!=0:
|
|
26
|
-
y=y/2
|
|
26
|
+
y=y//2
|
|
27
27
|
return gcd(x, y)
|
|
28
28
|
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
29
|
-
x, y=x, (y-x)/2
|
|
29
|
+
x, y=x, (y-x)//2
|
|
30
30
|
return gcd(x, y)
|
|
31
31
|
else:
|
|
32
|
-
x, y=(x-y)/2, y
|
|
32
|
+
x, y=(x-y)//2, y
|
|
33
33
|
return gcd(x, y)
|
|
34
34
|
|
|
35
35
|
print(f'gcd(123456, 65432)={gcd(123456, 65432)}')
|
1
ユークリッドの互除法ではありませんでした。
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
|
|
1
|
+
剰余演算を使わずに最大公約数を求めるには
|
body
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
1
|
### 前提・実現したいこと
|
|
2
2
|
プログラミング超初心者で初めて質問させていただきました。
|
|
3
|
-
題名にもある通り
|
|
3
|
+
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
4
4
|
最大公約数をgcd(x,y)とし、
|
|
5
5
|
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
|
|
6
6
|
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
|