3:55 pm - Найбільший спільний дільник на Пролозі
НОД на Пролозі
На Пролозі описуються факти. Програма на Пролозі відповідає на запитання на кшталт «чи вірно твердження? »Або« при якому X вірно дане твердження? ». Тому програма обчислення найбільшого загального дільника двох чисел повинна працювати як-то так:- Чи вірно, що НОД (22, 121) = 3?
- При якому G вірно вираз НСД (22, 121) = G?
- gcd2 (22, 121, 3).
- gcd2 (22, 121, G).
Традиційно, НОД шукається за алгоритмом Евкліда, в якому має місце вірний факт: НСД (a, 0) = a. Цей факт в Пролозі записується так: gcd2 (A, 0, A). На питання gcd2 (11, 0, G) буде дана відповідь G = 11. а відповідь на питання gcd2 (11, 0, 3) буде негативним.
Той факт, що НОД (a, b) = g, записується так: gcd2 (A, B, G). На питання gcd2 (22, 121, 11) повинен бути дана позитивна відповідь, на питання gcd2 (16, 32, 8) - негативний, а на питання gcd2 (22, 121, G) - G = 11.
Суть алгоритму Евкліда в тому, що НОД (a, b) = g, якщо НСД (b, n) = g, де n - залишок від ділення a на b. На Пролозі це записується так:
Рано чи пізно N дорівнюватиме нулю, і перевірка факту gcd2 (A, B, G). зведеться до перевірки факту gcd2 (X, 0, X). тобто рівності першого і третього параметра.
мінімальна програма
Мінімальна (неправильна) програма, записана в файл gcd.pl і виглядає так:
Ця програма не працюватиме, тому що рано чи пізно буде поділ на нуль. Справа в тому, що програма на Пролозі шукає всі можливі рішення, не зупиняючись на першому рядку. Щоб город від цього, треба додати, як мінімум, умова B = \ = 0 (B не дорівнює нулю):
А ще краще зажадати позитивні A і B:
Для перевірки використовуємо GNU Prolog 1.3.1. Розширення файлів: PL і PRO, наприклад hello.pl. gcd.pro. Перший варіант пріоритетний (якщо розширення не вказано), але конфліктує з Перлом: якщо в каталозі є файли gcd.pl і gcd.pro. то завантажується gcd.pl (з помилкою, якщо це Перл :-) Тому ім'я файлу краще вказувати повністю, укладаючи в одинарні лапки (через точки в імені).
повноцінна програма
Опис НСД для списку чисел:
Перетворення списку рядків в список чисел (або навпаки, це ж Пролог):
Читається так: список рядків є уявлення списку чисел, якщо перший рядок є поданням першого числа, і залишився список рядків є уявлення, що залишився списку чисел. На питання str2int ([ '22', '11'], [22, 11]) буде дана позитивна відповідь, на питання str2int ([ '22', '11'], X) буде дана відповідь X = [22, 11 ]. на питання str2int ([X, '11'], [22, Y]) буде дана відповідь X = '22', Y = 11.
Точка входу в програму (факт, який треба перевірити відразу після запуску програми):