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

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V < 1 2  
 Ответить  Открыть новую тему 
> Перестановки, Объясните [перемещено]
сообщение
Сообщение #21


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Сергей Меркурьев @ 19.07.2009 13:33) *
В принципе вот условие)
А в принципе, в чем проблема? ))

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

Цитата
Петей порядка 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. Отметим, что любой циклический сдвиг Пети также является Петей.

Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданного Пети

Как тебе такое? И короче вышло.. Извиняюсь, рука не поднялась писать Петя с маленькой буквы))).

Так в чем проблема? Дан Петя. Сдвигаешь его циклически и ищешь минимального.. Что именно непонятно?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #22


Бывалый
***

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

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


Тогда я так сказать приведу пару своих примеров и вы скажите правильно ли я это понимаю:
Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав?
Или вот ещё пару
321 - 132.
DCBAE - AEDCB (43215 - 15432)
Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка.


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #23


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Сергей Меркурьев @ 19.07.2009 13:51) *
Есть к примеру перестановка 4213, лексиграфически меньшая получается здесь будет 1342. Я прав?
Прав, Петя 4213 > Петя 1342.

Цитата(Сергей Меркурьев @ 19.07.2009 13:51) *
Или вот ещё пару
321 - 132.
DCBAE - AEDCB (43215 - 15432)
Если мои рассуждения не верны, скажи тогда как именно правильно будет выглядеть данная перестановка.
А тут я ничего не понял wacko.gif . Зачем знак "минус"? Если хочешь сказать, кто больше/меньше, используй > или <. И ЗАЧЕМ ты перевел в буквы?? Это же внесет страшную путаницу, когда (и если) ты будешь действительно пользоваться ими как перестановками. Ты, что, действительно говоришь в магазине "дайте мне b.e кило колбасы", вместо того, чтоб сказать 2.5 кило?? blink.gif Эта информация существенно цифровая! Она определяет номер позиции в упорядоченном множестве.

Перестановки должны содержать только цифры. Больше ничего, кроме цифр. Я имею в виду то определение перестановки, которое приведено тобой раньше.

А что касается сравнения перестановок на больше/меньше, то это выходит (в соответствии с приведенным тобой определением) простое сравнение чисел, если просто считать перестановки числами в n-ричной системе счисления. И если n<10, то простой взгляд на перестановки, как на числа, сразу дает ответ..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #24


Бывалый
***

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

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


321 > 132.
43215 > 15432

Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится)))
Скажите правильно ли я понял циклическую перестановку по этим примерам


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #25


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Сергей Меркурьев @ 19.07.2009 14:14) *
321 > 132.
43215 > 15432

Я имел ввиду это) А что по поводу букв, то я видел такие задачи! Могу конечно привести пример если чуть трудно верится)))
Скажите правильно ли я понял циклическую перестановку по этим примерам
Вроде правильно.. Но немного странно, что у тебя сомнения. В таком простом вопросе сомнений быть не должно)). Циферки сзади переносишь вперед, k раз - вот и все.

Трудно верится. Приведи, плз.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #26


Бывалый
***

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

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


http://acmp.ru/index.asp?main=task&id_task=350
К примеру вот) Ну там частично идёт речь о перестановках. Ну так сказать спасибо Вам, если у меня будут в дальнейшем вопросы по этой теме, буду Вас просить о помоще. good.gif


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #27


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Сергей Меркурьев @ 19.07.2009 14:31) *
К примеру вот) Ну там частично идёт речь о перестановках.
Сергей, ты путаешь различные понятия.

В этом примере перестановкой называется само упорядоченное множество, точнее - его конкретное воплощение. В изначальном же условии авторы задачи ввели свое собственное определение некоторого объекта, который назвали перестановкой. Надо сказать, что это название в данной ситуации вполне логично, и упрекать авторов задачи не нужно. Само слово "перестановка" проискодит от глагола "переставлять" и может выражать как само действие переставления ("не могу пойти гулять - у нас дома перестановка мебели"), так и его результат ("как вам нравится наша новая перестановка?"). Посмотри в словаре, наверняка там есть оба значения. Так вот, в изначальном условии перестановка понимается как действие (потому мы и называли ее операцией), а в твоей последней ссылке - как результат (в данном случае ищутся различные результаты всех возможных операций по перестановкам).

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 или разъяснить основную суть задачи?


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #29


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Сергей Меркурьев @ 21.07.2009 11:36) *
Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1).
А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи?
Сергей, когда ты уже научишься наконец правильно ставить задачу и правильно выбирать раздел? smile.gif Я всегда рад помочь (если могу), но следить за правильным наполнением Форума - моя обязанность (почетная)). Если воспринимать эту задачу как математическую и решать чисто аналитически (то есть вывести общую формулу), то это одно (и, думаю, это ооочень непросто). Но ты забыл сказать, что задачу-то нужно решать численно, т.к. она взята с олимпиады по информатике. И в этом случае она должна быть в разделе Задачи (переносить я не буду - замучился уже)). Я понимаю, что тема типа та же, но ты пойми, что комбинаторика - это целая большая отрасль математики. Как и в других областях, в ней есть задачи, которые решаются аналитически, и есть, которые численно. И не нужно всю ее лепить в одну тему. Выяснил основы предмета - решаешь задачи. Нужно выяснить еще что-то по ее теории - вернись сюда...

Объяснять тут численное решение не буду, флуд это. Надо - создай тему там, где надо. И приведи условие полностью (с ограничениями на 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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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