fork download
copy 
  1.  
  2.  
  3. :- use_module(library(lists)).
  4.  
  5. % ----------------------------
  6. % задание 1: шелл (седжвик)
  7. % ----------------------------
  8.  
  9. % shs(+l, -s)
  10. shs(L, S) :-
  11.     length(L, N),
  12.     sg(N, Gs),
  13.     sp(Gs, L, S).
  14.  
  15. % sg(+n, -gs)
  16. sg(N, Gs) :-
  17.     ( N =< 1 -> Gs = [1]
  18.     ; sgk(N, 0, [], Rs),
  19.       reverse(Rs, Gs)
  20.     ).
  21.  
  22. sgk(N, K, A, Rs) :-
  23.     hk(K, H),
  24.     K1 is K + 1,
  25.     hk(K1, H1),
  26.     ( 3*H1 > N ->
  27.         Rs = [H|A]
  28.     ;   sgk(N, K1, [H|A], Rs)
  29.     ).
  30.  
  31. % hk(+k,-h)
  32. hk(K, H) :-
  33.     ( 0 is K mod 2 ->
  34.         P2k  is 1 << K,
  35.         K2   is K // 2,
  36.         P2k2 is 1 << K2,
  37.         H is 9*P2k - 9*P2k2 + 1
  38.     ;   P2k  is 1 << K,
  39.         K2   is (K + 1) // 2,
  40.         P2k2 is 1 << K2,
  41.         H is 8*P2k - 6*P2k2 + 1
  42.     ).
  43.  
  44. sp([], L, L).
  45. sp([G|Gs], L, S) :-
  46.     gp(G, L, L1),
  47.     sp(Gs, L1, S).
  48.  
  49. % gp(+g,+l,-s)
  50. gp(G, L, S) :-
  51.     en(L, 0, Ps),
  52.     G1 is G - 1,
  53.     findall(Ns, (between(0, G1, R), cls(Ps, G, R, Ns)), Bs),
  54.     append(Bs, All),
  55.     keysort(All, Ss),
  56.     vs(Ss, S).
  57.  
  58. cls(Ps, G, R, Ns) :-
  59.     include(pr(G, R), Ps, Cs),
  60.     iv(Cs, Vs1, Is1),
  61.     ins(Vs1, Vs2),
  62.     pi(Is1, Vs2, Ns).
  63.  
  64. pr(G, R, I-_) :- 0 is (I - R) mod G.
  65.  
  66. en([], _, []).
  67. en([X|Xs], I, [I-X|Ps]) :-
  68.     I1 is I + 1,
  69.     en(Xs, I1, Ps).
  70.  
  71. iv([], [], []).
  72. iv([I-V|T], [V|Vs], [I|Is]) :- iv(T, Vs, Is).
  73.  
  74. pi([], [], []).
  75. pi([I|Is], [V|Vs], [I-V|T]) :- pi(Is, Vs, T).
  76.  
  77. vs([], []).
  78. vs([_-V|T], [V|Vs]) :- vs(T, Vs).
  79.  
  80. % ins(+l,-s)
  81. ins([], []).
  82. ins([X|Xs], S) :- ins(Xs, S1), is1(X, S1, S).
  83.  
  84. is1(X, [], [X]).
  85. is1(X, [Y|Ys], [X,Y|Ys]) :- X =< Y, !.
  86. is1(X, [Y|Ys], [Y|Zs]) :- is1(X, Ys, Zs).
  87.  
  88. % Пример использования сортировки Шелла
  89. ex_shs :-
  90.     L = [3, 1, 4, 1, 5, 9, 2, 6],
  91.     shs(L, S),
  92.     format('Сортировка Шелла:~n'),
  93.     format('  Исходный список: ~w~n', [L]),
  94.     format('  Отсортированный список: ~w~n', [S]).
  95.  
  96.     run_examples :-
  97.     ex_shs.
  98.  
  99. ?- run_examples.
  100.  
Success #stdin #stdout #stderr 0.05s 7048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сортировка Шелла:
  Исходный список: [3,1,4,1,5,9,2,6]
  Отсортированный список: [1,1,2,3,4,5,6,9]
stderr
copy 
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/4WNB7A
language:
Prolog (swi 7.6.4)
created:
7 hours 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!