Цель
Создайте программу / функцию, которая принимает входные данные N
, проверяет, являются ли N
случайные пары целых чисел относительно простыми, и возвращает sqrt(6 * N / #coprime)
.
TL; DR
Эти проблемы представляют собой симуляции алгоритмов, которые требуют только природы и вашего мозга (и, возможно, некоторых ресурсов многократного использования) для приближения Pi. Если вам действительно нужен Пи во время апокалипсиса зомби, эти методы не тратят патроны ! Есть еще восемь задач. Оформить запись в песочнице, чтобы дать рекомендации.
моделирование
Что мы моделируем? Итак, вероятность того, что два случайных целых числа являются относительно простыми (т.е. взаимно простыми или gcd == 1), такова 6/Pi/Pi
, поэтому естественным способом вычисления Pi будет выкопать два ведра (или горстки) камней; посчитай их; посмотрите, равен ли их gcd 1; повторение. После этого пару раз sqrt(6.0 * total / num_coprimes)
будет стремиться к Pi
. Если подсчет квадратного корня в постапокалиптическом мире заставляет вас нервничать, не волнуйтесь! Для этого есть метод Ньютона .
Как мы моделируем это?
- Принять вход
N
- Делайте следующее
N
время:- Равномерно генерировать случайные натуральные числа
i
иj
- С
1 <= i , j <= 10^6
- Если
gcd(i , j) == 1
:result = 1
- Else:
result = 0
- Равномерно генерировать случайные натуральные числа
- Возьмите сумму
N
результатов,S
- Возвращение
sqrt(6 * N / S)
Спецификация
- вход
- Гибкость, принимать входные данные любым из стандартных способов (например, параметр функции, STDIN) и в любом стандартном формате (например, String, Binary)
- Выход
- Гибкость, вывод на печать любым из стандартных способов (например, возврат, печать)
- Пробел, конечный и ведущий пробел приемлем
- Точность, укажите не менее 4 знаков после запятой (т.е.
3.1416
)
- счет
- Самый короткий код выигрывает!
Тестовые случаи
Ваш результат может не совпадать с этим из-за случайного шанса. Но в среднем вы должны получить примерно такую точность для заданного значения N
.
Input -> Output
----- ------
100 -> 3.????
10000 -> 3.1???
1000000 -> 3.14??
источник
N = 1000000
или это нормально, если программа возвращает, например, переполнение стека, еслиN
оно слишком велико?N=10^6
.Ответы:
APL, 23 байта
Объяснение:
?⍵2⍴1e6
: сгенерировать матрицу случайных чисел размером 2 на range в диапазоне [1..10 6 ]1+.=∨/
: получить GCD каждой пары и посмотреть, сколько равно 1. Это вычисляет S..5*⍨6×⍵÷
: (6 × ⍵ ÷ S) 0,5источник
Желе ,
20 1816 байт-2 байта благодаря @ Pietu1998 (цепочка и счет использования 1,
ċ1
вместо суммированных менее двух<2S
)-2 байта благодаря @Dennis (повторяйте 1e6 несколько раз перед выборкой, чтобы избежать цепочки)
(Чрезвычайно медленный из-за случайной функции)
Как?
TryItOnline
источник
ḤRµȷ6Xµ€g2/ċ1÷³6÷½
экономит 2 байта. (ȷ6
10 ^ 6 в одной ниладе,ċ1
считая единиц)ȷ²
, это чуть-чуть быстрееȷ6
)ȷ²
двух ссылок здесь не повредит, но потребует дополнительной ссылки или¤
для некоторых случаев использованияḤȷ6xX€
должен работать для случайной выборки.Python 2,
143140132124122124122 байтаПрошло довольно много времени с тех пор, как я пробовал играть в гольф, поэтому я, возможно, что-то здесь упустил! Буду обновлять, как я сокращаю это.
Проверь меня здесь!
спасибо Джонатану Аллану за двухбайтовое сохранение :)
источник
1 <= i , j <= 10^6
так что вам нужно использоватьrandrange(1,1e6+1)
.k=lambda:r.randrange(1e6)+1
сохраняет два байтаMathematica,
494851 байтБлагодаря @ LegionMammal978 сохранен один байт и исправлена одна ошибка .
источник
(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
1*^6
должно быть заменено на,{1,1*^6}
чтобы убедиться, что я , J ≠ 0.R,
1039995999894 байтаСкорее всего, немного проиграл. Сократите 4 байта из-за @ antoine-sac и еще 4 байта, определив псевдоним для
sample
, используя^.5
вместоsqrt
и1e6
вместо10^6
. Добавлены 4 байта для обеспечения того, чтобы выборкаi
иj
была действительно равномерной. Убрал один байт после того, как понял, что6*N/sum(x)
это тоже самое6/mean(x)
. Используетсяpryr::f
вместоfunction(x,y)
сохранения 4 байта.Образец вывода:
источник
sample(10^6,N)
. Он не только короче, но и гораздо эффективнее.sample(10,10)
гарантированно вернет все числа в 1:10, тогда какsample(10,10,T)
произведет случайный выбор, где числа могут повторяться.На самом деле, 19 байтов
Попробуйте онлайн!
Объяснение:
источник
MATL , 22 байта
Попробуйте онлайн!
источник
Pyth, 21 байт
Попробуйте онлайн.
объяснение
источник
Scala,
149126 байтОбъяснение:
источник
6f
,Seq.fill
иmath.random
.Ракетка 92 байта
Ungolfed:
Тестирование:
Выход:
источник
JavaScript (ES7),
1079594 байтаВерсия ES6 составляет ровно 99 байтов, но оператор возведения в степень ES7
**
экономит 5 байтовMath.sqrt
.Ungolfed
источник
gcd
вызывает функциюg
r=_=>
это код или рисунок?n=>(n*6/(r=_=>Math.random()*1e6,g=(a,b)=>b?g(b,a%b):a>-2,q=n=>n&&g(~r(),~r())+q(n-1))(n))**.5
1B корочеn=>(n*6/(q=_=>n--&&q(r=_=>Math.random()*1e6)+g(~r(),~r()))(g=(a,b)=>b?g(b,a%b):a>-2))**.5
PHP,
827774 байтаЗапустите так:
объяснение
Делает то, что говорит на банке. Требуется PHP_GMP для
gcd
.Tweaks
$argn
источник
Perl, 64 байта
Требуется опция командной строки
-pMntheory=gcd
, считается как 13. Ввод взят из стандартного ввода.Образец использования
источник
R, 94 байта
Относительно медленно, но все еще работает. Повторяем N раз функцию, которая берет 2 случайных числа (от 1 до 1e6) и проверяет, меньше ли их gcd, чем 2 (используя мою старую функцию gcd ).
источник
1:x
сработает.PowerShell v2 +,
118114 байтПринимает ввод
$n
, запускаетfor
цикл до тех пор, пока не$k
станет равным$n
(неявно$k=0
при первом входе в цикл). Каждую итерацию получают новыеRandom
числа$i
и$j
(-mi
минимум1
флаг гарантирует, что мы>=1
и флаг максимума не позволяет[int]::MaxValue
, что разрешено OP, так как он больше, чем10e6
).Затем мы идем в цикл GCD
while
. Тогда, пока GCD1
,$o
увеличивается. В концеfor
цикла мы делаем простой[math]::Sqrt()
вызов, который остается в конвейере и вывод неявен.Занимает около 15 минут, чтобы работать со входом
10000
на моем ~ 1-летнем ноутбуке Core i5.Примеры
источник
Java 8,
164151 байтобъяснение
Test Harness
Обновить
источник
n
,t+=1
может статьt++
, вы можете сжать своиint
объявления в одну строку, то естьint c=n,t=0,x,y;
, и!=0
(я думаю) может стать>0
. Это должно сэкономить 12 байт в целом. Это отличный способ найти GCD для x и y.Perl 6 ,
5653 байтаПопробуйте онлайн!
источник
Фринк,
8489Мне повезло: g = n = ... сохраняет байт за g = 0 n = ... ; и 1% gcd () дает (0,1) против (1,0), поэтому я могу вычесть. И не повезло: n предварительно назначено и используется, потому что переменные цикла и их границы являются локальными и неопределенными вне цикла.
Подробный
источник
AWK , 109 байт
Попробуйте онлайн!
Я удивлен, что он работает в разумные сроки за 1000000.
источник
Пыть ,
3735 байтОбъяснение:
источник
J, 27 байт
Объяснение:
Есть очень повезло с
3.14157
дляN = 10000000
, который занял2.44
секунд.источник
Japt , 23 байта
Попытайся
источник