Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Соревнования по логическому программированию
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию Соревнования по логическому программированию - 04.02.2006, 16:58

Очередное продолжение знаменитой темы о сравнении языков.

Соревнования по логическому программированию. 1999-2005 годы.
Интересно было бы посмотреть на решения этих задачек на различных языках.
Не уверен, что даже на задачках "заточенных" под Пролог, императивные языки окажуться беспомощными.
Постепенно буду переводить задачки на русский и выкладывать сюда.
Также, по мере возможности буду решать задачки.
Bсех, у кого есть время, силы и желание, приглашаю присоединиться .

11 - http://www.cs.kuleuven.ac.be/~bmd/PrologPr...ontest2005.html
10 - http://www.cs.kuleuven.ac.be/~remko/prolog/contest/
9 - http://www.cs.kuleuven.ac.be/~bmd/PrologPr...ontest2003.html
8 - http://www.cs.kuleuven.ac.be/~bmd/PrologPr...ontest2002.html
7 - http://www.cs.kuleuven.ac.be/~bmd/PrologPr...ontest2001.html
6 - http://www.cs.kuleuven.ac.be/~bmd/PrologPr.../Contest99.html

Во многих задачах в качестве входных данных используются прологовские базы данных. Для решения этих задач на других языках формат входных данных можно менять,
предварительно показав, что изменение формата не изменяет задачу.
Ответить с цитированием
  (#2 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 05.02.2006, 19:09

Прочитал 2005 - замечательно. Только кроме задачки про дерево я ничего не понял. Догадываюсь (чисто на интуитивном уровне) задачку о лжецах[who did it] и еще пару, но перевести по-человечески не могу. PROMT вааще урод. Так тупо переводит...
Ответить с цитированием
  (#3 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 06.02.2006, 12:35

Задачка из 11го соревнования:

Нужно сделать эмулятор машины Тьюринга.
Входные данные(файл):
Первая строка в файле - начальное состояние ленты.
остальные строки вида:
состояние символ новое_состояние новый_символ направление(right,left или stay).

Пример:
11111
q0 1 q0 b right
q0 _ qf _ stay

Результат выполнения:
bbbbb_

Соглашения:
пустую клетку на ленте обозначим '_'
начальное состояние называется q0, конечное qf, остальные как угодно (название состояния не должно
включать пробел), на названия состояний можно ввести дополнительные ограничения, это не принципиально.

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

Update:
слегка приблизил тот бред, который сперва написал к нормальному описанию задания.
Ответить с цитированием
  (#4 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 06.02.2006, 17:17

Придумалось очень забавное решение на Питоне.
Эта программа переводит полученное описание машины Тьюринга в программу на Питоне, после чего выполняет получившуюся программу.
если раскомментировать строку "#print prog", можно увидеть текст новорожденной программы:

Input:
Код:
11111 
q0 1 q0 b right 
q0 _ qf _ stay
Output:
Код:
while(1):
  if st=="qf":print "".join(lst);break
  elif st=="q0" and lst[index]=="1":change("q0","b","right")
  elif st=="q0" and lst[index]=="_":change("qf","_","stay")
  else:print "".join(lst);break

bbbbb_

Собственно программа:
Код:
from string import *

st='q0'
index=0

def change(state,symb,direction):
    global st,lst,index
    st=state
    lst[index]=symb
    if (direction=='left'): index-=1;
    if (direction=='right'): index+=1;
    if (index==len(lst)): lst+=['_']
    if (index==-1): lst=['_']+lst;index=0

f1=open('1.txt','r')
lst=list(strip(f1.readline()))
output='print "".join(lst);breakn'
prog='while(1):n  if st=="qf":'+output
for tmp in f1:
    [s,ch,ns,nch,d]=rsplit(tmp)
    prog+='  elif st=="'+s+'" and lst[index]=="'+ch+'":'
    prog+='change("'+ns+'","'+nch+'","'+d+'")n'
prog+='  else:'+output    
#print prog
exec(prog)
f1.close()
Ответить с цитированием
  (#5 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 07.02.2006, 01:30

Вот еще одна классная задачка, на этот раз из десятого соревнования:

Есть бесконечный клетчатый лист, по этому листу ходит черепаха, оставляя за собой следы (клетка, на которой
побывала черепаха, помечается).
Черепаха умеет выполнять две комманды:
вперед - идет на одну клетку вперед
повернись - поворачивается на 90 градусов по часовой стрелке

дана последовательность комманд, нужно найти МИНИМАЛЬНУЮ последовательность комманд, при которой остается такой же след.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
StarLey StarLey вне форума
Новичок
 
Сообщений: 11
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 28.03.2006
По умолчанию 06.04.2006, 19:51

Немного непонял? Получаеться что след циклически повторяеться?
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Книги по программированию Викентий Офтопик 2 11.01.2011 01:39
Запись сектора по его логическому номеру videomag Assembler 1 25.10.2010 19:52
зачет по Рекурсивно-логическому программированию. Заранее благодарен. GexogenSG1 Prolog 0 30.10.2009 17:38
2 задачи на си по программированию. STS Задания за деньги 2 06.06.2009 02:32
После переустановки виндовс нет доступа к логическому диску. Роман 84 Техническая поддержка 11 05.03.2009 22:49
соревнования nameAnn Prolog 6 26.12.2008 15:58
Нет доступа к логическому диску D. Thump Техническая поддержка 3 09.07.2008 16:11
Как открыть доступ к логическому диску по локальной сети? Rusik-ab Любые вопросы от новичков 2 21.04.2008 02:09
Контесты по программированию Greck Алгоритмы 1 24.03.2005 00:45
Инструмент для обучения логическому программированию!!! J7 Prolog 24 24.12.2004 00:13
Кубок по программированию Александра Ефименкова Некоммерческие проекты 0 20.04.2004 14:17



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов