Помощь - Поиск - Пользователи - Календарь
Полная версия: Интересная задача на рекурсию
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
striker
Нужна помощь в решении этой задачи:
Нужно записать с использованием рекурсии программу создания n-символьной последовательности, состоящей из совокупности трех символов (например: 0,1,2 или a,b,c), в которой нет двух смежных идентичных подпоследовательностей, например, послед-ти 2011 и 21012101 не удовлетворяют условию задачи, т.к. в первой рядом расположены два одинаковых элемента 1, а во второй – одинаковые подпоследовательности 2101.
Интересная только как тут задать условие повторения подпоследовательностей?
Предлагайте свои варианты решения.
volvo
Цитата
как тут задать условие повторения подпоследовательностей?
Вот это:
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
Если честно, не очень понял.
Это только для последовательности, состоящей из 0,1,2
или для всех?
Или только для 2011???
Если не трудно объясни.
volvo
Ты спросил, как определять существует ли повторяющаяся ПОДпоследовательность в заданной последовательности? Я тебе показал... Генерация всех возможных последовательностей, состоящих из заданного набора символов, уже рассматривалась на форуме, ищи в Поиске...

Теперь о вызове того алгоритма, что я написал: оформи его в виде функции:

function os_ok(s: string): boolean;
begin
{ Тут - описанные выше действия }
end;


Как только сгенерировал очередную последовательность - передавай ее в функцию, и если функция вернула True - значит, последовательность НЕ содержит 2-х рядом стоящих ПОДпоследовательностей ...
striker
1. Получается, что проверяется только повторение заданных подпоследовательностей (например в твоем
решении - 2101 и 2011)
Нужно проверить все повторения.
2. Как генерировать n-символьную последовательность? Я могу, например, сделать
последовательность,кратную 3,4,...
На форуме не нашел, а сам не допираю.
Подскажи, если не трудно.
volvo
striker, ты внимательно прочел, что я написал? Программу запустил? Попробовал менять исходные данные? Повторяю еще раз (больше повторять не буду): то, что я привел - проверяет, присутствуют ЛИ в переданной функции строке ЛЮБЫЕ 2 подпоследовательности, идущие ПОДРЯД одна за другой!!! Что ты в эту функцию будешь передавать - ее не касается! Передашь '1234567891234567890' - получишь False, потому, что эта строка СОДЕРЖИТ 2 раза подряд '123456789'. Все, больше повторять не буду.

Цитата
Я могу, например, сделать последовательность,кратную 3,4,
Покажи, как ты генерируешь последовательности длиной в 6 символов, я тебе покажу, как твой код переделать для N-символьных последовательностей...
striker
Нет, я делаю последовательности, но не состоящие из определенных символов.
Вот

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
Цитата
я делаю последовательности, но не состоящие из определенных символов.
Где в ПЕРВОНАЧАЛЬНОМ задании сказано, что в последовательности не должно быть каких-то символов? Я этого условия не обнаружил... Это во-первых.

Во-вторых, какой длины может быть последовательность? 6 символов? 7? 20? 120? чем больше будет это число, тем меньше у тебя шансов дождаться окончания работы программы, и тем большее значение приобретает оптимизация. Поэтому уточни, какое максимальное N может быть, потом я покажу, что надо делать...

Добавлено через 13 мин.
В частности, при N = 4 вполне возможно вот такое, например, решение:
const
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.

, программа отработает практически мгновенно... Однако при N = 22 эта программа будет работать уже больше 2-х секунд...
striker
Как вывести полученную послед-ть на экран?
Или она уже так быстро выводится?
volvo
Цитата
Как вывести полученную послед-ть на экран?
mad.gif А запустить программу не пробовал??? В общем, я смотрю, чем больше помогаешь, тем больше садятся на шею... Все, я больше в эту тему не хожу - надоело мне одно и то же пережевывать десятый раз!
Michael_Rybak
Жестко.

В общем, это ханойские башни. Между каждыми двумя столбиками на каждом шагу можно совершить только одну операцию (для столбиков А и В можно переложить с А на В, если верхний диск на А меньше, чем на В, и с В на А в противном случае).

Поэтому решение задачи однозначно задается последовательностью чисел 0, 1, 2, где 0 задает ход между А и В, 1 - между В и С и 2 - между А и С.

Генеришь эту последовательность для достаточно большого количества дисков (log n + 2 например). Получаешь то, что надо.

План доказательства у меня наметился, но в детали влезать лень. Просто как-нибудь - вряд-ли. Хотя, мало ли smile.gif
Гость
VOLVO, а сам Запускать не пробовал?
Если бы попробовал, то увидел бы, что при запуске Выводится Черный ЭКРАН и никаких символов!!!!!!!!!
Артемий
Цитата(Правила форума)
НЕ ПИШИТЕ В БОЛЬШОМ РЕГИСТРЕ! ЭТО РАСЦЕНИВАЕТСЯ КАК КРИК!! ВАМ НРАВИТСЯ, КОГДА НА ВАС КРИЧАТ?

Цитата(Правила форума)
Если вы НЕ СОГЛАСНЫ С ДАННЫМИ ПРАВИЛАМИ, вы имеете полное право найти для себя более подходящий ресурс.

Все прекрасно работает!!Ты бы убрал свою наглость и лень и все получилось-бы! Добавь readln в конец! dry.gif
volvo
Цитата
VOLVO, а сам Запускать не пробовал?
Заруби себе на носу! Я НИКОГДА, слышишь, НИКОГДА не выкладываю программ, которые не протестировал (если об этом не сказано отдельно). Ясно? Все, тема закрыта, я не считаю нужным тебе еще что-то объяснять (и уж тем более - оправдываться).
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.