0 / 0 / 2
Регистрация: 03.01.2013
Сообщений: 113
|
||||||
1 | ||||||
Программа рекурсивного нахождения НОД. Не могу понять.03.01.2013, 23:14. Показов 1239. Ответов 10
Метки нет (Все метки)
Доброе время суток! Программа с рекурсией. Не могу понять строку:
0
|
03.01.2013, 23:14 | |
Ответы с готовыми решениями:
10
Программа метода дихотомии для нахождения экстремумов не работает, не могу понять в чем ошибка Вычисление НОД. не могу понять где ошибка. Программа нахождения НОД двух чисел (нужны комментарии) Вычисление НОД - в чем преимущество рекурсивного подхода перед нерекурсивным? |
500 / 474 / 63
Регистрация: 26.01.2011
Сообщений: 2,033
|
|
03.01.2013, 23:20 | 2 |
А чё тут объяснять ? вернуть значение этого выражения 2 * nod(x / 2, y / 2)
0
|
0 / 0 / 2
Регистрация: 03.01.2013
Сообщений: 113
|
||||||
04.01.2013, 00:16 [ТС] | 4 | |||||
Обычный алгоритм Евклида на нахождение НОДа - понимаю. Бинарный - нет.
Встретил его на одном сайте. Когда стал разбирать его, не совсем понял его суть. Наверное из-за того, что не имел опыта с рекурсиями. Вот именно на этой строке и застопорился щас. По моей логике 2 умножаем на один аргумент, затем на второй. Но, затем мы аргументы делим на 2, т.е. возвращаем числам прежнее значение. Как тогда мы выйдем из рекурсии? По разному пробовал... и изменял код и дополнял. Возможно "полез" не туда, после чего окончательно запутался на очевидном. Вот и решил спросить у людей, которые разберются. Больше не у кого. Спрашивал у знакомого, который учится на айти специальности (почти уже магистр), только понял что мой гуманитарный мозг лучше понимает чем его "айтишный", т.к. человек писал диплом по с++, а не знает даже толком как работает цикл. Вот полный код:
0
|
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
|
|
04.01.2013, 00:35 | 5 |
Мы входим в nod с значениями, уменьшенными в два раза. Этот нод возможно вызовет по рекурсии опять себя - но со значением еще меньше. В итоге настанет тот момент, когда не будет больше рекурсионного вызова и просто вернется какое-то значение. И пойдет такой каскадный ретурн, дойдет до рассматриваемого - nod(x/2, y/2) вернет какое-то значение, оно умножится на два и полученное значение вернется к предыдущему шагу рекурсии и т.д. Лучше объяснить не смогу наверно.
0
|
ComfyMobile
401 / 282 / 34
Регистрация: 24.07.2012
Сообщений: 916
|
|
04.01.2013, 00:39 | 6 |
Не по теме: магистр, это недоспециалист по теме у вас конечное число которое вы получите будет 1, если оба числа четные, а наименьший для четных делитель кроме 1 это 2, поэтому 2 умножить на nod() который вернет 1, либо если они не четные то вернется результат Евклида nod(y, abs(y - x));
0
|
0 / 0 / 2
Регистрация: 03.01.2013
Сообщений: 113
|
|
05.01.2013, 18:59 [ТС] | 7 |
Вчера снова решил подумать над этим кодом, когда время появилось. Что получилось:
К примеру х=8, у=20. Вызывается рекурсия -> 4,10 -> 2,5 -> 1,5 -> (abs 1 - 5) НОД = 4. Вроде бы все понял, одно не понимаю в каком месте происходит умножение на 2? Все получилось, логика есть))), но умножение на 2 впритык не увидел. Ссылка ваша пустая. Перед созданием топика весь день просидел над этим кодом. В интернете все облазил. И вики, и сайты, форумы и на вашем форуме смотрел... Дело в том, что именно НОД меня не интересует. Я знаю 2 простых алгоритма, вычисления НОДа. Это с помощью остатка чисел, или же вычитания меньшего от большего. Ничего сложного там нет. Меня интересует как работает именно эта строка в коде. Выше, как я уже написал, что вроде бы и все ясно, только умножения я не увидел.
0
|
ComfyMobile
401 / 282 / 34
Регистрация: 24.07.2012
Сообщений: 916
|
|
05.01.2013, 22:55 | 8 |
(abs 1 - 5) вобщето это не конец, посмотрите код еще внимательней
Добавлено через 7 минут даже не то что не конец,это делатся не будет
0
|
0 / 0 / 2
Регистрация: 03.01.2013
Сообщений: 113
|
|
07.01.2013, 21:59 [ТС] | 9 |
Если не тяжело, напишите, пожалуйста, что будет "происходить" с аргументами с момента вызова рекурсии если х=8, у=20 -> ?,? ->...
0
|
ComfyMobile
401 / 282 / 34
Регистрация: 24.07.2012
Сообщений: 916
|
|||||||||||
07.01.2013, 22:28 | 10 | ||||||||||
-> 4,10 -> 2,5 -> 1,5 -> это верно, причем мы запомнили что у нас перед этим два раза вызывалось
1
|
0 / 0 / 2
Регистрация: 03.01.2013
Сообщений: 113
|
|
08.01.2013, 02:57 [ТС] | 11 |
0
|
08.01.2013, 02:57 | |
08.01.2013, 02:57 | |
Помогаю со студенческими работами здесь
11
Не могу понять, почему программа работает неправильно( Знаю, что где-то ошибки, но не могу найти Не могу понять почему программа не выводит результат (простейшая программа) Найти НОД трёх чисел, используя рекурсивную функцию нахождения НОД двух чисел программа на рисование не могу понять Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |