Здравствуйте, Буравчик, Вы писали:
Б>Задача не сложная. Поэтому предлагаю такой вариант задачи:
Б>Найти все строки, в которой любая подстрока не повторяется более 5 раз. Б>Причем не важно подряд или не подряд.
В ней не более 5 нулей и 5 единиц. И наоборот, если в строке не более 5 нулей и 5 единиц, то нет более 5 повторов.
Б>Считаем, что одинаковые ПЕРЕСЕКАЮЩИЕСЯ подстроки одинаковыми НЕ являются. Б>Например, вариант 1111111 тоже подходит, хотя с пересечениями подстрока 11 повторяется 6 раз (без пересечений всего 3)
Необходимо составить строку произвольной длины, которая соответствует следующим требованиям
— состоит из 0 и 1
— не содержит трех одинаковых подстрок идущих подряд
примеры
01110 — не ок
011011011010 — не ок (101 повторяется)
001001101 — ок
Средства, язык, любые. Код или алгоритм не имеет значения, но с кодом лучше проверить алгоритм.
Здравствуйте, Ation, Вы писали:
A>Средства, язык, любые. Код или алгоритм не имеет значения, но с кодом лучше проверить алгоритм.
Решение в лоб.
Пусть у нас есть некоторая строка, удовлетворяющая условию задачи.
Пробуем добавить в ее конец 0 или 1. Затем проверяем, что полученная строка тоже подходит под условие.
Как проверять:
Будем рассматривать три последних подстроки (с конца) некоторой длины и проверять их идентичность.
Т.е. рассматриваем три последних подстроки сначала длиной 1, затем 2, 3 и т.д.
Увеличиваем длину подстроки, пока мы можем выделить три полных подстроки подряд нужной длины.
Например для строки длиной 10 нам нужно проверить подстроки с конца длиной 1,2,3.
Если полученные подстроки на каком-то шаге получились одинаковыми, то строка не подходит.
Если все проверили и одинаковых подстрок не нашли, то строка подходит
Решение на Haskell. Выводит все искомые строки в порядке возрастания их длины.
import Data.List
import Control.Monad
-- разбивает список на блоки по n элементов
split [] _ = []
split xs n = let (as,bss) = splitAt n xs in as : split bss n
-- Проверяет, что строка соответствует условию задачи
-- Элементы строки представлены в обратном порядке (reverse)
goodStr xs = all good $ takeWhile ((>=3) . length) $ map (take 3 . split xs) [1..]
where good [a,b,c] = not $ a==b && a==c
-- Генерирует бесконечный список всех подходящих строк в порядке возрастания их длины
-- Не забываем обратно перевернуть строку
gen = gen' [[]]
gen' (str:ss) = if goodStr str then (reverse str) : rest else rest
where rest = gen' $ ss ++ ['0':str, '1':str]
Здравствуйте, Ation, Вы писали:
A>Необходимо составить строку произвольной длины, которая соответствует следующим требованиям A>- состоит из 0 и 1 A>- не содержит трех одинаковых подстрок идущих подряд A>примеры A>01110 — не ок A>011011011010 — не ок (101 повторяется) A>001001101 — ок
Задача не сложная. Поэтому предлагаю такой вариант задачи:
Найти все строки, в которой любая подстрока не повторяется более 5 раз.
Причем не важно подряд или не подряд.
Считаем, что одинаковые ПЕРЕСЕКАЮЩИЕСЯ подстроки одинаковыми НЕ являются.
Например, вариант 1111111 тоже подходит, хотя с пересечениями подстрока 11 повторяется 6 раз (без пересечений всего 3)
Здравствуйте, Ation, Вы писали:
A>Необходимо составить строку произвольной длины, которая соответствует следующим требованиям A>- состоит из 0 и 1 A>- не содержит трех одинаковых подстрок идущих подряд A>примеры A>01110 — не ок A>011011011010 — не ок (101 повторяется) A>001001101 — ок A>Средства, язык, любые. Код или алгоритм не имеет значения, но с кодом лучше проверить алгоритм.
Я бы на собеседовании спрашивал так:
1. Докажите, что существует бесконечная строка, удовлетворяющая условию. (Это больше, чем просто доказать, что для любого N есть такая строка длины N.)
2. Опишите алгоритм, который выписывает такую бесконечную строку.
Здравствуйте, Буравчик, Вы писали:
Б>Пусть у нас есть некоторая строка, удовлетворяющая условию задачи. Б>Пробуем добавить в ее конец 0 или 1. Затем проверяем, что полученная строка тоже подходит под условие.
Б>Как проверять: Б>Будем рассматривать три последних подстроки (с конца) некоторой длины и проверять их идентичность. Б>Т.е. рассматриваем три последних подстроки сначала длиной 1, затем 2, 3 и т.д. Б>Увеличиваем длину подстроки, пока мы можем выделить три полных подстроки подряд нужной длины. Б>Например для строки длиной 10 нам нужно проверить подстроки с конца длиной 1,2,3.
Б>Если полученные подстроки на каком-то шаге получились одинаковыми, то строка не подходит. Б>Если все проверили и одинаковых подстрок не нашли, то строка подходит
Не интересно. Тебе, чтобы построить строку длины N, надо хранить ВСЕ строки длины N-1.
Здравствуйте, vadimcher, Вы писали:
V>Не интересно. Тебе, чтобы построить строку длины N, надо хранить ВСЕ строки длины N-1.
Ну, в некотором роде это верно, т.к. не из любой строки (N-1) можно получить строку N.
Но, насчет хранения ВСЕХ строк — это перебор
Хотя, в целом, согласен.
Я решал более общую задачу — построение ВСЕХ таких строк, а не одной — заданной длины.
Для построения одной строки алгоритм не эффективен.
Б>Ну, в некотором роде это верно, т.к. не из любой строки (N-1) можно получить строку N.
Правильно. Например, 00100100 нельзя продлить, удовлетворяя условию.
Б>Но, насчет хранения ВСЕХ строк — это перебор
Не совсем. Если ты заранее не знаешь, какие строки окажутся такими, что их нельзя будет на каком-то шаге продлить, то придется строить все строки, чтобы из них построить все строки следующего размера и т.д. Можно, конечно, убрать какой-то процент строк за счет симметрии и т.п., но количество таких строк будет расти экспоненциально. Как вариант, надо знать как строить такую строку максимальной длины, а дальше строить ту часть, которая требуется.
Б>Хотя, в целом, согласен. Б>Я решал более общую задачу — построение ВСЕХ таких строк, а не одной — заданной длины. Б>Для построения одной строки алгоритм не эффективен.
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Ation, Вы писали:
A>>Необходимо составить строку произвольной длины, которая соответствует следующим требованиям A>>- состоит из 0 и 1 A>>- не содержит трех одинаковых подстрок идущих подряд A>>примеры A>>01110 — не ок A>>011011011010 — не ок (101 повторяется) A>>001001101 — ок A>>Средства, язык, любые. Код или алгоритм не имеет значения, но с кодом лучше проверить алгоритм.
V>Я бы на собеседовании спрашивал так:
V>1. Докажите, что существует бесконечная строка, удовлетворяющая условию. (Это больше, чем просто доказать, что для любого N есть такая строка длины N.) V>2. Опишите алгоритм, который выписывает такую бесконечную строку.
Интересно на какую должность надо проводить собеседование, чтоб в его рамки подходила такая задачка? Она то конечно простенькая, но для не топорного решения уйдет не 20 и не 30 минут.
Здравствуйте, Ation, Вы писали:
A>Необходимо составить строку произвольной длины, которая соответствует следующим требованиям A>- состоит из 0 и 1 A>- не содержит трех одинаковых подстрок идущих подряд A>примеры A>01110 — не ок A>011011011010 — не ок (101 повторяется) A>001001101 — ок
A>Средства, язык, любые. Код или алгоритм не имеет значения, но с кодом лучше проверить алгоритм.
По заданной длине составить одну строку?
Тогда это известная задача по построению сильно бескубного слова.
a, ab, abba, abba baab, abba baab baab abba,
ну и так далее. способ построения и доказательство можно найти по этим буквам (ну способ в принципе и так видно).
Re[3]: Задачка на формирование строки
От:
Аноним
Дата:
12.11.10 21:31
Оценка:
V>>1. Докажите, что существует бесконечная строка, удовлетворяющая условию. (Это больше, чем просто доказать, что для любого N есть такая строка длины N.) V>>2. Опишите алгоритм, который выписывает такую бесконечную строку.
A>Интересно на какую должность надо проводить собеседование, чтоб в его рамки подходила такая задачка? Она то конечно простенькая, но для не топорного решения уйдет не 20 и не 30 минут.
Ну про эту последовательность я лично знал с 6 класса (не шучу). без доказательства конечно.
Здравствуйте, Аноним, Вы писали:
V>>>1. Докажите, что существует бесконечная строка, удовлетворяющая условию. (Это больше, чем просто доказать, что для любого N есть такая строка длины N.) V>>>2. Опишите алгоритм, который выписывает такую бесконечную строку.
A>>Интересно на какую должность надо проводить собеседование, чтоб в его рамки подходила такая задачка? Она то конечно простенькая, но для не топорного решения уйдет не 20 и не 30 минут.
А>Ну про эту последовательность я лично знал с 6 класса (не шучу). без доказательства конечно.
Я не знал. Но приблизительно так решал бы, если бы понадобился такой алгоритм. Первый пункт достаточно простой. Его можно, конечно, избежать, если сразу догадаться, как строить последовательность для второго пункта. Но обычно, если не знаешь, можно ли вообще построить такую последовательность, то начинаешь с чего-то вроде такого утверждения, как в пункте 1.
А вот зайца кому, зайца-выбегайца?!
Re[3]: Задачка на формирование строки
От:
Аноним
Дата:
16.11.10 23:38
Оценка:
Здравствуйте, Аноним, Вы писали:
А>>ну и так далее. способ построения и доказательство можно найти по этим буквам (ну способ в принципе и так видно). А>а. вот оно как называется. А>http://ru.wikipedia.org/wiki/Последовательность_Морса-Туэ
Добавлю ещё.
По ссылке не указано, но эта последовательность обладает более сильным свойством чем отсутствие XXX.
"сильная бескубность" — то бишь отсутствие XXy где y — первая буква X.
Данное свойство позволяет на основе этой последовательности(в википедии есть пример замены) составить бесквадратную (не содержащую XX) последовательность из 3 символов.
