Ваша программа / функция должна
- вывести ровно одно целое число
- выведите любое целое число с положительной вероятностью
- выведите целое число больше 1.000.000 или меньше -1.000.000 с вероятностью не менее 50%.
Пример выходов (все должно быть возможно):
59875669123
12
-42
-4640055890
0
2014
12
24
-7190464664658648640055894646646586486400558904644646646586486400558904646649001
Разъяснения:
- Разрыв трейлинга разрешен.
- Ведущие нули не допускаются.
-0
разрешено
Самый короткий код выигрывает.
way too long to fit in an integer
- Это верно только в том случае, если вы предполагаете, что этоinteger
означаетint
тип данных в 32/64- битной арке, что не обязательно является допустимым предположением. «Integer» начинался как математический термин , который не имеет ограничений по размеру.Ответы:
CJam,
161413 байтЭто будет выполняться очень долго, потому что он использует текущую временную метку (порядка 10 12 ), чтобы определить, должен ли цикл завершиться. Я использую это как представление, поскольку оно самое короткое, но есть две 14-байтовые альтернативы, которые имеют свои достоинства:
Этот не ограничен периодом PRNG, так как диапазон всех случайных чисел зависит от текущей метки времени. Следовательно, это должно быть в состоянии произвести любое число, хотя вероятность отрицательных или даже небольших положительных чисел исчезающе мала.
Ниже приведена эквивалентная версия, которая использует
3e5
вместо отметки времени. И20
для первого диапазона (как 13-байтовое представление). Это намного быстрее, а также соответствует всем правилам. Это своего рода ограничивающий случай - получить 50% вероятности для чисел, превышающих 1 000 000, при сохранении разумного времени выполнения и небольшого размера кода. Объяснение и математическое обоснование относятся к этой версии:Обычно это занимает несколько секунд, чтобы бежать. Вы можете заменить
5
с2
на, чтобы он работал еще быстрее. Но тогда требование о 50% вероятности будет выполнено только для 1000 вместо 1 000 000.Я начинаю с 0. Затем у меня есть цикл, из которого я вырываюсь с вероятностью 1 / (3 * 10 5 ). В этом цикле я добавляю случайное целое число от -1 до 18 (включительно) к моему промежуточному итогу. Существует конечная (хотя и небольшая) вероятность того, что каждое целое число будет выведено, причем положительные целые числа гораздо более вероятны, чем отрицательные (я не думаю, что вы увидите отрицательное целое в своей жизни). Разрыв с такой малой вероятностью и увеличение в большинстве случаев (и добавление гораздо большего, чем вычитание) гарантирует, что мы, как правило, выйдем за пределы 1 000 000.
Некоторое математическое обоснование:
Вероятность того, что мы сделаем меньше этого количества шагов,
который оценивает
0.324402
. Следовательно, примерно в двух третях случаев мы предпримем более 117 647 шагов, и каждый из них легко будет составлять 1 000 000.9e9
не добавляя байтов (кроме лет времени выполнения).... или 11 байт?
Наконец, есть 11-байтовая версия, которая также не ограничена периодом PRNG, но у которой почти всегда будет не хватать памяти. Он генерирует только одно случайное число (на основе метки времени) каждой итерации и использует его как для увеличения, так и для завершения. Результаты каждой итерации остаются в стеке и суммируются только в конце. Спасибо Деннису за эту идею:
источник
Kmr
период, скорее всего, всегда будет большим положительным числом, большим, чем период. И это не может произвести все возможные числа в этом случае.Ява,
133149Пример выходов
Ungolfed
Старый ответ (до изменения правила)
источник
-
.Mathematica - 47
В основном, просто сгенерируйте случайное число, используя нормальное распределение с дисперсией, равной 1500000. Это даст целое число от -10 ^ 6 до 10 ^ 6 с вероятностью 49,5015%.
источник
Python 2,
7569 байтТривиально проверить, что цикл while в середине может генерировать все целые числа (хотя и смещенные к нулю). «12» выбирается таким образом, чтобы примерно половина чисел превышала ± 10 6 .
Старое решение:
Python 2, 44 байтаОсновано на решении Mathematica .На самом деле не работает, потому что Python
float
имеет только конечную точность.источник
Руби, 70
Чтобы сделать возможным генерирование очень больших чисел, я возвращаю число в
String
виде лямбды. Если это не разрешено, считайте 8 дополнительных символов (дляputs f[]
), чтобы сделать его программой, а не функцией.объяснение
Генерация числа между
-1,000,000
и1,000,000
. Если число больше1
или равно , номер возвращается какString
.Если число меньше чем
1
, функция вызывается рекурсивно, чтобы вернуть число вне диапазона номеров. Чтобы убедиться, что отрицательные числа также могут быть сгенерированы,-
перед результирующимString
будет добавлен префикс a, если начальное число больше, чем-500,000
.Надеюсь, я правильно понял задачу!
источник
Р, 38
Тяги из распределения Гаусса со средним значением 2 000 000, выбранным случайным образом, и стандартным отклонением 1 000 000, так что около 2/3 тиражей будут находиться в пределах 1 000 000 и 3 000 000 Распределение не ограничено, поэтому в теории это может генерировать любое целое число. Пакет Rmpfr заменяет R встроенные двойные числа с произвольной точностью.
источник
sample(c(1,-1),1)
думать, хотя. Достаточно просто центрироваться на 1e6 ..Perl, 53 символа
Я, конечно, не вижу смысла работать с целыми числами при печати одного :)
Имеет одинаковую вероятность печати числа с или без начального "-".
Печатает 1-значное число в 10% случаев, 2-значное число в 9% случаев, 3-значное число в 8,1% времени, 4-значное число в 7,29% времени, 5-значное число 6,56% времени, 6-значное число 5,9% времени и т. Д. Возможна любая длина с уменьшающейся вероятностью. Числа, состоящие из одной-пяти цифр, составляют около 41,5% выходных данных, а число 1 000 000 (или -1 000 000) - только 6 миллионов долей процента, поэтому выходное число будет выходить за пределы диапазона от 1 000 000 до 1 000 000, около 54,6. % времени.
И «0», и «-0» являются возможными выходами, что, я надеюсь, не является проблемой.
источник
print int(rand(20)-10)||1
, Мне нужен способ генерировать 0 в качестве вывода, хотя. Может быть || умрет 0, если разрешен завершающий мусор после нуля. Иначе нужен короткий способ напечатать ноль и выйти без дальнейшего вывода ifint(rand(20)-10)==0
.Perl, 114 символов
Сломать:
Вероятность получения значения между -1.000.000 и 1.000.000 стремится к нулю, НО это возможно.
Perl, 25Генерирует случайное целое число в диапазоне +/- 2 ^ 99.
Сломать
Протестировано с 1 миллионом образцов:
Это соответствует всем правилам:
Редактировать:
Мне пришлось увеличить показатель степени, чтобы генерировались большие целые числа. Я выбрал 99, потому что он делает код максимально коротким.источник
-2^31
и+2^31-1
(32 бита). Вы можете легко увеличить показатели, если вы хотите генерировать большие целые числа, но это может не сработать в зависимости от реализации Perl.1.#INF
если быть точным)C #,
126107 байтUngolfed:
Шанс сгенерировать число n цифр составляет 1/2 ^ (n-10), что больше 0 для всех положительных n и 1/2 для n = 11.
Также создает ведущие нули, которые, как представляется, не запрещены в исходном вопросе или в любом из его комментариев.источник
using System;
вам не нужноSystem.Random
дважды, а простоRandom
, верно?using
операторы. В любом случае это сохранит только 1 символ.-1E6, 1E6+1
.Perl, 62 байта
print $n=int rand(20)-10;while($n&&rand>.1){print int rand 10}
У меня была та же идея, что и у @Hobbs, - генерировать цифру за раз, но его код не удовлетворял добавленному требованию без ведущих нулей. Создание первой цифры вместо просто знака решило это. И если нет более короткого способа выхода, если мы напечатали ноль, или более короткого способа сгенерировать ведущие от -9 до 9, это должно сделать это для размера.
В цикле оболочки:
while perl -e '...'; do echo;done |less
Я думаю, что это один из самых коротких, который не требует бесконечной оперативной памяти для решения проблемы. В качестве бонуса, результат не сильно смещен ни к чему, и время выполнения очень быстрое.
Я попытался использовать побитовое и сохранить символ в состоянии while, но я думаю, что это чаще всего оказывается истиной, поэтому цикл завершается раньше. Потребовалось бы больше символов для корректировки других вещей, чтобы противостоять этому, чтобы поддерживать вероятность генерации abs (выход)> 1M.
источник
Javascript (73)
Это решение использует то, что вы можете построить число с основанием n , умножив предыдущее число на n и добавив цифру в основание n . У нас есть дополнительный,
..?..:..
чтобы иметь возможность создавать все отрицательные целые числа. Следующий код должен быть протестирован в консоли браузера.Вероятность получить целое число> =
2^1
(или <=-(2^1)
) равна вероятности того, что цикл будет выполнен 2 раза. Вероятность этого есть(98/99)^2
. Следовательно, вероятность получить число, которое больше2^20
(или <=-(2^20)
), составляет(98/99)^21 = 0.808
81%. Это все теоретически, и при условии, что Math.random действительно случайный. Это явно не так.Фрагмент, тестирующий этот код. Также более читабельным способом.
Показать фрагмент кода
источник
GolfScript, 20 байт
Да, этот тоже немного медленный.
По сравнению с такими языками, как CJam и Pyth, GolfScript страдает многословным ключевым словом генерации случайных чисел (
rand
). Чтобы преодолеть этот недостаток, мне нужно было найти способ использовать его только один раз.Этот код работает путем многократного выбора случайного числа в диапазоне от 0 до 8 8 -1 = 16 777 215 включительно и увеличения счетчика до тех пор, пока случайное число не окажется равным 0. Полученное значение счетчика имеет геометрическое распределение с медианой приблизительно -1 / log 2 (1 - 1/8 8 ) ≈ 11 629 080, что соответствует критерию «более 1 000 000, по крайней мере, 50% времени».
Увы, сгенерированное таким образом случайное число всегда строго положительно. Таким образом, дополнительная
.2&(*4/
часть необходима, чтобы позволить ей стать отрицательной или нулевой. Он работает, извлекая второй младший бит числа (который, таким образом, равен 0 или 2), уменьшая его до значения -1 или 1, умножая его на исходное число и деля результат на 4 (чтобы избавиться от младшие два бита, которые теперь соотносятся со знаком, а также позволяют результату стать нулевым). Даже после деления на 4 абсолютное значение случайного числа по-прежнему имеет медиану -1 / log 2 (1 - 1/8 8 ) / 4 ≈ 2 907 270, поэтому оно все равно проходит 50% тест.источник
JavaScript, 81 байт
Этот код выполняет все правила:
0
в выводеВ качестве бонуса алгоритм работает с временной сложностью O (log 10 n), поэтому он возвращает целое число почти мгновенно.
Это предполагает среду REPL. Попробуйте запустить приведенный выше код в консоли вашего браузера или используйте приведенный ниже фрагмент стека:
Алгоритм :
s
до тех пор, покаMath.random() > 0.1
.Math.random() > 0.5
, сделайте число отрицательным (добавив строкуs
с-
).Этот алгоритм не имеет равномерного распределения по всем целым числам. Целые числа с большим числом цифр менее вероятны, чем младшие. В каждой итерации цикла есть вероятность 10%, что я остановлюсь на текущей цифре. Я просто должен убедиться, что я останавливаюсь после 6 цифр более 50% времени.
Это уравнение от @nutki объясняет максимальное значение процента вероятности остановки на основе вышеуказанного условия:
Таким образом, 0,1 находится в пределах досягаемости, чтобы удовлетворить все три правила вопроса.
источник
TI-BASIC, 14 байтов
Подобно R-ответу @ ssdecontrol, он основан на гауссовском распределении со средним значением -1 000 000 или 1 000 000, выбранным случайным образом, и стандартным отклонением 9. Распределение не ограничено, поэтому в теории это может генерировать любое целое число.
Пояснение :
источник
:
«печатать» означает «объяснение»). Но может ли он генерировать числа более 20 цифр?randNorm
?Баш, 66
Он почти всегда печатает 5000000. Но если он нашел правильное число в
/dev/random
, он вместо этого напечатает это число.И этот быстрее:
источник
/dev/urandom
менее случайным./dev/urandom
сценария оболочки в основном аналогично вызовуrand()
в других языках. Хотя, если вы действительно используете bash, а не POSIX sh, вы можете получить случайные числаecho $RANDOM
. wiki.ubuntu.com/DashAsBinSh даетhexdump /dev/urandom
эквивалент для голого POSIX-минимума/bin/dash
.C ++, 95 байт
Expanded:
Объяснение:
Функция продолжает печатать последовательные случайные цифры, пока переключатель со случайным значением не примет необходимое значение для остановки функции. d - это переменная, в которой хранится значение следующей цифры для печати. s - переменная переключения, которая принимает случайные целочисленные значения в интервале [0, 9], если s == 9, то больше никаких цифр не печатается, и функция заканчивается.
Переменные d и s инициализируются, чтобы дать специальную обработку первой цифре (беря ее из интервала [-9, 9], и если первая цифра равна нулю, то функция должна заканчиваться, чтобы избежать начальных нулей). Значение d может быть назначено как d = rand ()% 10, но тогда первая цифра не может быть отрицательной. Вместо этого d присваивается как d = (rand ()% 19 + d + 9)% 10 и инициализируется в -18, поэтому первое значение d будет варьироваться от [-9, 9], а следующие значения всегда будут в диапазоне от [0 9].
Переменная s варьируется случайным образом от [0, 9], и если s равно 9, функция завершается, поэтому после печати первой цифры следующая будет напечатана с вероятностью 90% (при условии, что rand () действительно случайна, и чтобы удовлетворить третье условие). s можно легко назначить как s = rand ()% 10, однако, есть исключение: если первая цифра равна нулю, функция должна завершиться. Для обработки такого исключения s был назначен как s = 9-rand ()% 10 * min (d * d + s + 1,1) и инициализирован как -1. Если первая цифра равна нулю, min вернет 0, а s будет равно 9-0 = 9. Назначение переменной s всегда будет в диапазоне от [0, 9], поэтому исключение может произойти только в первой цифре.
Характеристики (при условии, что rand () действительно случайный)
Целое число печатается цифра за цифрой с фиксированной вероятностью 90% печати другой цифры после печати последней.
0 - это целое число с наибольшей вероятностью печати, с вероятностью приблизительно 5,2%.
Вероятность печати целого числа на интервале [-10 ^ 6, 10 ^ 6] составляет примерно 44% (расчет здесь не написан).
Положительные и отрицательные целые числа печатаются с одинаковой вероятностью (~ 47,4%).
Не все цифры печатаются с одинаковой вероятностью. Например: в середине печати целого числа, если последняя цифра была 5, цифра 3 будет иметь немного меньшую вероятность быть напечатанной следующей. В общем, если последняя цифра была d, цифра (d + 18)% 10 будет иметь немного меньшую вероятность быть напечатанной следующей.
Пример выходов (10 исполнений)
источник
Баш, 42 байта
printf "%d\n" 0x$(xxd -p -l5 /dev/random)
/ dev / random в OSX - это случайные байты, которые
xxd -p -l5
преобразуют 5 символов ascii в шестнадцатеричные и преобразуютprintf
их в десятичный формат.источник
Pyth , 11 байт
Примечание: эта программа, вероятно, завершится с ошибкой памяти на любом реальном компьютере. Чтобы проверить это, попробуйте заменить
G
более короткой строкой, такой как в этом коде, которая генерирует числа в среднем около 28000:Этот код зацикливается, добавляя случайное число от -1 до 8
Z
с вероятностью 2 ^ -26 выхода из цикла при каждом повторении. Вероятность 2 ^ -26 достигается выбором случайного элемента (O
) из набора всех подмножеств (y
) алфавита (G
).Технические детали и обоснование:
Вероятность 2 ^ -26 определяется двумя фактами:
y
при вызове последовательностей это функция набора мощности, которая строит список всех подмножеств входных данных. ПосколькуG
длина входного файла составляет 26 символов, в этом наборе мощностиyG
содержится 2 ^ 26 записей.OyG
выбирает случайный элемент из этих 2 ^ 26 записей. Именно одна из этих записей, пустая строка, при передачеW
в цикл while. Таким образом, существует вероятность 2 ^ -26 выхода из цикла каждый раз.В любом фиксированном количестве циклов цикла K вероятность получения числа K * 3,5 + m и получения K * 3,5 - m равна, потому что каждая последовательность суммирований, которая достигает одного итога, может быть инвертирована, -1 -> 8, 0 -> 7 и т. Д., Чтобы добиться другого. Кроме того, числа ближе к K * 3.5 явно более вероятны, чем числа дальше. Таким образом, если K> 2000000 / 3.5 = 571428.5, вероятность получения числа свыше 1000000 превышает 75%, поскольку некоторые из результатов, превышающих это число, можно сопоставить один к одному со всеми результатами ниже этого число, а верхняя половина меньше, может быть приведено в соответствие один к одному с теми, кто меньше 1000000. Вероятность получения не менее 571429 циклов составляет (1-2 ^ -26) ^ 571429, что не менее чем (1-2 ^ -26 * 571429), ожидаемое количество выходов из цикла за первые 571429 попыток, что составляет 99,1%. Таким образом, в 99,1% или более испытаний существует 75% или более шансов получить как минимум 1000000, так что существует более 50% шансов получить более 1000000.
Этот код основан на поведении,
O
когда ошибка была случайно введена 3 дня назад и была исправлена сегодня. Он должен работать на любой версии Pyth 3 до 22 декабря или после сегодняшнего дня. Следующий код эквивалентен и всегда работал:источник
Java, 113 байт
Эта программа печатает двоичное число в стандартный поток вывода. Возможно, вам придется подождать некоторое время, потому что вероятность того, что число закончится (или оно будет положительным), равна приблизительно 0. Идея, что абсолютное значение сгенерированного числа составляет менее 1 миллиона, забавна, но возможна.
Ungolfed:
Образец вывода: будет публиковаться, когда число будет сделано, генерируется.
источник
Ява (JDK) ,
140127 байт-13 bytes
добавив больше логики в заголовок цикла - благодаря @ceilingcatПопробуйте онлайн!
источник