Пятница, 29.03.2024, 04:48
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2020 » Май » 31 » Задача 527. Алгоритм Евклида
19:34
Задача 527. Алгоритм Евклида

Задача 527. Алгоритм Евклида

Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере.

Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r. Отсюда становится понятно, что k равно целой части от деления a на b, а r - остатку от деления.

Таким образом, алгоритм Евклида можно реализовывать через операцию взятия остатка от деления. Время работы этой версии алгоритма оценивается теоремой Ламе, которая устанавливает связь алгоритма Евклида и последовательности Фибоначчи (Задача 147. Числа Фибоначчи):

Просмотров: 410 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Май 2020  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2024