Машина з натуральночисельними регістрами
Машина з натуральночисельними регістрами, – ще одна модель для теорії алгоритмів. Не така відома, як машина Тюрінга, зате (як на мене) для неї легше складати алгоритми.
Але складати алгоритми на папірці не цікаво, тому я написав маленьке середовище, яке допомагає нам складати і перевіряти алгоритми. Ось як воно виглядає:
Зкачати можна звідси (213Кб Rar)
А ось довідка до нього:
// Дві похилі риски (як на початку цього рядка) задають коментар //На початку рядка можна описати мітку на цей рядок записавши // ідентифікатор мітки (послідовність букв і цифр) і закриваючу дужку. // Система має 100 регістрів (від 0 до 99). //Їх вміст можна побачити зправа. // Всі значення регістрів - цілі числа від 0 до 65 535. // Система має чотири команди : // Z(номер_регістру - встановлює //значення регістру в нуль. // S(номер_регістру - збільшує //значення регістру на одиницю // T(номер_регістру1,номер_регістру2 - // копіює значення регістру 1 в регістр 2 // J(номер_регістру1,номер_регістру2, ідентифікатор мітки // - якщо регістри 1 і 2 мають однакові значення, // то перейти до команди з міткою заданою //в третьому параметрі. Інакше перейде до наступної команди. // Команда якої нема в теорії, але вона //дуже потрібна на практиці - ввід. // I(номер_регістру - призупиняє роботу, //щоб попросити користувача ввести дані в регістр // При переході на мітку якої не існує, //або після виконання останньої команди програма зупиняється. //Зайві пропуски будуть викликати помилки в роботі. //Кожна команда знаходиться в новому рядку //Важливо зауважити що закриваюча дужка //Відділяє мітку від команди, тому не закривайте дужки
А це приклад програми, яка шукає модуль різниці двох чисел. Як бачимо все дуже просто 🙂
//Модуль різниці
I(0//Ввід
I(1
J(0,1,zero//Якщо числа рівні, то різниця - нуль
T(0,10// Копія даних
T(1,11
loop)S(0//Збільшуємо перше
S(2//Збільшуємо лічильник
J(0,1,min1//Якщо після збільшення перше стало рівне
//другому, то воно менше
J(2,1,min2//Якщо лічильник рівний другому числу, то //вже нема сенсу його шукати
J(0,0,loop
zero)Z(0//Різниця - нуль
J(0,0,exit
//Якщо перше менше, то міняємо перше і друге місцями
min1)T(10,1
T(11,0
J(0,0,sub
//Інакше все робим як було
min2)T(10,0
T(11,1
//Тепер маємо два числа в 0 і 1 регістрах
//При чому перше строго більше ніж друге
//Тому просто їх віднімаємо
//Принцип: z=x-y => x=y+z (знайти z таке що x=y+z)
sub)Z(2
loop2)J(0,1,res
S(1
S(2
J(0,0,loop2
res)T(2,0//Результат має міститись в нульовому регістрі
[…] з натуральночисельними регістрами Я вже раз про МНР писав, але ця машина просто ляля. Тому раджу […]
Виконання повороту « Інформаційні технології
22 Червня, 2009 at 15:06