Учитывая, что 8 букв можно переставить примерно 40 тысячами можно просто запустить поиск в ширину, сохранить для всех перестановок то, из какой строчки они получились, и потом восстановить ответ для строчки abcdefgh.
while not to_process.empty(): s, prev = to_process.get() if s in prec: continue for i in range(7): for j in range(i + 1, 8): if i == 0: next_s = s[j::-1] + s[j+1:] else: next_s = s[:i] + s[j:i-1:-1] + s[j+1:] if next_s not in prec: to_process.put((next_s, s)) prec[s] = prev
current = "abcdefgh" print(current) while prec[current] is not None: current = prec[current] print(current)
1)
var
s : real;
i, n : integer;
begin
s := 0;
read (n);
for i := 1 to n do s := s + 1 / i;
writeln (s);
end.
2)
var
a, i : integer;
begin
a := 1;
for i := 1 to 8 do
begin
a := a * 2;
writeln ('Через ', i * 3, 'часов будет ', a, ' амеб');
end;
end.
3)
var
n, i : integer;
x, s : real;
begin
s := 0;
read (n, x);
for i := 1 to n do
s := s + sin (i * x);
writeln (s);
end.
4)
var
n, a, r, i : integer;
begin
r := 1;
read (a, n);
for i := 1 to n do r := r * a;
writeln (r);
end.
Код на python 3:
from queue import Queue
to_process = Queue()
to_process.put(("edghcbfa", None))
prec = {}
while not to_process.empty():
s, prev = to_process.get()
if s in prec:
continue
for i in range(7):
for j in range(i + 1, 8):
if i == 0:
next_s = s[j::-1] + s[j+1:]
else:
next_s = s[:i] + s[j:i-1:-1] + s[j+1:]
if next_s not in prec:
to_process.put((next_s, s))
prec[s] = prev
current = "abcdefgh"
print(current)
while prec[current] is not None:
current = prec[current]
print(current)
Вывод программы:
abcdefgh
edcbafgh
edcbhgfa
edbchgfa
edghcbfa
Соответственно, ответ такой:
G B
B C
H A
E A