VPF::Правильность алгоритма - Форум программистов

oxonius

Дата 2.3.2011, 21:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 2.3.2011

Репутация: нет
Всего: нет

Даётся такой вот безобидный псевдокод:

Код


#предусловие: m и n - положительные натуральные числа
a = m
b = n
while a != b:
    if a < b:
        a += m
    else
        b += n
# пост-условие: a - это наименьшее кратное n и m, но как минимум не меньше самих  m и n

Собственно нужно доказать корректность данного алгоритма. Предположу (так как сам пытался по этому пути) использование понятий инварианта цикла и математической индукции при доказательстве с учётом того что алгоритм завершается в целом (?)

Это сообщение отредактировал(а) oxonius - 2.3.2011, 21:39

Akina

Дата 2.3.2011, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

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

делится на m
делится на n
не меньше самих m и n
является наименьшим

По-моему, все 4 пункта доказываются элементарно.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »