 |
|
Модераторы: Poseidon |
 
|
|
[Теория алгоритмов]Машина Шёнфилда 
| breaking |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 24.2.2007 Репутация: 1 Всего: 1 |
Помогите составить Машину Шёнфилда для следующей функции:
f(x,y) = |x-y| |
|||
|
||||
Загрузка ...
| andrew_121 |
|
|||
 Кодофей  Профиль Группа: Завсегдатай Сообщений: 3448 Регистрация: 3.1.2008 Репутация: 0 Всего: 33 |
breaking, Гугл тебе в руки.
-------------------- Удалил аккаунт. Прощайте! |
|||
|
||||
| breaking |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 24.2.2007 Репутация: 1 Всего: 1 |
Понимаешь тут особо и гуглить ничего не надо. Основную идею я понимаю, просто никак не могу понять один момент, сейчас объясню более конкретно. Программирование машин Шёнфилда чем-то напоминает программирование на языке Assembler:
Машина Шёнфилда имеет бесконечное число регистров, пронумерованных натуральными числами, начиная с 0. Каждый из этих регистров может содержать любое натуральное число. Для любой программы нам будет необходимо лишь конечное число регистров, которое нетрудно заранее определить по программе. Кроме этого у машины есть специальная память для программы, а также счётчик команд, всегда содержащий некоторое натуральное число. Программа для машины Шёнфилда состоит из конечного списка команд, последовательно пронумерованных натуральными числами начиная с 0. Перед запуском в машину вводится программа, в регистры заносятся начальные данные, а в счётчик команд заносится значение 0. После этого шаг за шагом осуществляется работа машины. Шаг машины состоит в исполнении команды, номер которой указан в счётчике команд. Если такого номера команды нет, то машина останавливается. Существеует два типа команд:
Вот несколько макросов: Макрос GOTO n 0: INC 0 1: DEC 0, n Макрос ZERO I. Этот макрос, который обнуляет содержимое I-го регистра. Состоит такой макрос всего из одной команды - DEC I, 0. Макрос [i] -> [j], (k), где i, j != k. Этот макрос копирует содержимое i-го регистра в j-й регистр, используя k-й регистр в качестве вспомогательного. Содержимое i-го регистра при i != j не изменяется. Программа для макроса [i] -> [j], (k) при i != j выглядит так: 0: ZERO j 1: ZERO k обнулили j-й и k-й регистры 2: GOTO 5 переход на 5-ю команду 3: INC j 4: INC k 5: DEC i, 3 если в i-м регистре не 0, увеличим i-й и k-й регистры 6: GOTO 8 7: INC i 8: DEC k, 7 копирование из k-го регистра в i-й Если i = j, то можно взять любую программу, которая ничего не меняет, например 0: GOTO 1 Макрос F([i1], ..., [ik] -> [j] вычисляет значение функции F, вычислимой по Шёнфилду с помощью программы P, от содержимого регистров [i1], ..., [ik], записывает это значение в j-й регистр и при этом не изменяет значения остальных регистров. Следующая машина определяет функцию сложения sum(x, y) = x + y 0: [2] -> [0] 1: GOTO 3 2: INC 0 3: DEC 1, 2 Для функции умножения mult(x, y) = x * y 0: ZERO 0 1: GOTO 3 2: sum([0], [2]) -> [0] 3: DEC 1, 2 А теперь возвратимся к моей задаче - f(x,y) = |x-y|. Как можно прочитать выше регистры могут содержать только натуральные числа, т.е. отрицательных там быть не может. В таком случае как же реализовать нужную мне функцию и, к примеру, функцию вычитания - sub(x,y) = x - y??? Вот мой пример реализации sub(x,y) = x - y 0: [1] -> [0] 1: INC 0 2: DEC 0, 4 3: GOTO 5 4: DEC 2, 2 Но он по ходу неверный... |
|||
|
||||
| solverr |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 17 Регистрация: 31.12.2008 Репутация: 1 Всего: 1 |
0. DEC 1, 2
1. GOTO 4 2. DEC 2, 0 3. INC 1 4. ZERO 0 5. DEC 1, 7 6. GOTO 9 7. INC 0 8. GOTO 5 9. DEC 2, 11 10. GOTO 13 11. INC 0 12. GOTO 9 13. HAPPY END |
|||
|
||||
| Aplles |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 7.5.2009 Репутация: нет Всего: нет |
Преветcтвую всех. Что-то никак не вникну в смысл машин Шёнфилда, и потому помогите плиз составить машину Шёнфилда для функции:
f(x,y) = x^y и f(x,y) =|sqrt(x)| |
|||
|
||||
Дата 7.5.2009, 09:53 (
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0649 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |