Здравствуйте. На выходных читал Stiven S. Skiena ADM, встретил несколько задач. Некоторые совершенно простые, но тем не менее попадались интересные.
Например задача 2-45. Вероятно правильный ответ , получается как частичная сумма гармонического ряда (вероятностей того, что текущий элемент будет меньше уже пройденных), однако с другой стороны, если сравнивать текущий элемент только с текущим минимумом можно получить , что вероятно не верно. Однако почему оно не верно и как это объяснить языком теории вероятности я не знаю.

Задача 2-43 интересная, но как решить её мне неизвестно. Вероятно нужно использовать некую функцию в которой присутствует n и k, хотя возникает вопрос, как при просмотре последнего элемента в исходном множестве, в том случае если в целевом множестве не будет хватать одного элемента вероятность может быть меньше 100%.
Если у вас есть идеи по поводу этих задач, было бы интересно послушать.

Вообще для задачи 2-43 я бы использовал метод Монте-Карло, это был бы идеальный вариант, но вероятно предполагается последовательный перебор элементов

tanglirЧто-то я 43 вообще не понял. Выбрать k элементов из множества в n элементов, чтобы вероятность выбора каждого была k/n? Так она и будет k/n, какие бы элементы мы ни выбрали...

Дано множество . Необходимо заполнить множество элементами из множества S. При этом вероятность того, что каждый элемент из S будет принадлежать подмножеству должна быть одинакова. Вы можете сделать только один проход по элементам множества S чтобы заполнить целевое подмножество.

Должно быть примерно следующее

Кроме того, скорее всего в так называемой probability function будет участвовать счётчик прохода и текущая наполненность множества S'.

tanglirSashaMercuryесли сравнивать текущий элемент только с текущим минимумом можно получить это как? текущий минимум ведь зависит от предыдущих элементов.

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

tanglirSashaMercuryПри этом вероятность того, что каждый элемент из S будет принадлежать подмножеству должна быть одинакова.Что тут подразумевается под "вероятностью"?

что у каждого элемента одинаковые шансы попасть в спасительную шлюпку S'

tanglir>тогда вероятность будет 0.5
В задаче же ни слова о динозаврах, да и вы, наверное, не блондинка - откуда же такие предположения?
>Если так делать нельзя, то как это объяснить нормальным языком теории вероятности
Зависимые/независимые события .
SashaMercuryчто у каждого элемента одинаковые шансы попасть в спасительную шлюпку S'То есть вся соль в "n is unknown". Тогда да, интересная задачка.

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

SashaMercury,

а если n известен ? Тут всё просто ?

tanglirSashaMercury, ну на объём используемой памяти ограничений же нет. Генерируем массив с нужным количеством различных случайных чисел (от 1 до n), потом в один проход... эээ... проходим по исходному множеству и выбираем элементы с соответствующими номерами.

ну а если сгенерируются одинаковые случайные числа ?

'массив с нужным количеством различных случайных чисел '
Как такое сделать ?

Dima TSashaMercuryну а если сгенерируются одинаковые случайные числа ?
игнорируй повторы

Тогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?

Dima TSashaMercuryТогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?
Насколько я знаю нет ГСЧ без повторов, рано или поздно повторы будут. Так что другого нет.

Изобретай наиболее оптимальный способ отлова повторов:
1. Биткарта. Работает быстро, но при большом диапазоне займет много места.
2. Заполняешь, сортируешь, в один проход проверяешь на повторы, заменяя повторы на новые случайные, затем снова сортируешь, проверяешь и т.д. пока проверка не покажет что повторов нет. Лишнего места не займет, но будут затраты на сортировку.

проход только один. Предполагается именно цикл по элементам, и какая-то функция, сомневаюсь что корректное решение такое

maytonПоскольку официальный язык форума - русский я настоятельно рекомендую
сейчас, и впредь использовать 2 варианта постановки задачи. А именно:

1) Оригинал на иностранном .
2) Русскоязычный перевод постановки топик-стартера приближённый
к оригиналу настолько насколько это возможно.

Игнорирование этого правила - я считаю лицемерием и попыткой показать
своё умственное превосходство над остальными.

Надеюсь мой посыл будет услышан.

Аргументация тут следующая, 1) английский тут совершенно не сложный, 2) любой IT-специалист должен знать английский язык на таком уровне, 3) и я уже как-то говорил о том, чем москвич отличается от деревни(мне она больше нравится, кстати), он не стесняется спросить как пройти на какую-нибудь Волхонку 20 или куда-нибудь ещё. Ну и в конце концов, если непонятно кому-то, пусть человек попросит, переведут. У нас в Сообществе(CPP, конечно), целый топик, где я задаю вопросы о том как перевести те или иные вещи из стандарта. ... 'лицемерием и попыткой показать своё...' вы знаете что это не так, Марк.

К следующим задачам(наиболее трудным для понимания) добавлю перевод, к этим смысла уже нет, одна совсем простая, а другую уже перевел выше

maytonНа том спасибо.
ну ладно вам. Лучше бы предложили какую идею :)