Перестановки, Объясните [перемещено] |
1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!
Перестановки, Объясните [перемещено] |
Lapp |
19.07.2009 12:44
Сообщение
#21
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
В принципе вот условие) А в принципе, в чем проблема? ))Пока я тут не вижу ничего реально связанного с перестановками, кроме названия. Можно было бы назвать.. скажем, Петей.. Цитата Петей порядка n называется последовательность из попарно различных целых положительных чисел p1, p2, ... , pn, где каждое 1 <= pi <= n. Будем говорить, что Петя q1, q2, ... , qn лексикографически меньше Пети p1, p2, . . . , pn, если существует такое i, что qi < pi, а для любого j < i pj = qj . Циклическим сдвигом на k Пети p1, p2, ... , pn называется последовательность, pk+1, pk+2, ... , pn, p1, ... , pk. Отметим, что любой циклический сдвиг Пети также является Петей. Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданного Пети Как тебе такое? И короче вышло.. Извиняюсь, рука не поднялась писать Петя с маленькой буквы))). Так в чем проблема? Дан Петя. Сдвигаешь его циклически и ищешь минимального.. Что именно непонятно? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Cheburashka |
19.07.2009 12:51
Сообщение
#22
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация: 2 |
Тогда я так сказать приведу пару своих примеров и вы скажите правильно ли я это понимаю:
Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав? Или вот ещё пару 321 - 132. DCBAE - AEDCB (43215 - 15432) Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка. -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
Lapp |
19.07.2009 13:11
Сообщение
#23
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав? Прав, Петя 4213 > Петя 1342.Или вот ещё пару А тут я ничего не понял . Зачем знак "минус"? Если хочешь сказать, кто больше/меньше, используй > или <. И ЗАЧЕМ ты перевел в буквы?? Это же внесет страшную путаницу, когда (и если) ты будешь действительно пользоваться ими как перестановками. Ты, что, действительно говоришь в магазине "дайте мне b.e кило колбасы", вместо того, чтоб сказать 2.5 кило?? Эта информация существенно цифровая! Она определяет номер позиции в упорядоченном множестве. 321 - 132. DCBAE - AEDCB (43215 - 15432) Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка. Перестановки должны содержать только цифры. Больше ничего, кроме цифр. Я имею в виду то определение перестановки, которое приведено тобой раньше. А что касается сравнения перестановок на больше/меньше, то это выходит (в соответствии с приведенным тобой определением) простое сравнение чисел, если просто считать перестановки числами в n-ричной системе счисления. И если n<10, то простой взгляд на перестановки, как на числа, сразу дает ответ.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Cheburashka |
19.07.2009 13:14
Сообщение
#24
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация: 2 |
321 > 132.
43215 > 15432 Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится))) Скажите правильно ли я понял циклическую перестановку по этим примерам -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
Lapp |
19.07.2009 13:28
Сообщение
#25
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
321 > 132. Вроде правильно.. Но немного странно, что у тебя сомнения. В таком простом вопросе сомнений быть не должно)). Циферки сзади переносишь вперед, k раз - вот и все. 43215 > 15432 Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится))) Скажите правильно ли я понял циклическую перестановку по этим примерам Трудно верится. Приведи, плз. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Cheburashka |
19.07.2009 13:31
Сообщение
#26
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация: 2 |
http://acmp.ru/index.asp?main=task&id_task=350
К примеру вот) Ну там частично идёт речь о перестановках. Ну так сказать спасибо Вам, если у меня будут в дальнейшем вопросы по этой теме, буду Вас просить о помоще. -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
Lapp |
19.07.2009 13:50
Сообщение
#27
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
К примеру вот) Ну там частично идёт речь о перестановках. Сергей, ты путаешь различные понятия.В этом примере перестановкой называется само упорядоченное множество, точнее - его конкретное воплощение. В изначальном же условии авторы задачи ввели свое собственное определение некоторого объекта, который назвали перестановкой. Надо сказать, что это название в данной ситуации вполне логично, и упрекать авторов задачи не нужно. Само слово "перестановка" проискодит от глагола "переставлять" и может выражать как само действие переставления ("не могу пойти гулять - у нас дома перестановка мебели"), так и его результат ("как вам нравится наша новая перестановка?"). Посмотри в словаре, наверняка там есть оба значения. Так вот, в изначальном условии перестановка понимается как действие (потому мы и называли ее операцией), а в твоей последней ссылке - как результат (в данном случае ищутся различные результаты всех возможных операций по перестановкам). Постарайся улавливать подобные различия, в математике это очень важно. Если в задаче приведено определение какого-то понятия - сразу подозревай, что тут подвох, и полностью действуй по нему, даже если оно отличается от общепринятого. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Cheburashka |
21.07.2009 10:36
Сообщение
#28
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация: 2 |
Цитата Назовем перестановку из N чисел 1…N K-перестановкой, если любые два соседних в ней элемента отличаются не более, чем на K. Требуется найти число K-перестановок из N чисел от 1 до N. В общем нашёл ещё одну интересную задачку на перестановки, и хотел бы спросить у Вас кое-что. Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1). А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи? -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
Lapp |
22.07.2009 1:26
Сообщение
#29
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1). Сергей, когда ты уже научишься наконец правильно ставить задачу и правильно выбирать раздел? Я всегда рад помочь (если могу), но следить за правильным наполнением Форума - моя обязанность (почетная)). Если воспринимать эту задачу как математическую и решать чисто аналитически (то есть вывести общую формулу), то это одно (и, думаю, это ооочень непросто). Но ты забыл сказать, что задачу-то нужно решать численно, т.к. она взята с олимпиады по информатике. И в этом случае она должна быть в разделе Задачи (переносить я не буду - замучился уже)). Я понимаю, что тема типа та же, но ты пойми, что комбинаторика - это целая большая отрасль математики. Как и в других областях, в ней есть задачи, которые решаются аналитически, и есть, которые численно. И не нужно всю ее лепить в одну тему. Выяснил основы предмета - решаешь задачи. Нужно выяснить еще что-то по ее теории - вернись сюда...А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи? Объяснять тут численное решение не буду, флуд это. Надо - создай тему там, где надо. И приведи условие полностью (с ограничениями на N). Но могу сказать некое чисто аналитическое соображение: при любом N число 1-перестановок (то есть К=1) всегда равно 2. Это следует из того, что в этом случае годятся только восходящая и низходящая расстановки, больше никакие. Для других значений К (например, 2), все значительно усложняется Еще, проверяй свои мессаджи на предмет ошибок, плз. Мне кажется, должно быть так: Цитата Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (1, 2, 3) и (3, 2, 1). Ну, а как объяснить, что для N=4, К=2 получается 12? Вот так, например: 1 2 3 4 2 1 3 4 1 3 2 4 .. 3 1 2 4 .. 1 3 4 2 1 2 4 3 4 3 2 1 3 4 2 1 4 2 3 1 .. 2 4 3 1 .. 4 2 1 3 4 3 1 2 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 10.06.2024 13:04 |