Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
Teratore |
|
|
Какие есть рекурсивные способы вычисления НОД и соотношения Безу? Шаги итерационного варианта алгоритма Евклида выглядят так: НОД(1071,147) = 21; 1071 = 2 × 462 + 147. 462 = 3 × 147 + 21. 147 = 7 × 21 + 0. Можно ли утверждать что запись НОД(1071,147) = НОД(1047 % 147, 147) = НОД(462,147) = НОД(21,147) = НОД(21, 147%21) = НОД(21,0) = 21 Это тот же алгоритм Евклида только в рекурсивной формулировке? Или я ошибаюсь? И можно ли как-то записать это более развернутом виде? Как организовать что-нибудь аналогичное для вычисления соотношения Безу(для расширенного алгоритма Евклида)? |
||
Вернуться к началу | ||
Booker48 |
|
|
Посмотрите "Алгебраическую алгоритмику" Ноден, Китте в сети. Там всё это есть.
|
||
Вернуться к началу | ||
За это сообщение пользователю Booker48 "Спасибо" сказали: Teratore |
||
Teratore |
|
|
Booker48 писал(а): Посмотрите "Алгебраическую алгоритмику" Ноден, Китте в сети. Там всё это есть. Посмотрел. Все тоже самое НОД(bq+r,b) = НОД(b,r) Нашел еще вот что: НОД(a,b,c) = НОД(НОД(a,b),c) И запутался еще больше. Что в теме реферата может означать фраза "Рекурсивное вычисление НОД целых чисел" ? Не с точки зрения компьютерной реализации(алгоритм Евклида можно реализовать через рекурсию), а с точки зрения математической записи? Т.е мне нужно сделать что-то вроде "отчета" с примерами, где я покажу как я "рекурсивно вычисляю нод целых чисел" Вариантов в итоге 2 : 1. Вместо стандартного итерационного варианта алгоритма Евклида писать НОД(1071,147) = НОД(1047 % 147, 147) = НОД(462,147) = НОД(21,147) = НОД(21, 147%21) = НОД(21,0) = 21 2. Ну или же имелось ввиду вычисление нескольких чисел. НОД(a,b,c) = НОД(НОД(a,b),c) |
||
Вернуться к началу | ||
Booker48 |
|
|
Если о теме реферата, кроме названия, ничего не известно, то предлагаю написать про первый вариант. Если рекурсивная функция вычисления GCD реализована, то второй вариант - это просто добавить одну строчку к уже написанному.
|
||
Вернуться к началу | ||
Teratore |
|
|
Booker48 писал(а): Если о теме реферата, кроме названия, ничего не известно, то предлагаю написать про первый вариант. Если рекурсивная функция вычисления GCD реализована, то второй вариант - это просто добавить одну строчку к уже написанному. Ну, в принципе да. Первого варианта еще нету. Ну т.е утверждение НОД(1071,147) = НОД(1047 % 147, 147) = НОД(462,147) = НОД(21,147) = НОД(21, 147%21) = НОД(21,0) = 21 это пример рекурсивного вычисления НОД с помощью Алгоритма Евклида подходит? Т.е что-то следующего вида: [math]\left[\!\begin{aligned} & GCD(a,0) = a \\ & GCD(a,b) = GCD( a \pmod{ b } ,b) \end{aligned}\right.[/math] Как тогда расширенный алгоритм Евклида представить рекурсивно? |
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Рекурсивное вычисление коррекции синусоиды
в форуме Дифференциальное исчисление |
0 |
293 |
06 дек 2016, 18:37 |
|
Рекурсивное определение вещественных чисел
в форуме Теория чисел |
2 |
356 |
12 апр 2021, 13:40 |
|
Вычисление
в форуме Дифференциальное исчисление |
4 |
382 |
27 апр 2014, 21:17 |
|
Вычисление
в форуме Алгебра |
5 |
400 |
11 сен 2017, 15:13 |
|
Вычисление определителя
в форуме Линейная и Абстрактная алгебра |
1 |
317 |
12 ноя 2015, 20:23 |
|
Вычисление процентов
в форуме Алгебра |
2 |
222 |
07 дек 2017, 17:45 |
|
Вычисление предела
в форуме Пределы числовых последовательностей и функций, Исследования функций |
1 |
336 |
17 ноя 2014, 20:33 |
|
Вычисление предела
в форуме Пределы числовых последовательностей и функций, Исследования функций |
1 |
216 |
25 ноя 2014, 23:47 |
|
Вычисление интегралов
в форуме Интегральное исчисление |
5 |
294 |
17 янв 2018, 15:57 |
|
Вычисление интеграла
в форуме Интегральное исчисление |
5 |
254 |
17 янв 2018, 18:40 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |