Помогите мне найти ошибку в алгоритме наибольшего общего делителя в python

Итак, я написал

function gcd(a, b)
  if b <> 0
    gcd (b, a % b)
  else
    return a

print gcd (12, 9)

Такие вот дела:

  1. НОД(12, 9)
  2. 9 ‹> 0 означает ИСТИНА
  3. НОД(9, 12 % 9 = 3)
  4. 3 ‹> 0 означает ИСТИНА
  5. НОД(3, 9 % 3 = 0)
  6. 0 ‹> 0 означает ЛОЖЬ
  7. вернуть a, который равен 3, но ничего не возвращает

Не могли бы вы помочь мне найти мою ошибку?


algorithm greatest-common-divisor
person Community    schedule 07.09.2011    source источник
comment
Я думаю, вы хотите вернуть B, а не A   -  person Sparky    schedule 07.09.2011
comment
@Sparky - я так не думаю. В строке, где он возвращает a, гарантируется, что b равно 0.   -  person Ted Hopp    schedule 07.09.2011
comment
В некоторых языках (например, в Perl) возвращаемое значение функции — это значение последнего вычисленного выражения. В других языках вам нужно явно сказать return, чтобы что-то вернуть.   -  person Ted Hopp    schedule 07.09.2011
comment
Кстати, <> следует избегать; он удален в Python 3 и уже давно не рекомендуется. != является принятым синтаксисом.   -  person Wooble    schedule 07.09.2011
comment
Что касается вашего редактирования: предложенное мной решение сработало для меня в Python. Можете ли вы показать свой код Python?   -  person Ted Hopp    schedule 07.09.2011

Ответы (1)


arrow_upward
5
arrow_downward

Я думаю, вам нужна эта строка:

return gcd (b, a % b)

вместо просто:

gcd (b, a % b)

Вот мой код Python, показывающий решение в действии:

>>> def gcd(a,b):
...   if b != 0:
...     return gcd(b, a % b)
...   else:
...     return a
...
>>> print gcd(12,9)
3
>>>

Это было с Python 2.4.3 в Linux.

person Ted Hopp    schedule 07.09.2011
comment
Ах. Только что понял это и собирался ответить, когда ты опередил меня. - person Nicholas; 07.09.2011
comment
@Templatar: предположить что-либо о языке на основе того, что делают другие языки, — это самый быстрый способ облажаться;) - person ; 07.09.2011
comment
@Templar - я добавил расшифровку своего решения, работающего на Python. - person Ted Hopp; 07.09.2011
comment
Если вам кажется странным, когда два языка программирования ведут себя по-разному, всегда будьте готовы к странностям! - person recursive; 07.09.2011