Выпуск#30: ITренировка — актуальные вопросы и задачи от ведущих компаний

[ptyrss]

Как-то большего ожидал. Вопросы имхо совершенно начального уровня.

Ну по вопросам всё просто.

первый

99 надёжно. последний передаёт бит чётности.

второй

ну если не думать то f = (f + 1) /2 отсюда на 1 мальчика будет 1 девочка. И ничего не меняется. Ну что логично в целом, так как количество детей никак не влияет на проценты рождаемости.

По задачам

Первая

Ну известная формула. https://oeis.org/A000124

Во второй ещё бы цикл обычный попросили написать, ну это несерьёзно даже...

Третья

Всё в один массив пар элементов (дата, флаг ухода) сортировка, проход. Сложность O(n log n). Абсолютно каноничная задача.

[AlexTest]

ну если не думать то f = (f + 1) /2 отсюда на 1 мальчика будет 1 девочка. И ничего не меняется. Ну что логично в целом, так как количество детей никак не влияет на проценты рождаемости.

Вы забываете о том, что по условию задачи они рожают девочек пока не родится мальчик. Т.е. на первом же мальчике процесс останавливается, а девочек может быть сколько угодно до этого. Очевидно, что в этой ситуации девочек будет рождаться больше чем мальчиков, вопрос в том — насколько?

[Dubovik_a]

В семьях будут встречаться следующие варианты последовательностей детей (0 — девочка, 1 — мальчик):
1
01
001
0001
00001

Вероятности таких последовательностей:
1 — 1/2
01 — 1/4
001 — 1/8
0001 — 1/16
00001 — 1/32

Процентное соотношение мальчиков вычисляется как предел суммы последовательности от 1 до бесконечности от 1 / (n * 2^n).
Численно получается около 69.31471805599% мальчиков.
Аналитически — натуральный логарифм от двух.

Задача решена в предположении, что вероятности рождения мальчика и девочки одинаковые (что в нашем неидеальном мире не совсем точно).

[ptyrss]

Самый простой способ. Берём большое количество пар у которых нет детей. Ровно у половины будет мальчик. У второй половины девочка. Пока 50/50. Начинаем 2 раунд. У оставшихся у половины мальчик, у второй половины девочка. Опять 50/50 и так далее.

А вы кстати ряд неправильно написали. Надо было (n-1)/2^n что в точности равно единице. Ну и мальчиков единица по определению.

И сразу AlexTest. Вероятности так не работают) У каждого броска монеты 50/50. Какую стратегию ни строй, ничего изменить нельзя. Любое множество бросков будет иметь именно такую вероятность среднюю.

P.S. вопрос оказался сложнее, чем я думал.

[Dubovik_a]

По строчкам:
1. В семье один ребёнок, один из них мальчик.
2. В семье два ребёнка, один из них мальчик.
3. В семье три ребёнка, один из них мальчик.
4. В семье четыре ребёнка, один из них мальчик.
…

Суммируйте.

[ptyrss]

Ну давайте. Посчитаем количество мальчиков. Кеп говорит что будет 1 в сумме. Считаем количество девочек.
0/2 + 1/4 + 2/8 + 3/16 + 4/32+… ну вы поняли. Итого 1. Вроде всё правильно.

[Dubovik_a]

Да, кажется, в моей формуле не хватает нормировки на кол-во детей.
А простое объяснение на словах звучит примерно так:
«При рождении n-го ребёнка родится поровну мальчиков и девочек. При этом все мальчики окажутся в семьях, в которых всего суммарно n детей, а все девочки окажутся в семьях с n+1, n+2 и т.д. детей».
Итого: поровну.

[AlexTest]

Да, вы правы. Когда у меня начала крыша ехать от рассуждений — написал простую програмку, чтобы численно проверить результат:

$d = 0;
$m = 0;
$n = [];
for ($i = 0; $i < 10000; $i++) {
    $notm = true;
    $k = 0;
    do {
        $v = mt_rand(0, 9999);
        if ($v < 5000) {
            $d++;
            $k++;
        } else {
            $m++;
            $notm = false;
        }
    } while ($notm);
    $n[$k] = isset($n[$k]) ? ++$n[$k] : 1;
}
ksort($n);
print_r($n);
echo "d=$d\nm=$m\n\n";

На 10000 семей каждый раз количество мальчиков и девочек получается примерно одинаково — по 10000 соответственно. При этом иногда получаются семьи, где есть и по 16 девочек, вот например в таком результате:
Array
(
[0] => 5038
[1] => 2393
[2] => 1291
[3] => 640
[4] => 323
[5] => 169
[6] => 73
[7] => 39
[8] => 23
[9] => 5
[10] => 5
[16] => 1
)
d=10038
m=10000


[AlexTest]

del