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

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

Здравствуйте, sdf, Вы писали:

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

Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

Здравствуйте, Caracrist, Вы писали:

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды.

Что-нибудь еще вы не забыли упомянуть? Например, то, что лотерея идет в прямом эфире, в исходном условии не было.

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

Сгенерировать 1 номер и опубликовать его. Выбрать человека с таким же или максимально похожим номером паспорта.

Например, человека с номером 1234567890 нет, значит ищем человека с номером 123456789х. Если опять нет, ищем человека с номером 12345678хх. Если таких людей несколько (их будет не более 9), провести среди них жребьёвку.

Здравствуйте, uuu84, Вы писали:

U>Сгенерировать 1 номер и опубликовать его. Выбрать человека с таким же или максимально похожим номером паспорта.

U>Например, человека с номером 1234567890 нет, значит ищем человека с номером 123456789х. Если опять нет, ищем человека с номером 12345678хх. Если таких людей несколько (их будет не более 9), провести среди них жребьёвку.

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

Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

это же частный случай задачи -- имея равномерный генератор целых чисел 1..N сгенерирвать равномерное целое 1..M
Понятно, что если N и M взаимно просты, то за гарантированно ограниченное число шагов равномерное целое 1..M сгенерировать нельзя

Здравствуйте, uuu84, Вы писали:

U>Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

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

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

т.к. здесь паспорта 10 ти значные и победитель один, то это будет работать. но только при условии, что номера распределены по диапазону равновеоятно, в чем я сильно сомневаюсь (но таковы условия задачи).

Здравствуйте, uuu84, Вы писали:

U>Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.
И как предполагается искать этих двух кандидатов? Если кто-то заявит, что его паспорт достаточно близок к сгенерированному числу, нет гарантии, что завтра не найдется другой, у кого он еще ближе, а он просто не успел об этом заявить.

Здравствуйте, Caracrist, Вы писали:

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

А если не сто, а 10?
1. Кидаем шарик в диапазоне [0..9] — это будет первая цифра в номере.
2. Кидаем ещё раз — это будет вторая.
И ... Упс! Выйдем ли мы на номер?

Здравствуйте, Caracrist, Вы писали:

C>Здравствуйте, sdf, Вы писали:

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

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

1. Сгенерировать 10-тизначное число [N1...N10]
2. Проверить, есть ли паспорт с таким номером. Если есть — конец
3. Путем последовательной замены цифр выпавшего числа и проверки на существование паспорта с таким номером, собрать все паспорта, отличающиеся от выпавшего числа на 1 в одном из знаков. Если кандидатов несколько — выбрать из них одного случайно или по заданной процедуре, например:
— приоритет получает номер, у которого отличается младший разряд, например [N1...(N10+1)] предпочительнее чем [N1...(N9+1) N10]
— при равенстве номера отличающегося разряда, приоритет получает меньший номер, т.е. [N1...(N9-1) N10] предпочительнее чем [N1...(N9+1) N10]
4. Если в п.3 ни одного паспорта не найдено, аналогично ищутся все паспорта отличающиеся на 2 в одном разряде, на 3 и т.д. ... потом в двух разрядах и т.д. до нахождения победителя, что неизбежно.

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

ну не будет справедливого распределения хоть ты тресни (если число владельцев паспортов не является редким круглым числом).

Потому что это частный случай известной задачи -- сгенерировать равномерно распределенное случайное 1..M если в наличии есть генератор равномерно распределенных 1..N.
Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).

Здравствуйте, dilmah, Вы писали:

D>ну не будет справедливого распределения хоть ты тресни (если число владельцев паспортов не является редким круглым числом).

D>Потому что это частный случай известной задачи -- сгенерировать равномерно распределенное случайное 1..M если в наличии есть генератор равномерно распределенных 1..N.
D>Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).

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

Здравствуйте, dilmah, Вы писали:


D>это же частный случай задачи -- имея равномерный генератор целых чисел 1..N сгенерирвать равномерное целое 1..M
D>Понятно, что если N и M взаимно просты, то за гарантированно ограниченное число шагов равномерное целое 1..M сгенерировать нельзя
В этой задаче N и M известны и не являются взаимно простыми

Здравствуйте, dilmah, Вы писали:

D>ну не будет справедливого распределения хоть ты тресни (если число владельцев паспортов не является редким круглым числом).

D>Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).
Вообще-то по условию N как раз кратно M

А>с точки зрения обывателя, в чём несправедливость? Кто получает изначальное преимущество или как его можно получить?

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

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

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

sdf>В этой задаче N и M известны и не являются взаимно простыми

ок, я думал, что они составляют _приблизительно_ одну пятидесятую.
Если ровно, то все хорошо, удивительно точная страна, Швейцария наверно

sdf>И как предполагается искать этих двух кандидатов? Если кто-то заявит, что его паспорт достаточно близок...

...его заявку берут на учёт. Сбор заявок заканчивается через 30 дней, и определяется победитель. Кто не успел — тот опоздал.

Здравствуйте, uuu84, Вы писали:

sdf>>И как предполагается искать этих двух кандидатов? Если кто-то заявит, что его паспорт достаточно близок...

U>...его заявку берут на учёт. Сбор заявок заканчивается через 30 дней, и определяется победитель. Кто не успел — тот опоздал.
А почему через 30 дней, а не через 3 или, скажем, 3,1415?