Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
У вас везде результаты совпадают с теми, что в условиях ответа. Значит все правильно?
Тут конечно python не заменим. А то многие бы на длинной арифметике рухнули.
1. Собственно первую задачу можно решить и без нее:
Нужна функция подсчета количества перестановок, которая бы останавливала вычисления, когда уйдет за нужную границу. И нет смысла для каждого n и k. Нужно для каждого n прекращать нитрирование по к, после того как найдется k для которой количество перестановок вылезло за предел.
2. Почему в условии 11/120, а у вас 15/120. У меня тоже 15/120 получается. Кто и где ошибся?
5. Зачем степень по модулю 1000000000000000000000? 10^10 было бы достаточно…
Это 30! число маленькое??!!! И опять неэффективности тонна. Можно было 2^30 вариантов рассмотреть, было бы достаточно. 2^30 все возможные варианты где он и что достал.
Можно было даже меньше, например рекурсией с отсечением, если уже известно что проиграл.
Тут конечно python не заменим. А то многие бы на длинной арифметике рухнули.
1. Собственно первую задачу можно решить и без нее:
Нужна функция подсчета количества перестановок, которая бы останавливала вычисления, когда уйдет за нужную границу. И нет смысла для каждого n и k. Нужно для каждого n прекращать нитрирование по к, после того как найдется k для которой количество перестановок вылезло за предел.
2. Почему в условии 11/120, а у вас 15/120. У меня тоже 15/120 получается. Кто и где ошибся?
5. Зачем степень по модулю 1000000000000000000000? 10^10 было бы достаточно…
Это 30! число маленькое??!!! И опять неэффективности тонна. Можно было 2^30 вариантов рассмотреть, было бы достаточно. 2^30 все возможные варианты где он и что достал.
Можно было даже меньше, например рекурсией с отсечением, если уже известно что проиграл.
Вы можете обьяснить, что именно считается здесь 1/60+1/40+1/30+1/24+1/120=15/120?
Если следовать данной логике, мы придем вот к чему:
Инвертируем постановку задачи и посчитаем шанс выпадения 3 или больше синих дисков.
Вероятности выбора синего диска на каждом из 4 шагов, соответственно, 1/2 2/3 3/4 4/5
По указанной в решении формуле считаем как бы «вероятность успеха»
24/120 (все синие) + 6/24(без четвертого) + 8/30 (без третьего) + 12/40(без второго) + 24/60 (без первого) = (24 + 30 + 32 + 36 + 48) = 170/120 — надежная игра выходит!
Налицо явное непонимание вероятностей.
Если следовать данной логике, мы придем вот к чему:
Инвертируем постановку задачи и посчитаем шанс выпадения 3 или больше синих дисков.
Вероятности выбора синего диска на каждом из 4 шагов, соответственно, 1/2 2/3 3/4 4/5
По указанной в решении формуле считаем как бы «вероятность успеха»
24/120 (все синие) + 6/24(без четвертого) + 8/30 (без третьего) + 12/40(без второго) + 24/60 (без первого) = (24 + 30 + 32 + 36 + 48) = 170/120 — надежная игра выходит!
Налицо явное непонимание вероятностей.
Я бы просто оставил ссылку на описание урновых схем, а не разжевывал частный случай.
круто, что вероятность >1 вас все же смутила)
я пытался добиться от автора и комментатора, что они данным образом хотели посчитать и явно показать на примере, что подход неправильный.
Хорошо, в следующий раз буду писать явнее <irony/>, хотя, я надеялся, в этом случае последняя строчка все же это покажет.
я пытался добиться от автора и комментатора, что они данным образом хотели посчитать и явно показать на примере, что подход неправильный.
Хорошо, в следующий раз буду писать явнее <irony/>, хотя, я надеялся, в этом случае последняя строчка все же это покажет.
Я брал сумму несовместных событий:
Вероятность того, что выпадет синий на 1 первом и только на первом, вероятность что на втором и только на втором, вероятность что на третьем и только на третьем и вероятность того что не выпадет совсем. Вероятность суммы равна сумма вероятностей для несовместных событий. И того:
1/2 * 1/3 * 1/4 * 1/5 +
1/2 * 1/3 * 1/4 * 1/5 +
1/2 * 2/3 * 1/4 * 1/5 +
1/2 * 1/3 * 3/4 * 1/5 +
1/2 * 1/3 * 1/4 * 4/5 = 1 / 120 + 1 / 120 + 2 / 120 + 3 / 120 + 4 /120 = 11 / 120.
А то, что у меня раннее вышло 15/120 — глупые арифметические ошибки.
Будьте уверены, непонимания теории вероятности и математической статистике у меня отсутствует.
1 / 120 + 2 / 120 + 3 / 120 + 4 / 120 + 5 /120 у меня вышло в первый раз, не извольте судить.
Вероятность того, что выпадет синий на 1 первом и только на первом, вероятность что на втором и только на втором, вероятность что на третьем и только на третьем и вероятность того что не выпадет совсем. Вероятность суммы равна сумма вероятностей для несовместных событий. И того:
1/2 * 1/3 * 1/4 * 1/5 +
1/2 * 1/3 * 1/4 * 1/5 +
1/2 * 2/3 * 1/4 * 1/5 +
1/2 * 1/3 * 3/4 * 1/5 +
1/2 * 1/3 * 1/4 * 4/5 = 1 / 120 + 1 / 120 + 2 / 120 + 3 / 120 + 4 /120 = 11 / 120.
А то, что у меня раннее вышло 15/120 — глупые арифметические ошибки.
Будьте уверены, непонимания теории вероятности и математической статистике у меня отсутствует.
1 / 120 + 2 / 120 + 3 / 120 + 4 / 120 + 5 /120 у меня вышло в первый раз, не извольте судить.
*красный.
Если вдруг, кто-то сомневается в истинности моих слов, у меня в профиле весит статья, которая всем своим видом указывает на то, что:
1. Я что-то понимаю в теор.вере.
2. Люблю делать глупые ошибки и опечатки на ровном месте.
1. Я что-то понимаю в теор.вере.
2. Люблю делать глупые ошибки и опечатки на ровном месте.
Касательно полного перебора от автора поста
Это все равно, что играть за Pudge и не качать Meat Hook. Facepalm, одним словом.
Можно и без перебора решать — при помощи динамического программирования можно найти ответ за O(N^3 * log(N)) для игры из N ходов (см. спойлер).
Факториал 30 число маленькое, опять используем полный перебор.
Это все равно, что играть за Pudge и не качать Meat Hook. Facepalm, одним словом.
Можно было 2^30 вариантов рассмотреть, было бы достаточно.
Можно и без перебора решать — при помощи динамического программирования можно найти ответ за O(N^3 * log(N)) для игры из N ходов (см. спойлер).
Подробнее
А именно: пронумеруем все красные шары на каждом ходу. Тогда у нас всего (N+1)! равновероятных возможных вариантов игры. Пусть d[i][j] — количество вариантов игры, при которых мы выиграем, если мы уже сделали i ходов и при этом вытянули j синих дисков. Посчитать каждый элемент d[i][j] можно за O(N * log(N)). При i = N, очевидно d[i][j] = 1 при j > N — j и 0 в противном случае. При j < N, получаем d[i][j] = d[i+1][j + 1] (мы вытянули синий диск) + (N+1) * d[i+1][j] (вытянули красный диск). Поскольку во всех числах O(N * log(N)) цифр, то каждая ячейка пересчитывается за O(N * log(N)), а всего их O(N^2).
про 30! маленькое число — «шутка-ловушка»
оно же больше 2^107 и за 15 минут не справиться в одно ядро на персоналке
у меня перебор до C(30,15)=1.5*10^8
оно же больше 2^107 и за 15 минут не справиться в одно ядро на персоналке
у меня перебор до C(30,15)=1.5*10^8
Да, с 30! все персональные компьютеры мира в сумме не справятся и за год.
На счет решения перебором до C(30,15) — я так понимаю, идет перебор расположения ходов, на которых вытянули красный диск. То есть надо еще и C(30,14), C(30,13)… C(30, 0) перебирать (что в сумме тоже имеет порядок 2^30, а именно 2^29). Потом для каждого расположения нужно посчитать частоту его возникновения, то есть для каждого хода выполнять умножение большого числа, что дает порядка 30^2 операций. Итого, будет считаться довольно долго (полагаю, около часа), но дождаться можно.
На счет решения перебором до C(30,15) — я так понимаю, идет перебор расположения ходов, на которых вытянули красный диск. То есть надо еще и C(30,14), C(30,13)… C(30, 0) перебирать (что в сумме тоже имеет порядок 2^30, а именно 2^29). Потом для каждого расположения нужно посчитать частоту его возникновения, то есть для каждого хода выполнять умножение большого числа, что дает порядка 30^2 операций. Итого, будет считаться довольно долго (полагаю, около часа), но дождаться можно.
Вас уже приняли?
Интересно
Не вполне ясно решение задачи про числа. Здесь точно нет никакой ошибки:
for d in range(0,11): # объявляем для чисел новой длины
a[tail,d]=0
b[tail,d]=0
for d in range(1,10): # приписываем слева цифры
А еще, кажется, ошибка в конечном подсчете результата.
Наверное, в цикле к start стоит прибавлять 9*10^(q-1).
и еще
правильнее было бы написать
так как числа состояшие из одинаковых цифр надо вычитать из количества увеличивающихся и убывающих, а не из результата
start=0
for q in range(2,76):
[pa,pb]=snext(q)
start=start-pa-pb-9 # т.к. числа состаящие из одних единиц, двоек, ...., девяток учитываем дважды - вычитаем лишние 9
Наверное, в цикле к start стоит прибавлять 9*10^(q-1).
и еще
start=start-pa-pb-9 # т.к. числа состаящие из одних единиц, двоек, ...., девяток учитываем дважды - вычитаем лишние 9
правильнее было бы написать
start=start-(pa+pb-9)
так как числа состояшие из одинаковых цифр надо вычитать из количества увеличивающихся и убывающих, а не из результата
Что-то они зациклились на математических задачах. Могли бы и что-то пооригинальнее придумать. Вот, к примеру задачка с олимпиады для школьников: дана матрица из 0 и 1, из единиц внутри матрицы нарисованы кольца (кривые и разного размера). Нужно подсчитать, сколько таких колец.
Пример:
0000000000
0100000000
1010011000
0100110110
0000110100
0000011100
Ответ: 2.
Ограничения для упрощения: кольца не граничат друг с другом, не пересекаются и не могут быть вложенными.
Пример:
0000000000
0100000000
1010011000
0100110110
0000110100
0000011100
Ответ: 2.
Ограничения для упрощения: кольца не граничат друг с другом, не пересекаются и не могут быть вложенными.
Интересно, ведь эти задачки можно решить аналитически.
Хорошо бы взглянуть на принципы и подходы к таким заданиям.
Хорошо бы взглянуть на принципы и подходы к таким заданиям.
Все задачи на применение специфических разделов математики (комбинаторика, арифметика остатков и пр.), а не на программирование. Например, задачи, подобные последней, учат решать в 8 классе физ-мат. школ без программирования вообще.
Ниодна из ваших задач не совпала c моими. Странно. Вы прошли во второй этап или нет?
Сейчас посчитал вторую задачу на руби, получил за 50 минут расчета результат:
Вероятность — 2289739189263596147049585 / 8222838654177922817725562880000000
Ответ — 3591168239
Кто-нибудь еще пробовал считать?
Вероятность — 2289739189263596147049585 / 8222838654177922817725562880000000
Ответ — 3591168239
Кто-нибудь еще пробовал считать?
Получил такой же ответ. Считал табличным методом. Работает меньше секунды.
Здорово, было бы любопытно взглянуть на ваше решение. Я, конечно, в лоб перебирал.
Как то так…
ПС с питоном знаком плохо
n = 30
a = [1,1]
def fact(x):
if(x <= 2):
return x
return fact(x-1)*x
for i in range(2,n+1):
b = [ a[0]*i ]
for j in range(1,i):
b += [ a[j-1] + a[j]*i ]
j += 1
b += [ a[j-1] ]
a = b
sum = 0;
for i in range(n/2+1,n+1):
sum += a[i]
print fact(n+1)/sum
ПС с питоном знаком плохо
0! = 1
а у вас будет 0
а у вас будет 0
Любопытный алгоритм, единственное не понял, как вам удалось заметить закономерность, что j-й элемент массива равен (j-1)-му на прошлом шаге плюс j-й на прошлом шаге умножить на n. То есть я расписал на листочке вероятности для n от 2 до 4 и убедился в этом, но вывести закономерность не так просто имхо.
Просто очень люблю задачи динамического программирования.
Пусть a[i,j] — количество способов вытащить j — синих дисков на i ходу.
Тогда a[i,j] = a[i-1,j] * j + a[i-1,j]
То есть
a[i-1,j] — мы взяли на прошлом ходу сколько нужно синих дисков, можем взять любой из i красных дисков (домножаем на i)
a[i-1,j-1] — набрали на прошлом ходу меньше, чем нужно, на один и только один способ взять красный (домножаем на 1)
Надеюсь, объяснил понятно.
Пусть a[i,j] — количество способов вытащить j — синих дисков на i ходу.
Тогда a[i,j] = a[i-1,j] * j + a[i-1,j]
То есть
a[i-1,j] — мы взяли на прошлом ходу сколько нужно синих дисков, можем взять любой из i красных дисков (домножаем на i)
a[i-1,j-1] — набрали на прошлом ходу меньше, чем нужно, на один и только один способ взять красный (домножаем на 1)
Надеюсь, объяснил понятно.
Сколько было дано времени на решение задач?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор задач 1 тура школы программистов HeadHunter