0
1

У Васи есть ряд чисел от 1 до 10: 1 3 2 7 8 9 10 4 5 6 Вася захотел упорядочить этот ряд по возрастанию следующим способом: он решил случайным образом равновероятно взять два числа и, если первое из них больше второго, поменять эти два числа местами.Вася продолжил выполнять эту операцию (случайно выбирать два числа и, если необходимо, менять их местами) N раз до тех пор, пока не массив не станет упорядочен по возрастанию. Так как пары чисел выбираются случайным образом, то N это случайная величина. Найдите ее математическое ожидание.

задан 21 Сен 23:36

изменен 22 Сен 0:39

1

@MrNoName: у Вас тут число 6 куда-то пропало в перестановке.

Вручную решить вряд ли получится, а с помощью рекурсивной процедуры -- вполне.

(22 Сен 0:39) falcao

@falcao А можно по подробнее про алгоритм, а то я уже достаточно долго решаю и не могу никак решить...

(22 Сен 0:40) MrNoName

Автор, ты решил задачку? Я с ней тоже мучаюсь две недели уже... помоги!)

(27 Сен 5:04) Alyona

Лимиты на комментарии везде исчерпаны, поэтому даю ответ на вопрос @kirill_egorov здесь. Только предлагаю на этом завершить, так как нельзя же сутками ходить по одному и тому же месту!

Итак, значение f зависит от перестановки, а не только от числа инверсий в ней. Для перестановки z строим все, которые получаются из неё переставлением символов. Количество инверсий при этом всегда уменьшается. Для всех перестановок с меньшим числом инверсий мы всё подсчитали ранее. Осталось подставить в рекуррентную формулу.

(27 Сен 23:55) falcao
-1

@kirill_egorov Не мог бы ты скинуть код для этой задачи, если у тебя получилось её сделать? @falcao @mrNoName К вам тот же вопрос?

(28 Сен 14:51) Unioltered

@Unioltered: я писал программу в Maple чисто для себя, это "сырой" продукт. Поэтому использовать его вряд ли имеет смысл. Надо написать программу заново (алгоритм был описан в комментариях), и независимо всё перепроверить. И вообще, я так понимаю, что это задание из какого-то соревнования по программировании, а не по списыванию :)

(28 Сен 18:30) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

Вот как составляются рекуррентные формулы.

Если перестановка z имеет k>=1 инверсий, то рассматриваем перестановки z(1), ... , z(k) после применения каждой из транспозиций. Эти перестановки имеют меньше инверсий, и для них по рекурсии мы матожидание знаем.

Обозначим через f(z) матожидание для перестановки z. Каждая из k пар выпадает с вероятностью 1/45. С вероятностью (45-k)/45 нам попадётся пара без инверсии. Перестановка останется той же, и за счёт одного "холостого" шага, среднее число ходов станет равно f(z)+1. Также надо прибавить 1 к каждому из f(z(i)). Отсюда

f(z)=(f(z(1))+...+f(z(k))+k)/45+(45-k)(f(z)+1)/45.

После упрощений имеем f(z)=(f(z(1))+...+f(z(k))+45)/k.

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

Можно не делать всё целиком, а для данной в условии перестановки выписать постепенно множество всех "нисходящих", а потом разметить вершины полученного подграфа по тому же принципу.

ссылка

отвечен 22 Сен 1:15

изменен 27 Сен 0:39

@fallao а код программы можно?

(22 Сен 1:22) MrNoName

@MrNoName: это была программа для Maple. Она пишется за пару минут, но в таком виде медленно работает. А улучшать мне было уже неохота.

(22 Сен 2:07) falcao

@falсao спасибо большое!)

(22 Сен 2:17) MrNoName

Это легко делается, погуглите как найти кол-во инверсий в перестановке. А задачка решается достаточно легко через графы

(26 Сен 20:51) MrNoName

@kirill_egorov: нахождение инверсий в перестановке -- вещь совсем элементарная. Особенно на фоне достаточно сложной задачи. Достаточно для каждого символа найти количество меньших, стоящих после него, а потом всё сложить.

Все 10! перестановок тут рассматривать не нужно. Число инверсий может лишь уменьшаться.

(26 Сен 21:42) falcao

@kirill_egorov: тогда имело смысл спросить, а что понимается под инверсиями? Хотя при рассмотрении перестановок это одно из самых стандартных понятий. Вы задали вопрос так, как будто смысл понятия Вам известен, и непонятно лишь то, как их находить.

(26 Сен 22:10) falcao

@kirill_egorov: понятие инверсии обычно изучается на первом курсе -- когда проходят определители. Это не имеет отношения к вероятности.

Инверсией называется пара чисел, идущих в перестановке не в порядке следования.

Для случая k=1, который тут рассмотрен, ответ 44. Для случая k=2 должно быть две перестановки: z(1) и z(2). Для z(1) переставляем 10 и 8, для z(2) -- 10 и 9.

(26 Сен 23:24) falcao

@falcao f(z(2)) = 44/2 + 43/2 = 43.5 - это верный ответ? Просто я решил погуглить может такая задача или похожая есть где-нибудь и нашёл на другом форуме такую же задачу, вроде даже от того же человека и там код кидали для этой задачи: https://rextester.com/TWPKU43350. И там ответы другие для [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] ответ близок к 45, а не 44. А для второго примера вроде как 67.5, а не 43.5, может я что-то упускаю. Вот у меня и встаёт вопрос, а что из этого правильно и можно ли решить эту задачу таким образом, как у вас, а не используя имитацию случайного выбора (там функция rand() используется)

(26 Сен 23:31) kirill_egorov

@kirill_egorov: для одной инверсии ответ вообще-то 45, что ясно из общих соображений (если вероятность успеха p, то ждать надо в среднем 1/p).

В рекуррентной формуле сейчас заметил у себя ошибку -- там не учтено, что при переходе к z(i), один шаг мы уже сделали. Сейчас исправлю.

(27 Сен 0:34) falcao

@falcao а не подскажете как мне писать не ответ, а комментарий, или не к своему ответу я не могу его писать?

(27 Сен 0:39) kirill_egorov

@kirill_egorov: там есть надпись "добавить комментарий".

(27 Сен 0:40) falcao

Дак Как найти этот N ? Я знаю, как найти инверсии. Но как найти N. без понятия. Уже 3 недели решаю задачу, перепробовала десятки способов. Какая формула тут будет рабочей? Какая рекурсия? Например, если у нас 5 инверсий, или 7. Как конкретно посчитать по формуле? Спасибо!

(27 Сен 17:01) Ksana

@Ksana: здесь нет какой-либо простой итоговой формулы, и искать её бесполезно. Считать должен компьютер. Рекуррентная формула позволяет выразить м.о. для случая, скажем, 5 инверсий, через случаи с меньшим числом инверсий. Это значит, что перед нахождением значения для 5, мы должны знать ответы для подстановок с количеством инверсий 0, 1, ... , 4. Для этого составляется таблица, и постепенно заполняется от меньшего числа инверсий к большему.

(27 Сен 18:53) falcao
показано 5 из 13 показать еще 8
10|600 символов нужно символов осталось
0

@falcao у меня почему-то эта кнопка больше не показывается, один или два раза была.

Таак, после изменения формулы для k = 2 получается:

f(z) = (45 + 45) / 2 что ли?)

И ещё, а почему в этой формуле:

f(z)=(f(z(1))+...+f(z(k))+45)/k.

вычисляя f(z) мы в формуле имеем ещё и f(z(k)) они разве не равны будут?

ссылка

отвечен 27 Сен 0:43

изменен 27 Сен 1:44

@kirill_egorov: здесь имеется лимит на число комментариев. Больше восьми под одним ответом оставить нельзя.

Для перестановки z с одной инверсией получается 45. Если у z инверсий было две, то из неё получаются z1 и z2 с одной инверсией. Тогда по формуле получится (45+45+45)/2 -- обратите внимание на дополнительное слагаемое. Но если инверсий было три, то ситуация усложняется. Скажем, если было 321..., то после перестановки 3 и 2 инверсий две, то же для перестановки 2 и 1. Однако если переставить 3 и 1, то инверсий станет 0. Чем дальше, тем больше всё усложнится.

(27 Сен 2:09) falcao

Не могу понять вообще каким алгоритмом можно это всё считать. Сразу говорю теории графов у меня в программе вообще нет, как ни странно

Ведь если k = 4 [1, 2, 3, 4, 5, 10, 6, 7, 8, 9], то там возможно 4 разных перестановки, которые выходят в z с 3 перестановками, которые выходят в z с двумя...

То это получается [ ( + 45 ] / 4 =

(27 Сен 2:52) kirill_egorov

@kirill_egorov: это и не надо понимать, так как оно сложно устроено. Это задача не по математике, а по программированию. О чём, кстати, надо было сразу сказать в тексте вопроса.

Алгоритм тут рекурсивный. Для перестановок с меньшим числом инверсий всё должно быть уже сосчитано.

(27 Сен 3:02) falcao

Ааааааааааааааааа я поняяяяяял. Только не понял как можно с теорией графов это связать. У меня её не было и не будет вроде как, но что-то про неё слышал. Без неё я так понимаю в худшем случае надо будет перебирать 10! (k = 45), ручками это точно не сделаешь ))) Хотя прии должном желании...

(27 Сен 5:23) kirill_egorov

@falcao спасибо, я правда уже не уверен, что преподу по тер.веру она нужна будет, но всё же расскажу ему))

(27 Сен 5:39) kirill_egorov

@kirill_egorov: тут из теории графов не используется ничего. Речь всего лишь об иллюстрации. Реализуется это так: сначала компьютер генерирует все "младшие" перестановки (их будет не 10!, а поменьше), потом размечает их от меньшего числа инверсий к большему. Это совершенно общий приём, который также используют при анализе игр, и так далее. Вручную тут не надо даже пытаться решать.

(27 Сен 11:07) falcao

@falcao как-то сложно это представить на самом деле

(27 Сен 15:48) kirill_egorov

@kirill_egorov: по-моему, Вы пытаетесь охватить в целом сложную ситуацию. Но это сделать нельзя. А общая идея тут совсем простая. Другое дело, что считать должен не человек, а компьютер. Подстановок там используется реально чуть больше двух тысяч.

(27 Сен 16:57) falcao

@falcao потому что они постоянно повторяются при больших k?

Накидал я программку под эту задачу, для значений k <= 6 считает вроде правильно, а если запустить [10 -> 1], то она очень долго считает и я так и не дождался ответа )))) Не имею понятие как можно сделать её быстрее

(27 Сен 17:20) kirill_egorov

@kirill_egorov: отвечаю на Ваш вопрос, но не хотелось бы потом снова возвращаться к этой задаче. Алгоритм такой: сначала выписываем те подстановки, которые получаются из данной применением одной из транспозиций. Их там совсем немного. Смотрим, сколько у каждой из них будет инверсий. Если их s, то запоминаем подстановку в s-м множестве. У нас возникают множества S(i) при i от 13 до 0 (подстановок с i инверсиями, возникающими из данной). Их вместе около 2 тысяч. Далее, начиная снизу, то есть с i=0, для каждой подстановки находим матожидание. По рекурсии, ответы последовательно выражаются.

(27 Сен 19:00) falcao

@falcao подстановки = перестановки? или это не опечатка

(27 Сен 21:08) kirill_egorov

@kirill_egorov: подстановки и перестановки -- почти одно и то же. См. учебники.

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

(27 Сен 21:30) falcao

@falcao Раз спросил надо ведь мне довести до конца задачку уже. Тем более, что осталось только алгоритм понять, попробовать реализовать и всё на этом будет

(27 Сен 21:36) kirill_egorov

@falcao, не хотел Вас возвращать к этой задачке, но есть некоторые детали, по которым хотелось бы узнать Ваше мнение. А именно, мы можем сразу отбросить первые три элемента (учесть одну транспозицию) и перейти к анализу подстановки 4, 5. 6.7, 1.2.3. Индукция не получается и подстановки плодятся «какие-попало», но на первых 3-х шагах их не так много с учетом дублирования. Кроме того, появляются варианты с левыми единицами и правыми семерками, что позволяет сократить размерность. Программировать, конечно, сейчас не берусь – нет времени (отложу «на потом»).

(27 Сен 21:48) Urt

... Если бы трактовать в задаче «если необходимо» как (pi>pj) и (pi=j или pj=i), то, наверное, задача упростилась (бы).

(27 Сен 21:48) Urt

@Urt: я думаю, что мелкие улучшения тут ничего не дадут -- программа окажется ещё длиннее.

Я на скорую руку что-то составил, так как интересно было узнать ответ. Он примерно равен 123, что меня немного удивило (я думал, будет побольше), но это желательно независимо перепроверить.

(27 Сен 22:20) falcao
показано 5 из 16 показать еще 11
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×3,042
×184

задан
21 Сен 23:36

показан
646 раз

обновлен
28 Сен 18:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru