Эта задача о написании кода для точного вычисления вероятности. Вывод должен быть точной вероятностью, записанной в виде дроби в наиболее сокращенной форме. То есть это никогда не должно выводиться, 4/8
а скорее 1/2
.
Для некоторого положительного целого числа n
рассмотрим равномерно случайную строку длиной 1 с и 1 с n
и назовем ее A. Теперь объединяем A
ее первое значение. То есть A[1] = A[n+1]
если индексирование от 1. A
теперь имеет длину n+1
. Теперь также рассмотрим вторую случайную строку длины n
, первые n
значения которой равны -1, 0 или 1 с вероятностью 1 / 4,1 / 2, 1/4 каждая и назовем ее B.
Например, рассмотрим n=3
. Возможные значения A
и B
могут быть A = [-1,1,1,-1]
и B=[0,1,-1]
. В этом случае два внутренних продукта 0
и 2
.
Теперь рассмотрим внутреннее произведение A[1,...,n]
и B
и и внутреннее произведение A[2,...,n+1]
и B
.
Ваш код должен выводить вероятность того, что оба внутренних продукта равны нулю.
Для n=1
этой вероятности это ясно 1/2
.
Я не против, как n
указано в коде, но это должно быть очень просто и понятно, как это изменить.
Языки и библиотеки
Вы можете использовать любой язык и библиотеки, которые вам нравятся. Я хотел бы запустить ваш код, поэтому, пожалуйста, включите полное объяснение того, как запустить / скомпилировать ваш код в Linux, если это вообще возможно.
n
были бы полезны. Также может быть полезен явный пример A, B и двух внутренних продуктов.n=4
считаться ноль, два или три байта? Должен ли вывод быть точнымa/b
или будет[a b]
, например, разрешен?n
? В противном случае, я думаю, что это не разрешено.Ответы:
Pyth,
48474644 байтаПопробуйте онлайн: Демонстрация
Онлайн-версия, вероятно, не рассчитывает
n=6
. На моем ноутбуке (автономная версия) это занимает около 45 секунд.Метод грубой силы.
Объяснение:
источник
+0r1_2
короче чем/R2r2_2
.Mathematica,
159100878685 байтДля изменения
n
просто измените определение переменной в начале.Так как это грубая сила, это довольно медленно, но вот первые восемь результатов:
Последний уже занял 231 секунду, и время выполнения ужасно экспоненциально.
объяснение
Как я уже сказал, это грубая сила. По сути, я просто перечисляю все возможные
A
иB
вычисляю два точечных произведения для каждой возможной пары, а затем нахожу полученную долю пар{0, 0}
. Комбинаторика Mathematica и функции линейной алгебры очень помогли в игре в гольф:Это создает все n-кортежи, содержащие
1
или-1
, то есть все возможныеA
. Дляn = 3
этого есть:Для вычисления
B
мы делаем почти то же самое:Повторяя
0
, мы дублируем каждый кортеж для каждого, который0
он содержит, тем самым делая в0
два раза больше вероятности, чем1
или-1
. Снова используяn = 3
в качестве примера:Теперь, для каждого возможного
A
, мы хотим получить точечное произведение каждого из этих возможныхB
, как с, такA[1 .. n]
иA[2 .. n+1]
. Например , если наш текущийA
является{1, 1, -1}
, мы хотим , чтобы скалярное произведение с обоими{1, 1, -1}
и с{1, -1, 1}
. Поскольку все нашиB
уже удобно являются строками матрицы, мы хотим, чтобы эти два подсписка былиA
столбцами другой матрицы, чтобы мы могли вычислить простое произведение точек между ними. Но транспонирование{{1, 1, -1}, {1, -1, 1}}
просто дает,{{1, 1}, {1, -1}, {-1, 1}}
который является просто списком всех 2-элементных циклических подсписковA
. Вот что это делает:Итак, мы вычислим это и возьмем скалярное произведение с нашим списком
B
. Так как теперь мы получаем вложенный список (поскольку каждый возможныйA
дает отдельный вектор), мы выравниваем их с помощью##&@@
.Чтобы узнать, есть ли пара
{x, y}
,{0, 0}
мы вычисляем,Sign[Norm[{x,y}]]
гдеNorm
дает√(x²+y²)
. Это дает0
или1
.Наконец, поскольку теперь мы просто хотим знать доли
1
s в списке0
s и1
s, все, что нам нужно, это среднее арифметическое этого списка. Однако это дает вероятность того, что оба, по крайней мере, одного точечного произведения отличны от нуля, поэтому мы вычтем его,1
чтобы получить желаемый результат.источник
Pyth -
6555 байтИсправлена ошибка с уменьшением дроби при стоимости одного байта.
Использует метод грубой силы, и может быть в гольфе, но просто хотел что-то получить. Очень медленно
Он использует декартовы произведения для генерации обоих
A
иB
, делая переменные вероятности,0
появляется дважды в списке источников, а затем подсчитывает те, которые являются внутренним произведением, до нуля. Внутренний продукт облегчается путемV
употребления синтаксического сахара. Упрощение дроби пугало меня поначалу, но это было довольно легко сP
функцией факторизации иней и пониманием того, что нам нужно уменьшить только на степени 2.Попробуйте это онлайн здесь .
источник
n
?CJam,
5857545146 байтЧтобы запустить его, вставьте желаемое целое число между
WX]
иm*
.Спасибо @ jimmy23013 за немного волшебства и за гольф в 5 байтах!
Попробуйте онлайн в интерпретаторе CJam .
идея
Большинство частей этого ответа просты, но в нем используются два хитрых трюка:
Вместо того чтобы связывать все векторы {-1, 1} n со всеми векторами {-1, 0, 1} n с желаемыми вероятностями, он считает количество триплетов векторов в {-1, 1} n, которые удовлетворяют определенное условие.
Если мы добавим два последних вектора триплета, результатом будет вектор {-2, 0, 2} n .
Поскольку (-1) + 1 = 0 = 1 + (-1) , 0 с будет происходить вдвое чаще, чем -2 с и 2 с.
Разделив каждый компонент на 2 , мы получим вектор {-1, 0, 1} n с желаемыми вероятностями.
Поскольку нас интересует только скалярное произведение 0 или нет, мы можем пропустить деление на 2 .
После подсчета всех триплетов, удовлетворяющих условию вопроса и общего количества триплетов, мы должны уменьшить полученную дробь.
Вместо вычисления GCD обоих чисел, поскольку знаменатель всегда будет степенью 2, достаточно разделить оба числа на наибольшую степень 2, которая делит числитель.
Чтобы получить наибольшую степень 2, которая делит x , мы можем взять побитовое И для x и ~ x + 1 .
~ x инвертирует все биты x , поэтому все завершающие 0 с становятся 1 с. При добавлении 1 к ~ x эти 1 с превратятся в 0 с, а последние 1 в ~ x + 1 будут соответствовать последним 1 в x .
Все остальные биты либо оба равны 0 , поэтому побитовое И возвращает целое число, состоящее из последней 1 из x и всех последующих 0 . Это высшая степень 2, которая делит х .
Код
источник
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
,