Prolog — задача 161 линейка

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 месяца назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6733
      @admin
      StudLance.ru

      Задача:

      При построении восемь мальчиков разместились так, что:
      1) А был впереди Б и В;
      2) Б – впереди К через одного;
      3) Л – впереди А, но после Д;
      4) В – после Е через одного;
      5) Д – между Б и Г;
      6) Е – рядом с К, но впереди В.
      В каком порядке выстроились мальчики?

      Приведенные тут варианты решения очень легко читаются — я думаю, к ним не нужны дополнительные пояснения. Если что-то не понятно — спрашивайте. Наиболее сложные предикаты — входит_в, без_повторов и убрать_повторы подробно разобраны тут. Там же, объясняется как понять findall. Также, понять решение может помочь статья «Решение логических задач на Prolog«.

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

      Решение 1

      DOMAINS 
      	мальчик = а;б;в;г;д;е;к;л
      	позиция = integer
      	
      	структура_гипотезы=позиция_мальчика(мальчик, позиция)
      	гипотеза = структура_гипотезы*
      	
      	позиции = позиция*
      PREDICATES
             nondeterm входит_в(позиция, позиции)
             nondeterm входит_в(структура_гипотезы, гипотеза)
             
             nondeterm выбрать_элемент(позиция, позиции, позиции)
             nondeterm перестановки(позиции, позиция, позиции)
             
             nondeterm число_в_диапазоне(integer, integer, integer)     
             
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm между(integer, integer, integer)
             nondeterm рядом(integer, integer)
            
      CLAUSES 
          	число_в_диапазоне(От, _До, От).
          	число_в_диапазоне(От, До, Число):-
          		От < До,
            		СледующееОт = От+ 1, 
            		число_в_диапазоне(СледующееОт, До, Число).
      
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      	  	входит_в(Элемент, Хвост_списка).   
      	  
      	выбрать_элемент(Элемент, [Элемент|Хвост], Хвост).
      	выбрать_элемент(Элемент, [ПервыйЭлемент|Хвост], [ПервыйЭлемент|ХвостРезультата]):-
        		выбрать_элемент(Элемент, Хвост, ХвостРезультата).
        		
        	перестановки(_Список, 0, []).
      	перестановки(Список, ДлинаПерестановки, [ПервыйЭлемент|ПерестановкаХвоста]):-
       		выбрать_элемент(ПервыйЭлемент, Список, Хвост), 
        		ДлинаПерестановкиХвоста = ДлинаПерестановки - 1,
        		перестановки(Хвост, ДлинаПерестановкиХвоста, ПерестановкаХвоста).
        		
        	генерация_гипотезы(Гипотеза):-
        		КоличествоМальчиков = 8,
        		findall(Позиция, число_в_диапазоне(1, КоличествоМальчиков, Позиция), ВозможныеПозции),
        		
        		перестановки(ВозможныеПозции, КоличествоМальчиков, ПересстановкаПозиций),
        		ПересстановкаПозиций = [А, Б, В, Г, Д, Е, К, Л],
       
        		Гипотеза = [
        			позиция_мальчика(а, А),
        			позиция_мальчика(б, Б),
        			позиция_мальчика(в, В),
        			позиция_мальчика(г, Г),
        			позиция_мальчика(д, Д),
        			позиция_мальчика(е, Е),
        			позиция_мальчика(к, К),
        			позиция_мальчика(л, Л)
        		].
        		
        	между(Х, Центр, У):-
        		Х < Центр, Центр < У;
        		Х > Центр, Центр > У.
        		
        	рядом(Х, У):-
        		Х = У + 1; Х = У - 1.
        		
        	проверка_гипотезы(Гипотеза):-
        		входит_в(позиция_мальчика(а, А), Гипотеза),
        		входит_в(позиция_мальчика(б, Б), Гипотеза),
        		входит_в(позиция_мальчика(в, В), Гипотеза),
        		входит_в(позиция_мальчика(г, Г), Гипотеза),
        		входит_в(позиция_мальчика(д, Д), Гипотеза),
        		входит_в(позиция_мальчика(е, Е), Гипотеза),
        		входит_в(позиция_мальчика(к, К), Гипотеза),
        		входит_в(позиция_мальчика(л, Л), Гипотеза),
      
        		% 1) А впереди Б и В 
        		А < Б, А < В,
        		% 2) Б впереди К через одного
        		% ...Б?К...
        		Б = К - 2,
        		% 3) Л впереди А но после Д
        		% ...Д...Л...А...
        		Л < А, Л > Д,
        		% 4) В после Е через одного
        		% ...Е?В...
        		В = Е + 2,
        		% 5) Д между Б и Г
        		% ...Б...Д...Г... или ...Г...Д...Б...
        		между(Б, Д, Г),
        		% 6) Е рядом с К, но впереди В 
        		% ...ЕК...В... или ...КЕ...В...
        		рядом(Е, К),
        		Е < В.
      GOAL   
              генерация_гипотезы(Гипотеза),
              Гипотеза = [
              	позиция_мальчика(а, А),
        		позиция_мальчика(б, Б),
        		позиция_мальчика(в, В),
        		позиция_мальчика(г, Г),
        		позиция_мальчика(д, Д),
        		позиция_мальчика(е, Е),
        		позиция_мальчика(к, К),
        		позиция_мальчика(л, Л)
        	],
        		
              проверка_гипотезы(Гипотеза).
      

      Решение 2

      DOMAINS 
      	мальчик = а;б;в;г;д;е;к;л
      	позиция = integer
      	
      	структура_гипотезы=позиция_мальчика(мальчик, позиция)
      	гипотеза = структура_гипотезы*
      	
      	позиции = позиция*
      	решение = мальчик*
      PREDICATES
             nondeterm входит_в(позиция, позиции)
             nondeterm входит_в(структура_гипотезы, гипотеза)
             nondeterm поиск_решения(решение)
             
             nondeterm выбрать_элемент(позиция, позиции, позиции)
             nondeterm перестановки(позиции, позиция, позиции)
             
             nondeterm число_в_диапазоне(позиция, позиция, позиция)     
             
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm между(позиция, позиция, позиция)
             nondeterm рядом(позиция, позиция)
             
             nondeterm позиция_больше(структура_гипотезы, структура_гипотезы)
             nondeterm переместить_максимум_в_конец(гипотеза, гипотеза)
             nondeterm сортировка_пузырьком(гипотеза, гипотеза)
            
      CLAUSES 
          	число_в_диапазоне(От, _До, От).
          	число_в_диапазоне(От, До, Число):-
          		От < До,
            		СледующееОт = От+ 1, 
            		число_в_диапазоне(СледующееОт, До, Число).
      
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      	  	входит_в(Элемент, Хвост_списка).   
      	  
      	выбрать_элемент(Элемент, [Элемент|Хвост], Хвост).
      	выбрать_элемент(Элемент, [ПервыйЭлемент|Хвост], [ПервыйЭлемент|ХвостРезультата]):-
        		выбрать_элемент(Элемент, Хвост, ХвостРезультата).
        		
        	перестановки(_Список, 0, []).
      	перестановки(Список, ДлинаПерестановки, [ПервыйЭлемент|ПерестановкаХвоста]):-
       		выбрать_элемент(ПервыйЭлемент, Список, Хвост), 
        		ДлинаПерестановкиХвоста = ДлинаПерестановки - 1,
        		перестановки(Хвост, ДлинаПерестановкиХвоста, ПерестановкаХвоста).
        		
        	генерация_гипотезы(Гипотеза):-
        		КоличествоМальчиков = 8,
        		findall(Позиция, число_в_диапазоне(1, КоличествоМальчиков, Позиция), ВозможныеПозции),
        		
        		перестановки(ВозможныеПозции, КоличествоМальчиков, ПересстановкаПозиций),
        		ПересстановкаПозиций = [А, Б, В, Г, Д, Е, К, Л],
       
        		Гипотеза = [
        			позиция_мальчика(а, А),
        			позиция_мальчика(б, Б),
        			позиция_мальчика(в, В),
        			позиция_мальчика(г, Г),
        			позиция_мальчика(д, Д),
        			позиция_мальчика(е, Е),
        			позиция_мальчика(к, К),
        			позиция_мальчика(л, Л)
        		].
        		
        	между(Х, Центр, У):-
        		Х < Центр, Центр < У;
        		Х > Центр, Центр > У.
        		
        	рядом(Х, У):-
        		Х = У + 1; Х = У - 1.
        		
        	проверка_гипотезы(Гипотеза):-
        		входит_в(позиция_мальчика(а, А), Гипотеза),
        		входит_в(позиция_мальчика(б, Б), Гипотеза),
        		входит_в(позиция_мальчика(в, В), Гипотеза),
        		входит_в(позиция_мальчика(г, Г), Гипотеза),
        		входит_в(позиция_мальчика(д, Д), Гипотеза),
        		входит_в(позиция_мальчика(е, Е), Гипотеза),
        		входит_в(позиция_мальчика(к, К), Гипотеза),
        		входит_в(позиция_мальчика(л, Л), Гипотеза),
      
        		% 1) А впереди Б и В 
        		А < Б, А < В,
        		% 2) Б впереди К через одного
        		% ...Б?К...
        		Б = К - 2,
        		% 3) Л впереди А но после Д
        		% ...Д...Л...А...
        		Л < А, Л > Д,
        		% 4) В после Е через одного
        		% ...Е?В...
        		В = Е + 2,
        		% 5) Д между Б и Г
        		% ...Б...Д...Г... или ...Г...Д...Б...
        		между(Б, Д, Г),
        		% 6) Е рядом с К, но впереди В 
        		% ...ЕК...В... или ...КЕ...В...
        		рядом(Е, К),
        		Е < В.
        		
        	позиция_больше(позиция_мальчика(_, ПозицияБольше), позиция_мальчика(_, ПозицияМеньше)):-
        		ПозицияБольше < ПозицияМеньше.
        		
      	переместить_максимум_в_конец([], []).
          	переместить_максимум_в_конец([Первый], [Первый]).
          	переместить_максимум_в_конец([Первый, Второй|Остальные], [Второй|ОстальныеСМаксимумом]):-
            		позиция_больше(Второй, Первый),
            		переместить_максимум_в_конец([Первый|Остальные], ОстальныеСМаксимумом).
          	переместить_максимум_в_конец([Первый, Второй|Остальные], [Первый|ОстальныеСМаксимумом]):-
          		NOT(позиция_больше(Второй, Первый)),
            		переместить_максимум_в_конец([Второй|Остальные], ОстальныеСМаксимумом).
            
              сортировка_пузырьком(Сортированный_список, Сортированный_список):-
            		переместить_максимум_в_конец(Сортированный_список, ДваждыСортированный),
            		Сортированный_список = ДваждыСортированный.
          	сортировка_пузырьком(Список, Сортированный_список):-
            		переместить_максимум_в_конец(Список, ЧастичноСортированный),
            		NOT(Список = ЧастичноСортированный),
            		сортировка_пузырьком(ЧастичноСортированный, Сортированный_список).
        	
        	поиск_решения(Решение):-
        		генерация_гипотезы(Гипотеза),
             	 	проверка_гипотезы(Гипотеза), 
             	 	
             	 	сортировка_пузырьком(Гипотеза, СортированнаяГипотеза),
             	 	СортированнаяГипотеза = [
              		позиция_мальчика(Мальчик1, 1),
        			позиция_мальчика(Мальчик2, 2),
        			позиция_мальчика(Мальчик3, 3),
        			позиция_мальчика(Мальчик4, 4),
        			позиция_мальчика(Мальчик5, 5),
        			позиция_мальчика(Мальчик6, 6),
        			позиция_мальчика(Мальчик7, 7),
        			позиция_мальчика(Мальчик8, 8)
        		],
        		
        		Решение = [
        			Мальчик1, Мальчик2, Мальчик3, Мальчик4, 
        			Мальчик5, Мальчик6, Мальчик7, Мальчик8
        		].
             	 	
      GOAL   
              поиск_решения(Решение).
      

      Решение 3

      DOMAINS 
      	мальчик = а;б;в;г;д;е;к;л
      	позиция = integer
      	
      	структура_гипотезы=позиция_мальчика(мальчик, позиция)
      	гипотеза = структура_гипотезы*
      	
      	позиции = позиция*
      	решение = мальчик*
      PREDICATES
             nondeterm входит_в(позиция, позиции)
             nondeterm входит_в(структура_гипотезы, гипотеза)
             nondeterm поиск_решения(решение)
           
             nondeterm возможное_имя(мальчик)
      
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm между(позиция, позиция, позиция)
             nondeterm рядом(позиция, позиция)
      CLAUSES       		
            	возможное_имя(а).
            	возможное_имя(б).
            	возможное_имя(в).
            	возможное_имя(г).
            	возможное_имя(д).
            	возможное_имя(е).
            	возможное_имя(к).
            	возможное_имя(л).
      
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      	  	входит_в(Элемент, Хвост_списка).   
      
        	генерация_гипотезы([
        		позиция_мальчика(А, 1),
        		позиция_мальчика(Б, 2),
        		позиция_мальчика(В, 3),
        		позиция_мальчика(Г, 4),
        		позиция_мальчика(Д, 5),
        		позиция_мальчика(Е, 6),
        		позиция_мальчика(К, 7),
        		позиция_мальчика(Л, 8)
        	]):-
        		возможное_имя(А), возможное_имя(Б), возможное_имя(В), 
        		возможное_имя(Г), возможное_имя(Д), возможное_имя(Е), 
        		возможное_имя(К), возможное_имя(Л), 
        		
        		NOT(А=Б), NOT(А=В), NOT(А=Г), NOT(А=Д), NOT(А=Е), NOT(А=К), NOT(А=Л),
        		NOT(Б=В), NOT(Б=Г), NOT(Б=Д), NOT(Б=Е), NOT(Б=К), NOT(Б=Л),
        		NOT(В=Г), NOT(В=Д), NOT(В=Е), NOT(В=К), NOT(В=Л),
        		NOT(Г=Д), NOT(Г=Е), NOT(Г=К), NOT(Г=Л),
        		NOT(Д=Е), NOT(Д=К), NOT(Д=Л),
        		NOT(Е=К), NOT(Е=Л),
        		NOT(К=Л).
        		
        	между(Х, Центр, У):-
        		Х < Центр, Центр < У;
        		Х > Центр, Центр > У.
        		
        	рядом(Х, У):-
        		Х = У + 1; Х = У - 1.
        		
        	проверка_гипотезы(Гипотеза):-
        		входит_в(позиция_мальчика(а, А), Гипотеза),
        		входит_в(позиция_мальчика(б, Б), Гипотеза),
        		входит_в(позиция_мальчика(в, В), Гипотеза),
        		входит_в(позиция_мальчика(г, Г), Гипотеза),
        		входит_в(позиция_мальчика(д, Д), Гипотеза),
        		входит_в(позиция_мальчика(е, Е), Гипотеза),
        		входит_в(позиция_мальчика(к, К), Гипотеза),
        		входит_в(позиция_мальчика(л, Л), Гипотеза),
      
        		% 1) А впереди Б и В 
        		А < Б, А < В,
        		% 2) Б впереди К через одного
        		% ...Б?К...
        		Б = К - 2,
        		% 3) Л впереди А но после Д
        		% ...Д...Л...А...
        		Л < А, Л > Д,
        		% 4) В после Е через одного
        		% ...Е?В...
        		В = Е + 2,
        		% 5) Д между Б и Г
        		% ...Б...Д...Г... или ...Г...Д...Б...
        		между(Б, Д, Г),
        		% 6) Е рядом с К, но впереди В 
        		% ...ЕК...В... или ...КЕ...В...
        		рядом(Е, К),
        		Е < В.
      
        	поиск_решения(Решение):-
        		генерация_гипотезы(Гипотеза),
             	 	проверка_гипотезы(Гипотеза), 
             	 	
             	 	Гипотеза = [
              		позиция_мальчика(Мальчик1, 1),
        			позиция_мальчика(Мальчик2, 2),
        			позиция_мальчика(Мальчик3, 3),
        			позиция_мальчика(Мальчик4, 4),
        			позиция_мальчика(Мальчик5, 5),
        			позиция_мальчика(Мальчик6, 6),
        			позиция_мальчика(Мальчик7, 7),
        			позиция_мальчика(Мальчик8, 8)
        		],
        		
        		Решение = [
        			Мальчик1, Мальчик2, Мальчик3, Мальчик4, 
        			Мальчик5, Мальчик6, Мальчик7, Мальчик8
        		].
             	 	
      GOAL   
              поиск_решения(Решение).
      

      Решение 4

      DOMAINS 
      	имя = а;б;в;г;д;е;к;л
      	структура_гипотезы=мальчик(имя, integer)
      	гипотеза = структура_гипотезы*
      	номера = integer*
      	имена = имя*
      CONSTANTS
      	все_имена = [а,б,в,г,д,е,к,л]
      	все_номера = [1,2,3,4,5,6,7,8]
      PREDICATES
             nondeterm входит_в(integer, номера)
             nondeterm входит_в(имя, имена)
             nondeterm входит_в(структура_гипотезы, гипотеза)
             
             nondeterm без_повторов(имена)
            
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm между(integer, integer, integer)
             nondeterm рядом(integer, integer)
             nondeterm впереди(integer, integer)
             
             nondeterm поиск_решения(имена)
      CLAUSES       		
      	входит_в(Элемент, [Элемент|_]).
      	входит_в(Элемент, [_|Хвост_списка]):-
      	  	входит_в(Элемент, Хвост_списка).   
      	  	
      	без_повторов([]).
          	без_повторов([Первый|Остальные]):-
            		NOT(входит_в(Первый, Остальные)),
            		без_повторов(Остальные).
      
        	генерация_гипотезы(Гипотеза):-
        		входит_в(Мальчик1, все_имена), входит_в(Мальчик2, все_имена),
        		входит_в(Мальчик3, все_имена), входит_в(Мальчик4, все_имена),
        		входит_в(Мальчик5, все_имена), входит_в(Мальчик6, все_имена),
        		входит_в(Мальчик7, все_имена), входит_в(Мальчик8, все_имена),
        		
        		без_повторов([Мальчик1, Мальчик2, Мальчик3, Мальчик4,
        					    Мальчик5, Мальчик6, Мальчик7, Мальчик8]),
        		
        		Гипотеза = [
        			мальчик(Мальчик1, 1), мальчик(Мальчик2, 2), мальчик(Мальчик3, 3),
        			мальчик(Мальчик4, 4), мальчик(Мальчик5, 5), мальчик(Мальчик6, 6),
        			мальчик(Мальчик7, 7), мальчик(Мальчик8, 8)
        		].
        		
        	между(Х, Кто , У):-
        		впереди(Х, Кто), впереди(Кто, У);
        		впереди(У, Кто), впереди(Кто, Х).
        		
        	рядом(Х, У):-
        		Х = У + 1; Х = У - 1.
        		
        	впереди(Х, У):-
        		Х < У.
        		
        	проверка_гипотезы(Гипотеза):-
        		входит_в(мальчик(а, А), Гипотеза),
        		входит_в(мальчик(б, Б), Гипотеза),
        		входит_в(мальчик(в, В), Гипотеза),
        		входит_в(мальчик(г, Г), Гипотеза),
        		входит_в(мальчик(д, Д), Гипотеза),
        		входит_в(мальчик(е, Е), Гипотеза),
        		входит_в(мальчик(к, К), Гипотеза),
        		входит_в(мальчик(л, Л), Гипотеза),
      
        		% А был впереди Б и В;
        		впереди(А, Б), впереди(А, В),
        		% 2) Б – впереди К через одного;
        		Б = К - 2,
        		% 3) Л – впереди А, но после Д;
        		впереди(Л, А), впереди(Д, А),
        		% 4) В – после Е через одного;
        		В = Е + 2,
        		% 5) Д – между Б и Г;
        		между(Б, Д, Г),
        		% 6) Е – рядом с К, но впереди В.
        		рядом(Е, К),
        		впереди(Е, В).
      
        	поиск_решения(Решение):-
        		генерация_гипотезы(Гипотеза),
             	 	проверка_гипотезы(Гипотеза), 
             	 	
             	 	Гипотеза = [
        			мальчик(Мальчик1, 1), мальчик(Мальчик2, 2), мальчик(Мальчик3, 3),
        			мальчик(Мальчик4, 4), мальчик(Мальчик5, 5), мальчик(Мальчик6, 6),
        			мальчик(Мальчик7, 7), мальчик(Мальчик8, 8)
        		],
        		
        		Решение = [
        			Мальчик1, Мальчик2, Мальчик3, Мальчик4, 
        			Мальчик5, Мальчик6, Мальчик7, Мальчик8
        		].
      GOAL   
              поиск_решения(Решение).
      

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×