fork download
copy 
  1. :- use_module(library(lists)).
  2.  
  3. % ----------------------------
  4. % задание 1: шелл (седжвик)
  5. % ----------------------------
  6.  
  7. % shs(+l, -s, -other_list)
  8. shs(L, S, OtherList) :-
  9.     length(L, N),
  10.     sg(N, Gs),
  11.     sp(Gs, L, S),
  12.     generate_other_list(N, OtherList).  % Создаем SomeOtherList
  13.  
  14. % sg(+n, -gs)
  15. sg(N, Gs) :-
  16.     ( N =< 1 -> Gs = [1]
  17.     ; sgk(N, 0, [], Rs),
  18.       reverse(Rs, Gs)
  19.     ).
  20.  
  21. sgk(N, K, A, Rs) :-
  22.     hk(K, H),
  23.     K1 is K + 1,
  24.     hk(K1, H1),
  25.     ( 3*H1 > N ->
  26.         Rs = [H|A]
  27.     ;   sgk(N, K1, [H|A], Rs)
  28.     ).
  29.  
  30. % hk(+k,-h)
  31. hk(K, H) :-
  32.     ( 0 is K mod 2 ->
  33.         P2k  is 1 << K,
  34.         K2   is K // 2,
  35.         P2k2 is 1 << K2,
  36.         H is 9*P2k - 9*P2k2 + 1
  37.     ;   P2k  is 1 << K,
  38.         K2   is (K + 1) // 2,
  39.         P2k2 is 1 << K2,
  40.         H is 8*P2k - 6*P2k2 + 1
  41.     ).
  42.  
  43. sp([], L, L).
  44. sp([G|Gs], L, S) :-
  45.     gp(G, L, L1),
  46.     sp(Gs, L1, S).
  47.  
  48. % gp(+g,+l,-s)
  49. gp(G, L, S) :-
  50.     en(L, 0, Ps),
  51.     G1 is G - 1,
  52.     findall(Ns, (between(0, G1, R), cls(Ps, G, R, Ns)), Bs),
  53.     append(Bs, All),
  54.     keysort(All, Ss),
  55.     vs(Ss, S).
  56.  
  57. cls(Ps, G, R, Ns) :-
  58.     include(pr(G, R), Ps, Cs),
  59.     iv(Cs, Vs1, Is1),
  60.     ins(Vs1, Vs2),
  61.     pi(Is1, Vs2, Ns).
  62.  
  63. pr(G, R, I-_) :- 0 is (I - R) mod G.
  64.  
  65. en([], _, []).
  66. en([X|Xs], I, [I-X|Ps]) :-
  67.     I1 is I + 1,
  68.     en(Xs, I1, Ps).
  69.  
  70. iv([], [], []).
  71. iv([I-V|T], [V|Vs], [I|Is]) :- iv(T, Vs, Is).
  72.  
  73. pi([], [], []).
  74. pi([I|Is], [V|Vs], [I-V|T]) :- pi(Is, Vs, T).
  75.  
  76. vs([], []).
  77. vs([_-V|T], [V|Vs]) :- vs(T, Vs).
  78.  
  79. % ins(+l,-s)
  80. ins([], []).
  81. ins([X|Xs], S) :- ins(Xs, S1), is1(X, S1, S).
  82.  
  83. is1(X, [], [X]).
  84. is1(X, [Y|Ys], [X,Y|Ys]) :- X =< Y, !.
  85. is1(X, [Y|Ys], [Y|Zs]) :- is1(X, Ys, Zs).
  86.  
  87. % Оценка сложности сортировки Шелла (Sedgewick's sequence): O(N^(4/3)) в среднем, до O(N^(3/2))  в худшем случае
  88. shellsort_complexity(N, Complexity) :-
  89.     Complexity is N**(4/3).  % Средняя сложность
  90.  
  91. % Пример использования сортировки Шелла
  92. ex_shs :-
  93.     L = [3, 1, 4, 1, 5, 9, 2, 6, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
  94.     shs(L, S, OtherList),
  95.     length(L, N),
  96.     shellsort_complexity(N, Complexity),
  97.     format('Сортировка Шелла:~n'),
  98.     format('  Исходный список: ~w~n', [L]),
  99.     format('  Отсортированный список: ~w~n', [S]),
  100.     format('  Другой список: ~w~n', [OtherList]), % Выводим второй список
  101.     format('  Оценка сложности (O(N^(4/3))): ~w для N = ~w~n', [Complexity, N]).
  102.  
  103.  
  104. % ----------------------------
  105. % задание 2: бинарные включения
  106. % ----------------------------
  107.  
  108. % bis(+l,-s, -other_list)
  109. bis(L, S, OtherList) :- bis1(L, [], S), generate_other_list(N, OtherList), length(L, N).
  110.  
  111. bis1([], A, A).
  112. bis1([X|Xs], A, S) :-
  113.     bin_ins(X, A, A1),
  114.     bis1(Xs, A1, S).
  115.  
  116. % bin_ins(+x,+l,-r)
  117. bin_ins(X, L, R) :-
  118.     length(L, N),
  119.     bin_pos(X, L, 0, N, P),
  120.     sp2(P, L, A, B),
  121.     append(A, [X|B], R).
  122.  
  123. % bin_pos(+x,+l,+lo,+hi,-p)
  124. bin_pos(X, L, Lo, Hi, P) :-
  125.     ( Lo >= Hi ->
  126.         P = Lo
  127.     ; M is (Lo + Hi) // 2,
  128.       nth0(M, L, V),
  129.       ( X =< V ->
  130.           bin_pos(X, L, Lo, M, P)
  131.       ; M1 is M + 1,
  132.         bin_pos(X, L, M1, Hi, P)
  133.       )
  134.     ).
  135.  
  136. % sp2(+k,+l,-a,-b)
  137. sp2(0, L, [], L) :- !.
  138. sp2(K, [X|Xs], [X|A], B) :-
  139.     K > 0,
  140.     K1 is K - 1,
  141.     sp2(K1, Xs, A, B).
  142.  
  143. % Оценка сложности бинарной вставки: O(N^2) в худшем случае
  144. binary_insertion_complexity(N, Complexity) :-
  145.     Complexity is N*N.  % Или N * log(N) для среднего случая
  146.  
  147. % Пример использования бинарных включений
  148. ex_bis :-
  149.     L = [3, 1, 4, 1, 5, 9, 2, 6, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
  150.     bis(L, S, OtherList),
  151.     length(L, N),
  152.     binary_insertion_complexity(N, Complexity),
  153.     format('Бинарные включения:~n'),
  154.     format('  Исходный список: ~w~n', [L]),
  155.     format('  Отсортированный список: ~w~n', [S]),
  156.     format('  Другой список: ~w~n', [OtherList]),  % выводим второй список
  157.     format('  Оценка сложности (O(N^2)): ~w для N = ~w~n', [Complexity, N]).
  158.  
  159. % ----------------------------
  160. % задание 3: "слово из домино" (игра)
  161. % ----------------------------
  162.  
  163. % igra(-w)
  164. igra(w(I, G, R, A)) :-
  165.     ds(Ts),
  166.     gr(Ts, 7, 42, Ti, T1), ch(Ti, I),
  167.     gr(T1, 7, 42, Tg, T2), ch(Tg, G),
  168.     gr(T2, 7, 42, Tr, T3), ch(Tr, R),
  169.     T3 = Ta, sm(Ta, 42), ch(Ta, A).
  170.  
  171. % ds(-ts)
  172. ds(Ts) :- findall(A-B, (between(0,6,A), between(A,6,B)), Ts).
  173.  
  174. % sm(+ts,-s)
  175. sm([], 0).
  176. sm([A-B|T], S) :-
  177.     sm(T, S1),
  178.     S is S1 + A + B.
  179.  
  180. % gr(+ts,+k,+s,-g,-r)
  181. gr(Ts, 0, 0, [], Ts) :- !.
  182. gr(Ts, K, S, [X|G], R) :-
  183.     K > 0, S >= 0,
  184.     select(X, Ts, T1),
  185.     X = A-B,
  186.     S1 is S - (A + B),
  187.     K1 is K - 1,
  188.     gr(T1, K1, S1, G, R).
  189.  
  190. % ch(+ts,-c)
  191. ch(Ts, C) :-
  192.     select(T, Ts, R),
  193.     or(T, A-B),
  194.     ch1(R, B, [A-B], C).
  195.  
  196. ch1([], _, A, C) :- reverse(A, C).
  197. ch1(Ts, X, A, C) :-
  198.     select(T, Ts, R),
  199.     or1(T, X-Y),
  200.     ch1(R, Y, [X-Y|A], C).
  201.  
  202. or(A-B, A-B).
  203. or(A-B, B-A).
  204.  
  205. or1(A-B, X-Y) :- (X=A, Y=B ; X=B, Y=A).
  206.  
  207. % Пример использования игры в домино
  208. ex_igra :-
  209.     igra(W),
  210.     format('Игра "Слово из домино":~n'),
  211.     format('  Решение: ~w~n', [W]).
  212.  
  213. % ----------------------------
  214. % задание 4 (вариант 2): вставка подсписка с i-го элемента
  215. % ----------------------------
  216.  
  217. % ins_sub(+sub,+l,+i,-r)
  218. ins_sub(Sub, L, I, R) :-
  219.     I >= 1,
  220.     K is I - 1,
  221.     sp2(K, L, P, S),
  222.     append(P, Sub, T),
  223.     append(T, S, R).
  224.  
  225. % Пример использования вставки подсписка
  226. ex_ins_sub :-
  227.     Sub = [7, 8, 9],
  228.     L = [1, 2, 3, 4, 5, 6],
  229.     I = 3,
  230.     ins_sub(Sub, L, I, R),
  231.     format('Вставка подсписка:~n'),
  232.     format('  Исходный список: ~w~n', [L]),
  233.     format('  Подсписок: ~w~n', [Sub]),
  234.     format('  Индекс вставки: ~w~n', [I]),
  235.     format('  Результат: ~w~n', [R]).
  236.  
  237. % Вспомогательное правило для генерации второго списка
  238. generate_other_list(N, OtherList) :-
  239.   findall(X, (between(1, N, I), X is I * 3), OtherList). % Другой список кратный трем
  240.  
  241. % Запуск всех примеров
  242. run_examples :-
  243.     ex_shs,
  244.     ex_bis,
  245.     ex_igra,
  246.     ex_ins_sub.
  247.  
  248.     ?- run_examples.
Success #stdin #stdout #stderr 0.05s 7336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сортировка Шелла:
  Исходный список: [3,1,4,1,5,9,2,6,10,11,12,13,14,15,16,17,18,19,20,21]
  Отсортированный список: [1,1,2,3,4,5,6,9,10,11,12,13,14,15,16,17,18,19,20,21]
  Другой список: [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60]
  Оценка сложности (O(N^(4/3))): 54.28835233189812 для N = 20
stderr
copy 
ERROR: /home/Ou4xYW/prog:248:
	between/3: Arguments are not sufficiently instantiated
Warning: /home/Ou4xYW/prog:248:
	Goal (directive) failed: user:run_examples
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/sVFxgX
language:
Prolog (swi 7.6.4)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!