Алгоритми з перериванням, нескінченні алгоритми, які не вирішуються - що робити 1000 обраних
У попередніх темах todid.ru ми багато говорили про алгоритми і алгоритмізації процесів. У даній статті ми спробуємо скласти наочний приклад схеми дій, стосовно до конкретного завдання.
Наприклад, якщо спробувати описати у вигляді алгоритмічного процесу дії міфологічного Сізіфа, то виявиться, що за будь-яке кінцеве число кроків бажаний для нього результат (підйом каменю на вершину скелі) недосяжний в силу виникнення непереборних перешкод.
завдання Ахіллеса
Якщо спробувати побудувати алгоритм рішення задачі, в основі якої лежить відомий логічний парадокс:
«За який час Ахіллес наздожене черепаху, якщо в кожен момент часу рухається в 10 разів швидше, ніж вона, то оскільки при таких умовах відстань між« змагаються »буде скорочуватися до нескінченності, але ніколи не зникне, алгоритм вирішення задачі за кінцеве кількість кроків не дасть результату ».
Розподіл 10 на 3
Відомий приклад нескінченного алгоритмічного процесу, який виходить при перекладі неправильного дробу в десяткову.
Процес поділу 10 на 3 може тривати безперешкодно до нескінченності. Значить, відомий алгоритм застосуємо, оскільки не дозволяє отримати точне значення приватного за кінцеве число кроків. Однак якщо поставити завдання інакше, передбачивши обрив алгоритму на якомусь етапі (обчислення із заданою точністю, уточнення алгоритму) - алгоритм виявиться результативним.
Те ж можна сказати про нього, якщо вважати 3 (3) точним значенням частки від розподілу 10 на 3.
Приклад незавершеного алгоритму
1.1. Типовий приклад, коли алгоритмічний процес безрезультатно обривається. Нехай алгоритм складається з наступної послідовності приписів (вони записані нижче у вигляді тексту п.п. 1-4):
1. Початкове дане помножити на 3.
2. До отриманого результату додати 2.
3. Визначити залишок «Х» від ділення одержаної суми на 4.
4. Розділити вихідні дані на «Х».
1.2. Надаємо Новомосковсктелю можливість самому переконатися в тому, що якщо вихідне дане одно:
наприклад, числу 2, «Х» виявляється рівним «0» і алгоритм безрезультатно обривається, оскільки розподіл виявляється неможливим і п. 4 не здійснимо.
Приклад розрахунку, де К = 0:
4 х 0 + 2 = 2;
2 х 3 = 6;
6 + 2 = 8;
8/4 = 2,0
ЦЕЛАЯ ЧАСТИНА = 2, а ЗАЛИШОК = 0
Таким чином, слід вважати, що безліч значень вихідних даних для наведеного алгоритму складається з будь-яких дійсних чисел, крім цілі виду 4K + 2.
Інші новини по темі:
