Pull to refresh

Comments 44

UFO landed and left these words here
Не могу понять, увы, в чем в первом примере ошибка? Неверно считаются комбинации?
В тексте программы написано 133 вместо 132. Лишнего вычислили.
У вас везде результаты совпадают с теми, что в условиях ответа. Значит все правильно?

Тут конечно 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 — надежная игра выходит!

Налицо явное непонимание вероятностей.
UFO landed and left these words here
Я бы просто оставил ссылку на описание урновых схем, а не разжевывал частный случай.
UFO landed and left these words here
круто, что вероятность >1 вас все же смутила)
я пытался добиться от автора и комментатора, что они данным образом хотели посчитать и явно показать на примере, что подход неправильный.

Хорошо, в следующий раз буду писать явнее <irony/>, хотя, я надеялся, в этом случае последняя строчка все же это покажет.
UFO landed and left these words here
Да, с инвертированием не заметил. Красные надо было. Увлекся получением прекрасной оценки вероятности > 1.
Я брал сумму несовместных событий:
Вероятность того, что выпадет синий на 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 у меня вышло в первый раз, не извольте судить.
Щаз мона каменты ридактировать если чо

Комментарии можно редактировать с октября 2012.
Если вдруг, кто-то сомневается в истинности моих слов, у меня в профиле весит статья, которая всем своим видом указывает на то, что:
1. Я что-то понимаю в теор.вере.
2. Люблю делать глупые ошибки и опечатки на ровном месте.
UFO landed and left these words here
Касательно полного перебора от автора поста
Факториал 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
Да, с 30! все персональные компьютеры мира в сумме не справятся и за год.
На счет решения перебором до 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=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.
Ограничения для упрощения: кольца не граничат друг с другом, не пересекаются и не могут быть вложенными.
UFO landed and left these words here
Интересно, ведь эти задачки можно решить аналитически.
Хорошо бы взглянуть на принципы и подходы к таким заданиям.
Все задачи на применение специфических разделов математики (комбинаторика, арифметика остатков и пр.), а не на программирование. Например, задачи, подобные последней, учат решать в 8 классе физ-мат. школ без программирования вообще.
Так ведь это только 1 этап из 3, простое автоматизированное тестирование.
Или вы считаете, что знать математику даже на таком уровне программисту не нужно?
Ниодна из ваших задач не совпала c моими. Странно. Вы прошли во второй этап или нет?
Сейчас посчитал вторую задачу на руби, получил за 50 минут расчета результат:

Вероятность — 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


ПС с питоном знаком плохо
Думаю, в данном случае это не принципиально. Код — говно. Но в данном случае это и не важно, потому что он написан для того, чтобы один раз посчитать, а с этой задачей, как Вы можете убедиться, он справился.
Любопытный алгоритм, единственное не понял, как вам удалось заметить закономерность, что 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)

Надеюсь, объяснил понятно.
Only those users with full accounts are able to leave comments. Log in, please.