1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
class PYRAMID
--
-- Solving the problem of the Pyramid for small pyramid only.
--
-- This program uses the back-tracking method.
-- Its goal is to try to fill a pyramid by making a substraction
-- between two succesive columns and to take its absolute value.
-- The result is put on the next line.
-- Example:
-- 6 14 15 3 13
-- 8 1 12 10
-- 7 11 2
-- 4 9
-- 5
--
-- See also pyramid2, which run faster than this first solution.
inherit ANY redefine out_in_tagged_out_memory end;
creation make
feature
size: INTEGER;
make is
do
if argument_count = 0 then
std_output.put_string("Want to compute a small pyramid ?%N%
%Enter a small number (> 1): ");
std_output.flush;
std_input.read_integer;
size := std_input.last_integer;
else
size := argument(1).to_integer;
end;
if size <= 1 then
std_output.put_string("You feel sick ?%N");
elseif size > biggest_one then
std_output.put_string("Value too big for this method.%N");
else
!!elem.make(1,max);
if fill_up(1) then
std_output.put_string("Full pyramid:%N");
print_on(std_output);
else
std_output.put_string("Unable to fill_up such one.%N");
end;
end;
end;
max: INTEGER is
do
Result := (size * (size + 1)) // 2;
end;
out_in_tagged_out_memory is
local
lig,col,nb: INTEGER;
do
from
lig := 1;
col := 1;
nb := 0;
until
nb = max
loop
if col = 1 then
tagged_out_memory.extend('%N');
end;
(elem.item(indice(lig,col))).append_in(tagged_out_memory);
tagged_out_memory.append(" ");
if col = size - lig + 1 then
col := 1 ;
lig := lig + 1 ;
else
col := col + 1;
end;
nb := nb + 1;
end;
tagged_out_memory.extend('%N');
end;
belongs_to(nb: INTEGER): BOOLEAN is
require
too_small: nb >= 1;
too_large: nb <= max
local
i: INTEGER;
found: BOOLEAN;
do
from
i := 1;
until
((i > max) or found)
loop
found := (nb = elem.item(i));
i := i + 1;
end;
Result := found;
end;
propagate (col, val_column_1: INTEGER): BOOLEAN is
require
val_column_1.in_range(1,max);
col.in_range(1,size)
local
stop: BOOLEAN;
lig: INTEGER;
val: INTEGER;
do
if belongs_to(val_column_1) then
Result := false ;
else
from
elem.put(val_column_1,indice(1,col));
lig := 1;
val := val_column_1;
stop := false;
Result := true;
until
stop
loop
lig := lig + 1;
if lig > col then
stop := true;
else
val := val - elem.item(indice(lig-1,col-lig+1));
val := val.abs;
if belongs_to(val) then
clear_column(col);
stop := true;
Result := false;
else
elem.put(val,indice(lig,col-lig+1));
end;
end;
end;
end;
end;
fill_up (col: INTEGER): BOOLEAN is
require
col >= 1;
local
stop: BOOLEAN;
nb: INTEGER;
do
if col > size then
Result := true;
else
from
stop := false;
nb := max;
until
stop
loop
if belongs_to(nb) then
nb := nb - 1;
stop := (nb = 0);
elseif propagate(col,nb) then
if fill_up(col + 1) then
stop := true;
else
clear_column(col);
nb := nb - 1;
stop := (nb = 0);
end;
else
nb := nb - 1;
stop := (nb = 0);
end;
end;
Result := (nb > 0);
end;
end;
feature {NONE}
elem: ARRAY[INTEGER];
case_vide: INTEGER is 0;
biggest_one: INTEGER is 10;
indice (lig,col: INTEGER): INTEGER is
require
lig_trop_petit: lig >= 1 ;
lig_trop_grand: lig <= size ;
col_trop_petit: col >= 1 ;
col_trop_grand: col <= size ;
local
l: INTEGER ;
do
l:= size - lig + 1;
Result := max - ((l * (l + 1)) // 2) + col;
ensure
Result >= 1 ;
Result <= max ;
end;
clear_column (col: INTEGER) is
require
col >= 1;
col <= size;
local
lig: INTEGER;
do
from
lig := 1;
until
lig > col
loop
elem.put(case_vide,indice(lig,col-lig+1));
lig := lig + 1;
end;
end; -- clear_column
end -- PYRAMID
|
