Палиндром. какие бывают палиндромы?

Поиск

« Мар
1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

О нас

Этот Сайт использует файлы cookies для сбора и хранения данных. Посещая Сайт, вы автоматически соглашаетесь с использованием данных технологий.

Copyright, 2016. Enigma Theme | При копировании материала активная ссылка обязательна | Developed By Weblizar specially for Развивайка

Ответы по русскому языку. 4 класс. Учебник. Часть 2. Канакина В. П., Горецкий В. Г.

Ответы по русскому языку. Учебник. 4 класс. Часть 2. Канакина В. П., Горецкий В. Г.

Посещая Сайт, вы автоматически соглашаетесь с использованием данных технологий.

14.04.2017 8:07:57

2017-04-14 08:07:57

Коллекция палиндромов

Для начала мы хотели бы Вас пригласить на наш чемпионат:

Мы решили собирать коллекцию палиндромов.

Палиндром (от греч. «назад, снова» и греч. — «бег») — слово или текст, одинаково (или почти одинаково) читающиеся в обоих направлениях. Отдельные палиндромические словосочетания и фразы известны с глубокой древности, когда им зачастую придавался магически-сакральный смысл (не лишена этого оттенка, например, фраза На в лоб, болван, использовавшаяся русскими скоморохами в качестве перформативного высказывания). Авторское творчество в области палиндрома начинается, по-видимому, в Средние века. В русской литературе достоверно известно об авторском палиндромном стихе Державина «Я и;ду съ ме;чемъ судия», затем об авторском палиндромном стихе Фета «А роза упала на лапу Азора». Первую попытку многострочного (и довольно длинного) стихотворного произведения в форме палиндрома предпринял Велимир Хлебников в поэме «Разин». Однако расцвета русский литературный палиндром (преимущественно стихотворный) достиг только в 1970—1990-е года в творчестве Николая Ладыгина, а затем Владимира Гершуни, Елены Кацюбы и Дмитрия Авалиани. В 1990-х годах началось в России и детальное литературоведческое и лингвистическое изучение палиндромии — прежде всего Александром Бубновым и Германом Лукомниковым. Теоретики и практики палиндрома выделили многочисленные пограничные с палиндромом формы: например, оборотень — текст, читающийся слева направо иначе, чем справа налево: «Мир удобен» (Сергей Федин). Среди более редких разновидностей палиндромических текстов следует назвать также слоговые, словесные и фразовые палиндромы, двуязычные палиндромы (в одну сторону текст читается на одном языке, в обратную — на другом) и т. п.. На русском языке наиболее длинным буквенным палиндромом на сегодняшний день является произведение Р. Адрианова «ЦЕН ОКНО», в которой свыше 6 000 букв.

Мы будем Вам благодарны, если Вы добавите свои палиндромы в нашу коллекцию.

Ежу хуже Лев осовел Зона заноз Неуч учуен Утоп в поту Шику кукиш Ты сама сыта Болвана в лоб Да, гневен гад Маска как сам Чем нежен меч Мат и тут и там Там холм лохмат Он рёва наверно Вид усов осудив Лев с ума ламу свёл Кот, сука, за кусток Уверена я, а не реву Цени в себе свинец Отлично кончил-то Кошмар, срам, шок Милашка, как шалим Нахапал фуфла пахан А вот и харя рахитова Акт у нимф — минутка Кот учён, но не чуток Аргентина манит негра Потенция — яиц нет, оп Коту скоро сорок суток Лидер Венере не вредил Замучен он, но не чумаз А леди у ног его — ну и дела А роза упала на лапу Азора Он щи хлебал, слабея хищно И он видит сон юности дивной Желала дама секса, Ваське сама дала лёжа Лена набила pожy мyжy — мyж оpал и банан ел Муза, ранясь шилом опыта, ты помолишься на разума

Кирилл лирик Обратите внимание на это уникальное тройное «Л»

Палиндром. Какие бывают палиндромы?

Палиндромы — это слова, которые читаются одинаково в обоих направлениях: слева направо и справа налево. Самым длинным в мире палиндромом, состоящим из одного слова, принято считать финское слово SAIPPUAKIVIKAUPPIAS (торговец щелоком — мыльным камнем). В английском языке самый длинный палиндром — REDIVIDER (своего рода перегородка).

В русском языке довольно много слов-палиндромов. Приводим их группами по количеству букв.

Палиндромы из 2 букв

АА — так малыши говорят, когда садятся на горшок
ИИ — искусственный интеллект
ЯЯ — посёлок городского типа в Кемеровской области

Палиндромы из 3 букв

АБА — еврейское мужское имя, а также город в Нигерии
АГА — ядовитая тропическая жаба
АДА — женское имя
АЗА — женское имя
АКА — одна из групп пигмеев в Африке
АЛА — конное вспомогательное подразделение римской армии
АМА — японская ныряльщица за жемчугом
АРА — род птиц семейства попугаевых
АТА — в древнегреческой мифологии богиня обмана и глупости
АША — город в Челябинской области
БОБ — спортивные сани и плод растения семейства бобовых
ДЕД — пожилой мужчина
ИХИ — бог музыки у древних египтян
КОК — корабельный повар
МИМ — актер, работающий в жанре пантомимы
ОКО — глаз
ПОП — просторечное наименование священника
ПУП — пупок
СОС — сигнал о помощи в море
ТИТ — мужское имя
ТУТ — тутовое дерево
УШУ — китайское воинское искусство
ШИШ — то же, что кукиш

Палиндромы из 4 букв

АББА — знаменитый шведский квартет
АВВА — собака Айболита
АККА — главная гусыня из сказки про Нильса
АЛЛА — женское имя
АННА — женское имя
АССА — название фильма
ОТТО — мужское имя

Палиндромы из 5 букв

АДАДА — фильм Квон-Тэк Има (Ю. Корея).
АЗИЗА — женское имя
ВЕНЕВ — город в Тульской области
ДЕБЕД — река в Армении и Грузии
ДОВОД — аргумент в споре
ДОРОД — хороший урожай (устар.), антоним к НЕДОРОД (неурожай)
ДОХОД — прибыль
ЗАКАЗ — то, что заказали
КАБАК — старинный аналог бара
КАЗАК — житель Дона или Кубани
КИЛИК — древнегреческий сосуд плоской формы на короткой ножке
КИНИК — циник (устар.).
КОВОК — один удар молотом (устар.) — отсюда глагол ковать
КОЛОК — стержень для натяжения струн на гитаре
КОМОК — что-то скомканное
КОПОК — действие, производимое лопатой при копании
КОТОК — ласковое название кота (устар.)
МАДАМ — обращение к замужней женщине
НАГАН — пистолет
НАТАН — еврейское имя
НИЖИН — город, родина Марка Бернеса.
НОЙОН — монгольский аристократ
ПОТОП — наводнение
РАДАР — радиолокатор
РЕПЕР — геодезический знак
РОТОР — подвижная часть механизма
СОРОС — американский бизнесмен
ТАНАТ — (Фанат, Танатос) брат-близнец бога сна Гипноса
ТОПОТ — шум шагов
ШАБАШ — гулянка нечисти
ШАЛАШ — палатка из веток

Палиндромы из 6 букв

МИЛЛИМ — 1/000 тунисского динара.
НЯННЯН — китайская богиня, защищающая младенцев и помогающая при родах
ТИЛЛИТ — минерал, сульфид олова и свинца
ТИННИТ — богиня в Карфагене
ТОММОТ — город в Якутии

Палиндромы из 7 букв

АНИСИНА — плод аниса
АПОКОПА — отпадение звука в конце слова
КИНОНИК — православное церковное песнопение
РОТАТОР — аппарат для печати копий с рукописей, документов, чертежей
ТАРТРАТ — соль винной кислоты

Улучшаем асимптотику решения

Мы можем ускорить это решение с помощью техники двух указателей. Не будем обнулять счётчики и сбрасывать позицию R после того, как максимально отошли вправо от L. Переиспользуем текущую информацию при переходе от L к L+1. Для этого надо убрать из счётчиков элемент на позиции L — и всё. Затем можно продолжать делать проверки и отодвигать R вправо до тех пор, пока не исчерпаются K операций изменения элементов.

На рисунке выше показан ход указателей L и R, K=2. Подчёркнутые символы будут изменены при соответствующих L и R

Оценим сложность новой версии алгоритма. Указатель R суммарно сделает не более n шагов вправо, указатель L — тоже. Передвижение указателя сопровождается обновлением счётчиков и проверкой числа изменений для получения хорошей подстроки — эти действия выполняются за константное время, O(1). Таким образом мы получаем сложность O(n).

Мы выпутались из этой задачи, теперь можно запутываться в какую-нибудь другую.

Подробнее про метод двух указателей и про другие интересные приёмы мы рассказываем на курсе «Алгоритмы и структуры данных». Если вам интересна эта тема, приглашаю на наш курс.

Что такое палиндром

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, слово «АТАТА» — это палиндром, а вот слово «АЙАЙАЙ» — нет.

Пример палиндрома из латинских слов: он составлен таким образом, что в каком бы направлении вы ни начали читать текст, получится одно и то же

Известный кинематографический палиндром — название вышедшего в 2020 году фильма «Довод» (англ. «Tenet»). Русская адаптация в каком-то плане уникальна, потому что у нас нашлась подходящая альтернатива слову «tenet», которая тоже является палиндромом. На многих других языках (в том числе славянских) название фильма оставили как есть. Например, на украинском это «ТЕНЕТ» (Википедия).

Источники:

Русский язык учебник Канакина, Горецкий 4 класс 2 часть. Ответы на задания » /> » /> .keyword { color: red; }

Русский язык учебник Канакина, Горецкий 4 класс 2 часть. Ответы на задания

Готовые домашние задания по учебнику русского языка за 4 класс, вторая часть, авторы В. П. Канакина, В. Г. Горецкий, программа Школа России. Продолжаем углубляться в правила русского языка, будет много разборов — это и разбор слов по составу, и звуко-буквенный, и разбор предложений по членам. Схемы и образцы разбора есть в конце учебника, на них ориентируйтесь. Учитель может вас просить оформлять иначе, чем в учебнике, так что слушайте и прислушивайтесь, делайте так, как разбирали в классе.

Занимаясь по второй части учебника для четвертого класса, ребята в подробностях изучат имя прилагательное, узнают многое о местоимениях и какими они бывают, поближе познакомятся с глаголами, а потом снова повторят, обобщат и закрепят весь изученный материал.

Списывать нежелательно, пытайтесь сами рассуждать и отвечать на вопросы, а использовать только для сверки своих ответов с правильными. Не забывайте учить словарные слова и пополнять свой словарный запас

Важно уделять внимание и время изучению русского языка уже сейчас, потому что в четвертом классе происходит обобщение ранее изученного материала, углубление знаний, закладывается основа для успешной учёбы в последующие годы

С грамотным человеком всегда приятнее общаться, будьте же такими.

Решебник проверен и одобрен учителем начальных классов. Все ответы расположены постранично, так же, как и задания в учебнике Канакиной и Горецкого за 4 класс.

Постановка задачи

Итак, задача. Подготовьтесь морально.

Всё, клубок запутался. Начнём распутывать.

Вот несколько примеров нечётных палиндромов: «ATATA», «KKKKKKKK», «ABA», «ZO».

Рассмотрим подробнее первую строку — АТАТА. Выпишем все её подстроки нечётной длины:

A, T, A, T, A — однобуквенное слово всегда палиндром
ATA, TAT, ATA — очевидно, палиндромы
ATATA — тоже

В слове ZO нет подстрок нечётной длины больше чем в одну букву. И «Z», и «O» — палиндромы, поэтому «ZO» — нечётный палиндром.

Пусть нам дана строка ABCDEF, и мы можем заменить не более одного символа (K=1), чтобы сделать из неё нечётный палиндром. Оптимальным решением было бы, например, заменить первую букву на C, тогда мы получили бы CBCDEF, где длина наибольшей подстроки, являющейся нечётным палиндромом, была бы равна трём (это CBC).

С тем же успехом мы могли бы прийти к варианту ABCFEF.

А вот если изначально у нас была строка ZXXXZ, и опять можно изменить не более одного символа, то надо заменить средний, так как ZXX и XXZ не являются палиндромами. В итоге мы получим ZXZXZ.

Наивное решение

Теперь попробуем сделать как можно более длинную хорошую подстроку, которая начинается строго в символе с номером L. Указатель R будет отмечать ту позицию, до которой мы сумели расширить хорошую подстроку. Будем шагать указателем R вправо, начиная от позиции L. На каждом шаге будем учитывать в счётчике символов для чётных и нечётных позиций очередной символ. Прежде чем передвинуть R на шаг вправо, проверим по счётчикам, что сделать подстроку с L до R хорошей можно не более чем за K операций.

Если применить описанные действия независимо для всех L от 0 до n – 1, где n — длина исходной строки, а затем найти наиболее длинную найденную хорошую подстроку, то мы решим задачу. Однако временная сложность данного решения составит O(n^2), так как для каждой позиции L мы сделаем в худшем случае примерно n – L шагов при передвижении R.

Палиндромы из 9 букв

В сказке А.К.Толстого «Золотой ключик, или приключения Буратино» Мальвина диктовала Буратино палиндром, который тот должен был записать.

Палиндромы из нескольких слов

В разных языках существует огромное количество палиндромов, состоящих из нескольких слов. Короткие фразы-палиндромы, как правило, изящны и заключают в себе некий смысл.

А роза упала на лапу Азора. (Афанасий Фет)
Я иду съ мечемъ судия (Гавриил Державин)
Я — арка края (Валерий Брюсов)
О, лета тело! (Валерий Брюсов)
Аргентина манит негра.
На в лоб, болван!
Умер, и мир ему.
Лезу на санузел.
Лепс спел.
Лёша на полке клопа нашёл.
Нажал кабан на баклажан.
Утречко летело к черту.
У дуба буду.
Дом мод.
Oколо Миши молоко.
Морда казака за кадром.
Вот сила типа капиталистов.
Летя, догонит иного дятел.
Ешь немытого ты меньше!
Откопать тапок-то?
«Пустите!» — Летит супу миска Максиму. — «Пустите, летит суп!»
А щётка – как тёща!
Я не реву — уверен я.
А муза рада музе без ума да разума.
Кулинар, храни лук.
Ты, милок, иди яром: у дороги мина, за дорогой огород, а за ним и город у моря; иди, коли мыт.
Он в аду давно.
Ого, вижу живого.
Коту скоро сорок суток.
Не женат, а нежен.
Ты моден и недомыт.
Оно, лосося мясо, солоно.
Дорого небо, да надобен огород.
Яро бранил уксус кулинар Боря.
Веер веял для евреев.
Я с леди все же свиделся.
Мак чужд жучкам.
Мокнет Оксана с котенком.
Ешь немытого ты меньше!
Дорого небо, да надобен огород.
Лидер бредил.
Меня истина манит сияньем.
Надо меч в кулак, а лук — в чемодан.
Шорох от дубка как будто хорош.
Не видно, как он дивен.
А в Енисее — синева.
Я сличил то и то — вот и отличился.
Лидер бодро, гордо бредил.
Я умру, хлебороб, – ел хурму я.
И мал Иван, а лупил у лип улана вилами!
Веласкес — секса лев!
Арбуз-то от зубра.
Масла ЗАМ мазал сам.
Хам он, о Мономах!
Режу фужер.
Тима хамит.
Лёша нашёл.
Уверен — она зараза, но не реву.
Олесе весело.

Интересно двустишие Д. Авалиани, написанное гомеровским гекзаметром (две строчки — два палиндрома):

Море могуче. В тон ему, шумен отвечу Гомером:

«Море, веру буди — ярок, скор я иду буревером»

Палиндромы на иностранных языках

Древнейший из сохранившихся палиндромов написан на латыни и датируется 4 в. н.э. Это фраза «Sator Arepo tenet opera rotas», что означает «Сеятель Арепо с трудом держит колёса». Обычно записывают ее в форме квадрата:

S A T O R A R E P O T E N E T O P E R A R O T A S

В таком виде палиндром читается четырьмя способами: по горизонтальным и вертикальным рядам — слева направо и справа налево.

Еще один изящный палиндром, понятный даже без знания инотсранных языков:

«Madam, I’m Adam» («Мадам, я — Адам», — представился первый человек первой женщине) «Eve» («Ева», — скромно палиндромом ответила она).

Самые длинные палиндромы в мире

В палиндромичном году (2002) Петер Норвиг (англ. Peter Norvig) закончил пятилетнюю работу с применением компьютера по созданию самого длинного палиндрома на английском языке, состоящего из 17 259 слов. Написанная в традициях классического палиндрома A man, a plan, a canal. Panama («Человек, план, канал — Панама»), эта фраза начинается A man, a plan, a cameo, Zena… и заканчивается …Ibanez, OEM, a canal, Panama. К сожалению, в целом этот длиннейший палиндром лишен смысла.

Самый длинный связный роман-палиндром «Olson in Oslo» был написан Лоуренсом Левиным (англ. Lawrence Levine) и состоит из 31 594 слов. Но он труден для чтения из-за применения странных грамматических структур и архаичного языка.

Еще один очень длинный палиндром был составлен Джеральдом Бернсом (англ. Gerald M. Berns), и представляет собой бессмысленный список из 31 358 слов.

Структура нечётного палиндрома

Теперь заметим кое-что в рассмотренных примерах. Все нечётные палиндромы имеют схожую структуру: в них чередуются буквы (или все буквы одинаковые). И это действительно единственная форма, которую имеет нечётный палиндром. Почему это так?

Посмотрим ещё раз на определение: нечётным палиндромом будем называть такую строку, у которой все подстроки нечётной длины являются палиндромами. Если все подстроки нечётной длины являются палиндромами, то и все подстроки длины 3 являются палиндромами. Отсюда сразу же следует, что на чётных позициях не может быть двух различных букв, то же самое верно для нечётных.

На рисунке выше показано, как получается чередующаяся структура строки. Одинаковым цветом выделены одинаковые символы. Сначала посмотрим на палиндром длины 3, который начинается в самом первом символе исходной строки. Тогда 1 и 3 символ можно пометить зеленым. Про 2-й символ пока ничего непонятно. Сдвинем палиндром на единицу вправо, получим, что 2 и 4 символы можно покрасить в один цвет. Так, сдвигаясь каждый раз на единицу, мы получим, что все символы на нечётных позициях зелёные, а на чётных — синие. Более строго можно доказать этот факт с помощью метода математической индукции, например.

Теперь, когда мы поняли, что надо искать, вернёмся непосредственно к задаче. Для краткости будем называть подстроки, которые являются нечётными палиндромами, хорошими. Надо изменить не более K символов так, чтобы максимизировать длину хорошей подстроки в последовательности.

Сперва разберёмся, как сделать из произвольной подстроки хорошую. Надо заменить на один и тот же символ все элементы на чётных позициях и отдельно заменить на нечётных.

Чтобы сделать как можно меньше замен, стоит выбрать в качестве единого символа самый частый среди тех, что стоят на чётных или нечётных позициях. Найти самый частый символ можно с помощью словаря (хеш-мапа, хеш-таблицы) отдельно для чётных и нечётных позиций. Алфавит в текущей задаче ограничен 26 символами, поэтому счётчик будет занимать константное количество дополнительной памяти.

Пройдёмся один раз по строке и добавим единицу в ячейку нужного словаря по текущему символу. Далее найдём в каждом словаре самый частый символ (если символов с максимальным числом вхождений несколько, то можно выбрать любой). Именно на этот символ надо заменить все элементы на чётных или нечётных позициях.

Дерево палиндромов

Дерево палиндромов (англ. palindromic tree, EERTREE) — структура данных, использующая другой, более мощный формат хранения информации обо всех подпалиндромах, чем размеры (n) палиндромов. Она была предложена Михаилом Рубинчиком на летних петрозаводских сборах в 2014-м году.

Лемма. В строке есть не более (n) различных подпалиндромов.

Доказательство. Пусть мы дописываем к строке по одному символу и в данный момент, записав (r) символов, имеем наибольший суффикс-палиндром (s_{l:r}). Пусть у него, в свою очередь, есть суффикс-палиндром (s_{l’:r} = t). Тогда он также имеет более раннее вхождение в строку как (s_{l:l+r-l’} = t). Таким образом, с каждым новым символом у строки появляется не более одного нового палиндрома, и если таковой есть, то это всегда наибольший суффикс-палиндром.

Этот факт позволяет сопоставить всем палиндромам строки сопоставить следующую структуру: возьмём от каждого палиндрома его правую половину (например, (caba) для (abacaba) или (ba) для (abba); будем рассматривать пока что только чётные палиндромы) и добавим все эти половины в префиксное дерево — получившуюся структуру и будем называть деревом палиндромов.

Наивный алгоритм построения будет в худшем случае работать за (O(n^2)), но это можно делать и более эффективно.

Построение за линейное время

Будем поддерживать наибольший суффикс-палиндром. Когда мы будем дописывать очередной символ (c), нужно найти наибольший суффикс этого палиндрома, который может быть дополнен символом (c) — это и будет новый наидлиннейший суффикс-палиндром.

Для этого поступим аналогично алгоритму Ахо-Корасик: будем поддерживать для каждого палиндрома суффиксную ссылку (l(v)), ведущую из (v) в её наибольший суффикс-палиндром. При добавлении очередного символа, будем подниматься по суффиксным ссылкам, пока не найдём вершину, из которой можно совершить нужный переход.

Если в подходящей вершине этого перехода не существовало, то нужно создать новую вершину, и для неё тоже понадобится своя суффиксная ссылка. Чтобы найти её, будем продолжать подниматься по суффиксным ссылкам предыдущего суффикс-палиндрома, пока не найдём второе такое место, которое мы можем дополнить символом (c).

Здесь мы использовали обычный массив для хранения переходов. Как и для любых префиксных деревьев, вместо него можно использовтать бинарное дерево поиска, хэш-таблицу, односвязный список и другие структуры, позволяющие обменять время на память, немного изменив асимптотику.

Асимптотика

Покажем линейность алгоритма. Рассмотрим длину наибольшего суффикс-палиндрома строки. Каждый новый символ увеличивает её не более, чем на 2. При этом каждый переход по суффиксной ссылке уменьшает её, поэтому нахождение первого суффикс-палиндрома амортизировано работает за линейное время.

Ответы на задания учебника русского языка 4 класс

С грамотным человеком всегда приятнее общаться, будьте же такими.