Skip to content
Логотип

1000+ полезных советов…

Это Гадалка ОНЛАЙН
пиши вопрос - получай ответ:
"ДА" или "НЕТ"




ИНТЕРЕСНЫЕ ТЕСТЫ ОНЛАЙН

(поиск по сайту - ниже)
ЧТО ДЕЛАТЬ | 1000+ избранных полезных советов… » IT / Компьютеры » Алгоритмы с прерыванием, бесконечные алгоритмы, которые не решаются

IT / Компьютеры » Алгоритмы с прерыванием, бесконечные алгоритмы, которые не решаются

Просмотров: 2087 | 6-10-2013, 11:40

Алгоритмы с прерыванием, бесконечные алгоритмы, которые не решаются

В предыдущих темах todid.ru мы много говорили об алгоритмах и алгоритмизации процессов. В данной статье мы попробуем составить наглядный пример схемы действий, применительно к конкретной задаче.

Например, если попробовать описать в виде алгоритмического процесса действия мифологического Сизифа, то окажется, что за любое конечное число шагов желаемый для него результат (подъем камня на вершину скалы) недостижим в силу возникновения непреодолимых препятствий.

Задача Ахиллеса



Если попытаться построить алгоритм решения задачи, в основе которой лежит известный логический парадокс:

«За какое время Ахиллес догонит черепаху, если в каждый момент времени движется в 10 раз быстрее, чем она, то поскольку при таких условиях расстояние между «соревнующимися» будет сокращаться до бесконечности, но никогда не исчезнет, алгоритм решения задачи за конечное количество шагов не даст результата».

Деление 10 на 3



Известен пример бесконечного алгоритмического процесса, который получается при переводе неправильной дроби в десятичную.

Процесс деления 10 на 3 может продолжаться беспрепятственно до бесконечности. Значит, известный алгоритм неприменим, поскольку не позволяет получить точное значение частного за конечное число шагов. Однако если поставить задачу иначе, предусмотрев обрыв алгоритма на каком-то шаге (вычисление с заданной точностью, уточнение алгоритма) — алгоритм окажется результативным.

То же можно сказать о нем, если считать 3 (3) точным значением частного от деления 10 на 3.




Пример незавершенного алгоритма



1.1. Типичен пример, когда алгоритмический процесс безрезультатно обрывается. Пусть алгоритм состоит из следующей последовательности предписаний (они записаны ниже в виде текста п.п. 1—4):

1. Исходное данное умножить на 3.
2. К полученному результату прибавить 2.
3. Определить остаток «Х» от деления полученной суммы на 4.
4. Разделить исходные данные на «Х».

1.2. Предоставляем читателю возможность самому убедиться в том, что если исходное данное равно:

4K + 2, (K = 0, 1, ...)

например, числу 2, «Х» оказывается равным «0» и алгоритм безрезультатно обрывается, поскольку деление оказывается невозможным и п. 4 не выполним.

Пример расчета, где К=0:
4 х 0 + 2 = 2;
2 х 3 = 6;
6 + 2 = 8;
8 / 4 = 2,0
ЦЕЛАЯ ЧАСТЬ = 2, а ОСТАТОК = 0

Таким образом, следует считать, что множество значений исходных данных для приведенного алгоритма состоит из любых вещественных чисел, исключая целые вида 4K + 2.





Почитайте похожие тексты по вашему вопросу:





Архивы

Декабрь 2016 (3)
Сентябрь 2016 (2)
Июль 2016 (1)
Июнь 2016 (5)
Май 2016 (7)
Апрель 2016 (13)

ВВЕРХ