Интересная задача на рекурсию, Посл-ть из 3 символов Опции

[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]

Как вывести полученную послед-ть на экран?

А запустить программу не пробовал??? В общем, я смотрю, чем больше помогаешь, тем больше садятся на шею... Все, я больше в эту тему не хожу - надоело мне одно и то же пережевывать десятый раз!

[Michael_Rybak]

Жестко.

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

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

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

План доказательства у меня наметился, но в детали влезать лень. Просто как-нибудь - вряд-ли. Хотя, мало ли

[Гость]

VOLVO, а сам Запускать не пробовал?
Если бы попробовал, то увидел бы, что при запуске Выводится Черный ЭКРАН и никаких символов!!!!!!!!!

[Артемий]

НЕ ПИШИТЕ В БОЛЬШОМ РЕГИСТРЕ! ЭТО РАСЦЕНИВАЕТСЯ КАК КРИК!! ВАМ НРАВИТСЯ, КОГДА НА ВАС КРИЧАТ?

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

Все прекрасно работает!!Ты бы убрал свою наглость и лень и все получилось-бы! Добавь readln в конец!

Сообщение отредактировано: Артемий2 - 12.03.2007 21:40

[volvo]

VOLVO, а сам Запускать не пробовал?

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