回答編集履歴
2
追加説明
test
CHANGED
|
@@ -101,3 +101,79 @@
|
|
|
101
101
|
```
|
|
102
102
|
|
|
103
103
|
4行目、つまり elif x&1==0 and y&1==0 and y!=0:のところで、float型とint型で&はできませんというエラーメッセージが出ています。これは理解できますか。
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
自力で解決できたようなので、いくつかのサンプルを載せておきます。
|
|
108
|
+
|
|
109
|
+
|
|
110
|
+
|
|
111
|
+
syoutaro22さんのアルゴリズムですが、これは互減法のアルゴリズムに2だけ割るアルゴリズムを付け加えたものです。こういう発想はプロ的なのですが、syoutaro22さんは初心者ということですので、たまたま思いつけたということなのでしょう。一般的には、数字が小さいときには互減法は互除法より高速なのです。python3の場合は、64ビットを超えると整数の割り算が極端に遅くなるので、その場合も有効かもしれません。
|
|
112
|
+
|
|
113
|
+
|
|
114
|
+
|
|
115
|
+
互減法は、割り算機能のついていない組み込み用の小さなCPUなどでも使います。
|
|
116
|
+
|
|
117
|
+
互減法については[最大公約数をもっと高速に求める](http://lpha-z.hatenablog.com/entry/2019/03/03/231500)などを見てみてください。
|
|
118
|
+
|
|
119
|
+
|
|
120
|
+
|
|
121
|
+
```python
|
|
122
|
+
|
|
123
|
+
def gcd(x, y):
|
|
124
|
+
|
|
125
|
+
if y==0:
|
|
126
|
+
|
|
127
|
+
return x
|
|
128
|
+
|
|
129
|
+
elif x < y:
|
|
130
|
+
|
|
131
|
+
return gcd(y, x) #こうやっておいたほうが間違いが少ない。
|
|
132
|
+
|
|
133
|
+
elif x&1==0 and y&1==0:
|
|
134
|
+
|
|
135
|
+
return 2*gcd(x//2, y//2)
|
|
136
|
+
|
|
137
|
+
elif x&1==0 and y&1==1:
|
|
138
|
+
|
|
139
|
+
return gcd(x//2, y)
|
|
140
|
+
|
|
141
|
+
elif x&1==1 and y&1==0:
|
|
142
|
+
|
|
143
|
+
return gcd(x, y//2)
|
|
144
|
+
|
|
145
|
+
elif x&1==1 and y&1==1:
|
|
146
|
+
|
|
147
|
+
return gcd(x-y, y) # 大きいほうから小さいほうを引く
|
|
148
|
+
|
|
149
|
+
else:
|
|
150
|
+
|
|
151
|
+
print('proguram error') # ここに来るならプログラムの間違い
|
|
152
|
+
|
|
153
|
+
raise(Exception)
|
|
154
|
+
|
|
155
|
+
```
|
|
156
|
+
|
|
157
|
+
一方、互除法でやるには、y_waiwaiさんが勧めていたようにやります。以下をご覧下さい。
|
|
158
|
+
|
|
159
|
+
```python
|
|
160
|
+
|
|
161
|
+
def gcd(x, y):
|
|
162
|
+
|
|
163
|
+
if x < y:
|
|
164
|
+
|
|
165
|
+
return gcd(y, x)
|
|
166
|
+
|
|
167
|
+
elif y==0:
|
|
168
|
+
|
|
169
|
+
return x
|
|
170
|
+
|
|
171
|
+
elif x == x // y*y:
|
|
172
|
+
|
|
173
|
+
return y
|
|
174
|
+
|
|
175
|
+
else:
|
|
176
|
+
|
|
177
|
+
return gcd(x-y, y)
|
|
178
|
+
|
|
179
|
+
```
|
1
修正
test
CHANGED
|
@@ -14,9 +14,11 @@
|
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
これが間違っています。
|
|
17
|
+
~~これが間違っています。
|
|
18
18
|
|
|
19
|
-
まず、互除法をちゃんと理解しましょう。
|
|
19
|
+
まず、互除法をちゃんと理解しましょう。~~
|
|
20
|
+
|
|
21
|
+
gcd((x-y)/2,y)が正しいとのことなので、互除法はわかっていますね。
|
|
20
22
|
|
|
21
23
|
|
|
22
24
|
|