Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Циклич. сдвиг списка.
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
F@ntom F@ntom вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.10.2005
По умолчанию Циклич. сдвиг списка. - 04.10.2005, 01:55

Помогите плиз доделать прогу :
Создание списка, в который занесены все неповторяющиеся списки, являющиеся циклическими сдвигами заданного влево на заданное количество элементов, не включая заданный список.
• исходный список, количество элементов;
• результирующий список.

Вот почти доделанная:

Код:
cyc(List,P,Res):-cyc(List,P,[],[]).
cyc(List,P,Res,[]):- cycleL(List,P,M), addlast(M,Res,Res1), cyc(M,P,Res1,[]).
cycleL([],_,[]).
cycleL(List,0,List).
cycleL([H|T],K,List):-
   addlast(H,T,N),  
   K1 is K-1,
   cycleL(N,K1,List). 

addlast(Z,[],[Z]).
addlast(Z,[A|X],[A|R]):-addlast(Z,X,R).
Не знаю как проверить, что список уже готов и его вывести.
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 04.10.2005, 11:20

Думаю, что Вам поможет эта ссылка:
http://www.hardforum.ru/t49469
Ответить с цитированием
  (#3 (permalink)) Старый
F@ntom F@ntom вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.10.2005
По умолчанию 04.10.2005, 15:04

Мне эта ссылка помогла, но не до конца
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 05.10.2005, 21:27

Цитата:
Вот почти доделанная:
Не "почти доделанная", а совсем недоделанная.
Насколько я поняла задачку, можно сделать так:
Код:
domains
il=integer*
ill=il*
predicates
решение(il,integer,ill)
цикл_сдвиги(il,integer,integer,integer,ill)
длина(il,integer,integer)
нод(integer,integer,integer)
цикл_сдвиг(il,integer,integer,il)
разделить(il,integer,il,il)
соединить(il,il,il)
goal
L=[1,2,3,4,5],K=2,решение(L,K,ЦиклСдвиги).
clauses
решение(L,K,ЦиклСдвиги):- 
    длина(L,0,N),
    нод(N,K,НОД),
    M=N div НОД,
    цикл_сдвиги(L,N,M,K,ЦиклСдвиги).

цикл_сдвиги(L,N,C,K,[L1|LL]):- C>0,цикл_сдвиг(L,N,K,L1),
    C1=C-1,!,цикл_сдвиги(L1,N,C1,K,LL).
цикл_сдвиги(_,_,_,_,[]).
    
цикл_сдвиг(L,N,N,L):- !.
цикл_сдвиг(L,N,K,Сдвиг):- K<N,!,M=N-K,
    разделить(L,M,Префикс,Постфикс),
    соединить(Постфикс,Префикс,Сдвиг).
цикл_сдвиг(L,N,K,Сдвиг):- M=K mod N,цикл_сдвиг(L,N,M,Сдвиг).
    
разделить([A|L],M,[A|L1],L2):- 
    M>0,M1=M-1,!,
    разделить(L,M1,L1,L2).
разделить(L,0,[],L).

соединить([A|L1],L2,[A|L]):- соединить(L1,L2,L).
соединить([],L,L).

нод(А,Б,Б):- А mod Б=0,!.
нод(А,Б,НОД):- А mod Б=В,нод(Б,В,НОД).

длина([_|L],C,Д):- C1=C+1,длина(L,C1,Д).
длина([],Д,Д).
Результат:
Код:
L=[1,2,3,4,5], K=2, ЦиклСдвиги=[[4,5,1,2,3],[2,3,4,5,1],[5,1,2,3,4],[3,4,5,1,2],[1,2,3,4,5]]
1 Solution
Если Вам не нужен в ответе исходный список, который всегда получается на последнем шаге, то замените в коде для предиката цикл_сдвиги выражение C>0 на выражение C>1.
Количество шагов равно N / НОД, где N - длина списка, а НОД - это наибольший общий делитель N и величины сдвига.
Ответить с цитированием
  (#5 (permalink)) Старый
F@ntom F@ntom вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.10.2005
По умолчанию 06.10.2005, 10:19

Cпвсибо большое, Alison, все работает. С НОД - хорошая идея
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 06.10.2005, 12:34

С НОД - идея хорошая, но можно сделать и без НОД. Просто сравнивать, совпадает ли очередной сдвиг с исходным списком и, если да, то останавливаться.
Ответить с цитированием
Ads
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Позиция элемента и сдвиг в списке glyc Lisp 14 19.11.2015 19:04
сдвиг изображения zffni Любые вопросы от новичков 11 29.01.2012 17:43
циклический сдвиг вправо на n єлементов. Darya17 Prolog 1 15.12.2011 22:17
Сдвиг списка kasperr Prolog 4 25.11.2011 17:12
осуществить сдвиг Стася Pascal 2 11.05.2011 23:57
Циклический сдвиг списка(просьба объяснить) dllxllb Prolog 1 21.10.2010 23:28
циклический сдвиг элементов списка denis120 Prolog 2 03.05.2010 15:30
Побитовый сдвиг как его реализовать imported_bio С/С++ 5 12.05.2009 10:55
Быстрый сдвиг на асме Rocky Вопросы начинающих программистов 10 02.12.2008 23:21
Массивы и указатели циклический сдвиг insi С/С++ 7 06.06.2008 11:34
Что такое побитовый сдвиг tota С/С++ 12 04.02.2007 10:32
Сдвиг объектов InlineShapes над строкой _aleksey_ Visual Basic 0 05.08.2006 11:09



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