Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Правильность алгоритма

Автор: oxonius 2.3.2011, 21:38

Даётся такой вот безобидный псевдокод: Код #предусловие: m и n - положительные натуральные числа a = m b = n while a != b:     if a < b:         a += m     else         b += n # пост-условие: a - это наименьшее кратное n и m, но как минимум не меньше самих  m и n Собственно нужно доказать корректность данного алгоритма. Предположу (так как сам пытался по этому пути) использование понятий инварианта цикла и математической индукции при доказательстве с учётом того что алгоритм завершается в целом (?)

Автор: Akina 2.3.2011, 23:22

Пффф... Надо доказать 4 вещи - что результат, полученный в a (ну и в b - ибо условием окончания является их равенство): делится на m делится на n не меньше самих m и n является наименьшим По-моему, все 4 пункта доказываются элементарно.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)