IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
Closed Topic Открыть новую тему 
> Интересная задача на рекурсию, Посл-ть из 3 символов
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Нужна помощь в решении этой задачи:
Нужно записать с использованием рекурсии программу создания n-символьной последовательности, состоящей из совокупности трех символов (например: 0,1,2 или a,b,c), в которой нет двух смежных идентичных подпоследовательностей, например, послед-ти 2011 и 21012101 не удовлетворяют условию задачи, т.к. в первой рядом расположены два одинаковых элемента 1, а во второй – одинаковые подпоследовательности 2101.
Интересная только как тут задать условие повторения подпоследовательностей?
Предлагайте свои варианты решения.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
как тут задать условие повторения подпоследовательностей?
Вот это:
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.

с небольшими усовершенствованиями (для ускорения работы) применять для каждой сгенерированной последовательности... Разберешься?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Если честно, не очень понял.
Это только для последовательности, состоящей из 0,1,2
или для всех?
Или только для 2011???
Если не трудно объясни.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Ты спросил, как определять существует ли повторяющаяся ПОДпоследовательность в заданной последовательности? Я тебе показал... Генерация всех возможных последовательностей, состоящих из заданного набора символов, уже рассматривалась на форуме, ищи в Поиске...

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

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


Как только сгенерировал очередную последовательность - передавай ее в функцию, и если функция вернула True - значит, последовательность НЕ содержит 2-х рядом стоящих ПОДпоследовательностей ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


1. Получается, что проверяется только повторение заданных подпоследовательностей (например в твоем
решении - 2101 и 2011)
Нужно проверить все повторения.
2. Как генерировать n-символьную последовательность? Я могу, например, сделать
последовательность,кратную 3,4,...
На форуме не нашел, а сам не допираю.
Подскажи, если не трудно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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

Цитата
Я могу, например, сделать последовательность,кратную 3,4,
Покажи, как ты генерируешь последовательности длиной в 6 символов, я тебе покажу, как твой код переделать для N-символьных последовательностей...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Нет, я делаю последовательности, но не состоящие из определенных символов.
Вот

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.


Помоги пожалуйста.
Я никак не разберусь.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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

Во-вторых, какой длины может быть последовательность? 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-х секунд...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Как вывести полученную послед-ть на экран?
Или она уже так быстро выводится?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата
Как вывести полученную послед-ть на экран?
mad.gif А запустить программу не пробовал??? В общем, я смотрю, чем больше помогаешь, тем больше садятся на шею... Все, я больше в эту тему не хожу - надоело мне одно и то же пережевывать десятый раз!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Жестко.

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

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

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

План доказательства у меня наметился, но в детали влезать лень. Просто как-нибудь - вряд-ли. Хотя, мало ли smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






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


Помощник капитана
****

Группа: Пользователи
Сообщений: 601
Пол: Мужской
Реальное имя: Артем

Репутация: -  2  +


Цитата(Правила форума)
НЕ ПИШИТЕ В БОЛЬШОМ РЕГИСТРЕ! ЭТО РАСЦЕНИВАЕТСЯ КАК КРИК!! ВАМ НРАВИТСЯ, КОГДА НА ВАС КРИЧАТ?

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

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

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


--------------------
Dum spiro spero!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






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

Closed Topic Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.10.2020 18:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name