Фундаментальные алгоритмы

Два основных фундаментальных алгоритма - это алгоритм деления и алгоритм Евклида

Алгоритм деления - предназначен для вычисления неполного частного и остатка от деления двух целых чисел.

Алгоритм деления

a - делимое

b - делитель

q- неполное частное

r – остаток

Ввод: натуральные числа a и b. Вывод: неотрицательные целые числа Q и R для которых выполнено равенство: a=bq+r и 0≤r<b.

Шаг 1 положить Q=0 и R=a

Шаг 2 если R < b, то сообщить: «частное равно Q , а остаток равен R», и остановится. В противном случае перейти к шагу 3.

Шаг 3 если R ≥ b, то вычесть b из R, увеличить Q на 1 и вернуться к шагу 2

Для правильного прочтения алгоритма нужно придерживаться следующих простых соглашений. Заметим, что алгоритм использует две переменные Q и R. Имена переменных выбраны такими потому, что по завершении работы алгоритма их значения будут равны неполному частному и остатку от деления a на b. (термины «частное» и «остаток» в переводе с английского выглядит как “quotient” и “remainder” отсюда и обозначение). Для вычисления результата шаги 2 и 3 будут повторены несколько раз. Значит они образуют цикл. Значения переменных Q и R будут манятся от цикла к циклу. Именно поэтому они и называются переменными. Изменение значения переменных происходит на шаге 3. Инструкция «вычесть b из R» означает, что переменной R должно быть присвоено новое значение, равное ее значению после окончания предыдущего цикла, уменьшенному на b. Аналогично инструкция «увеличить Q на 1» означает, что значение Q после окончания предыдущего цикла следует увеличить на 1. Предположим, например, что a>b. тогда после первого прохода через шаг 3 мы получим Q=1 и R=a-b. если a-b≥b, то, согласно алгоритму, мы должны выполнить шаг 3 еще раз. Проделав это мы получаем Q=2 и R=a-2b, и т.д. Заметим, что в результате последовательного применения шага 3 мы получаем следующую последовательность значений переменной R: Начальное значение: a 1-й цикл: a-b 2-й цикл: a-2b 3-й цикл: a-3b и т.д. Это убывающая последовательность целых чисел. Поскольку количество чисел между a и 0 конечно, последовательность с необходимостью попадает в число, меньшее b. тогда на шаге 2 работа останавливается, и алгоритм выводит значение переменных R и Q.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.