Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Рекурсивное вычисление НОД
СообщениеДобавлено: 24 дек 2017, 15:53 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день!
Какие есть рекурсивные способы вычисления НОД и соотношения Безу?

Шаги итерационного варианта алгоритма Евклида выглядят так: НОД(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 Это тот же алгоритм Евклида только в рекурсивной формулировке? Или я ошибаюсь? И можно ли как-то записать это более развернутом виде?

Как организовать что-нибудь аналогичное для вычисления соотношения Безу(для расширенного алгоритма Евклида)?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекурсивное вычисление НОД
СообщениеДобавлено: 24 дек 2017, 19:06 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5207
Cпасибо сказано: 340
Спасибо получено:
923 раз в 872 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Посмотрите "Алгебраическую алгоритмику" Ноден, Китте в сети. Там всё это есть.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
Teratore
 Заголовок сообщения: Re: Рекурсивное вычисление НОД
СообщениеДобавлено: 24 дек 2017, 22:50 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекурсивное вычисление НОД
СообщениеДобавлено: 25 дек 2017, 00:11 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5207
Cпасибо сказано: 340
Спасибо получено:
923 раз в 872 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Если о теме реферата, кроме названия, ничего не известно, то предлагаю написать про первый вариант. Если рекурсивная функция вычисления GCD реализована, то второй вариант - это просто добавить одну строчку к уже написанному. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Рекурсивное вычисление НОД
СообщениеДобавлено: 25 дек 2017, 00:24 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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]


Как тогда расширенный алгоритм Евклида представить рекурсивно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Рекурсивное вычисление коррекции синусоиды

в форуме Дифференциальное исчисление

dorringtorr

0

293

06 дек 2016, 18:37

Рекурсивное определение вещественных чисел

в форуме Теория чисел

rain_walker

2

356

12 апр 2021, 13:40

Вычисление

в форуме Дифференциальное исчисление

Danly

4

382

27 апр 2014, 21:17

Вычисление

в форуме Алгебра

qorsac

5

400

11 сен 2017, 15:13

Вычисление определителя

в форуме Линейная и Абстрактная алгебра

rfgbnfkbyf

1

317

12 ноя 2015, 20:23

Вычисление процентов

в форуме Алгебра

Allexxx

2

222

07 дек 2017, 17:45

Вычисление предела

в форуме Пределы числовых последовательностей и функций, Исследования функций

Cr0ss

1

336

17 ноя 2014, 20:33

Вычисление предела

в форуме Пределы числовых последовательностей и функций, Исследования функций

alexandrkamarov

1

216

25 ноя 2014, 23:47

Вычисление интегралов

в форуме Интегральное исчисление

Westr

5

294

17 янв 2018, 15:57

Вычисление интеграла

в форуме Интегральное исчисление

hunn74

5

254

17 янв 2018, 18:40


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved