Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Интересная задача на рекурсию
Автор: striker 1.03.2007 2:24
Нужна помощь в решении этой задачи:
Нужно записать с использованием рекурсии программу создания n-символьной последовательности, состоящей из совокупности трех символов (например: 0,1,2 или a,b,c), в которой нет двух смежных идентичных подпоследовательностей, например, послед-ти 2011 и 21012101 не удовлетворяют условию задачи, т.к. в первой рядом расположены два одинаковых элемента 1, а во второй – одинаковые подпоследовательности 2101.
Интересная только как тут задать условие повторения подпоследовательностей?
Предлагайте свои варианты решения.
Автор: volvo 1.03.2007 2:38
const
{ s: string = '21012101'; }
s: string = '2011';
var
i, p: integer;
ok: boolean;
begin
ok := true;
for i := length(s) div 2 downto 1 do begin
for p := 1 to length(s) - 2 * i + 1 do
ok := ok and (copy(s, p, i) <> copy(s, p+i, i));
end;
writeln(ok);
end.
с небольшими усовершенствованиями (для ускорения работы) применять для каждой сгенерированной последовательности... Разберешься?
Автор: striker 1.03.2007 23:25
Если честно, не очень понял.
Это только для последовательности, состоящей из 0,1,2
или для всех?
Или только для 2011???
Если не трудно объясни.
Автор: volvo 1.03.2007 23:35
Ты спросил, как определять существует ли повторяющаяся ПОДпоследовательность в заданной последовательности? Я тебе показал... Генерация всех возможных последовательностей, состоящих из заданного набора символов, уже рассматривалась на форуме, ищи в Поиске...
Теперь о вызове того алгоритма, что я написал: оформи его в виде функции:
function os_ok(s: string): boolean;
begin
{ Тут - описанные выше действия }
end;
Как только сгенерировал очередную последовательность - передавай ее в функцию, и если функция вернула True - значит, последовательность НЕ содержит 2-х рядом стоящих ПОДпоследовательностей ...
Автор: striker 2.03.2007 23:58
1. Получается, что проверяется только повторение заданных подпоследовательностей (например в твоем
решении - 2101 и 2011)
Нужно проверить все повторения.
2. Как генерировать n-символьную последовательность? Я могу, например, сделать
последовательность,кратную 3,4,...
На форуме не нашел, а сам не допираю.
Подскажи, если не трудно.
Автор: volvo 3.03.2007 0:15
striker, ты внимательно прочел, что я написал? Программу запустил? Попробовал менять исходные данные? Повторяю еще раз (больше повторять не буду): то, что я привел - проверяет, присутствуют ЛИ в переданной функции строке ЛЮБЫЕ 2 подпоследовательности, идущие ПОДРЯД одна за другой!!! Что ты в эту функцию будешь передавать - ее не касается! Передашь '1234567891234567890' - получишь False, потому, что эта строка СОДЕРЖИТ 2 раза подряд '123456789'. Все, больше повторять не буду.
Автор: striker 11.03.2007 0:58
Нет, я делаю последовательности, но не состоящие из определенных символов.
Вот
uses crt;
var i,j,k,l,a : longint;
m,n : integer;
begin
clrscr;
write('Kol-vo chisel ');readln(n);
m:=0;
for j:=1 to 9 do
for k:=0 to 9 do
for l:=0 to 9 do
if (j<>k)and(j<>l)and(k<>l)and(m<=n)then
begin
a:=100*j+k*10+l;
write(a);m:=m+1;
end;
readln;
end.
Помоги пожалуйста.
Я никак не разберусь.
Автор: volvo 11.03.2007 1:04
Во-вторых, какой длины может быть последовательность? 6 символов? 7? 20? 120? чем больше будет это число, тем меньше у тебя шансов дождаться окончания работы программы, и тем большее значение приобретает оптимизация. Поэтому уточни, какое максимальное N может быть, потом я покажу, что надо делать...
Добавлено через 13 мин.
В частности, при N = 4 вполне возможно вот такое, например, решение:
const, программа отработает практически мгновенно... Однако при N = 22 эта программа будет работать уже больше 2-х секунд...
n = 4;
chars: string = 'abc';
function check(s: string): boolean;
var
i, p: integer;
ok: boolean;
begin
ok := true;
for i := length(s) div 2 downto 1 do begin
for p := 1 to length(s) - 2 * i + 1 do
ok := ok and (copy(s, p, i) <> copy(s, p+i, i));
end;
check := ok;
end;
procedure generate(s: string);
var i: integer;
begin
if length(s) = n then begin
if check(s) then writeln(s)
end
else
if check(s) then
for i := 1 to length(chars) do generate(s + chars[i])
end;
begin
generate('');
end.
Автор: striker 11.03.2007 22:18
Как вывести полученную послед-ть на экран?
Или она уже так быстро выводится?
Автор: volvo 11.03.2007 22:57
А запустить программу не пробовал??? В общем, я смотрю, чем больше помогаешь, тем больше садятся на шею... Все, я больше в эту тему не хожу - надоело мне одно и то же пережевывать десятый раз!
Автор: Michael_Rybak 12.03.2007 7:44
Жестко.
В общем, это ханойские башни. Между каждыми двумя столбиками на каждом шагу можно совершить только одну операцию (для столбиков А и В можно переложить с А на В, если верхний диск на А меньше, чем на В, и с В на А в противном случае).
Поэтому решение задачи однозначно задается последовательностью чисел 0, 1, 2, где 0 задает ход между А и В, 1 - между В и С и 2 - между А и С.
Генеришь эту последовательность для достаточно большого количества дисков (log n + 2 например). Получаешь то, что надо.
План доказательства у меня наметился, но в детали влезать лень. Просто как-нибудь - вряд-ли. Хотя, мало ли 
Автор: Гость 13.03.2007 1:30
VOLVO, а сам Запускать не пробовал?
Если бы попробовал, то увидел бы, что при запуске Выводится Черный ЭКРАН и никаких символов!!!!!!!!!
Автор: Артемий2 13.03.2007 1:39
Все прекрасно работает!!Ты бы убрал свою наглость и лень и все получилось-бы! Добавь readln в конец!
