Неверный процент результатов, имитирующий парадокс дня рождения
Я видел видео о проблеме с днем рождения: если в комнате 23 человека, то с вероятностью 50% у двух человек день рождения будет одинаковым. Вместо того, чтобы просто разбираться в математике, я хотел провести быстрое моделирование, поэтому поторопился и написал этот код с нуля.
Просто для некоторого контекста: я занимаюсь программированием всего около года, пройдя курс в старшей школе и имея некоторый опыт работы за пределами школы. Очевидно, что когда я запускаю симуляцию, истинный процент оказывается равным 5%, что на порядок превышает ожидаемый. Что именно не так с кодом?
Я написал код для запуска только 1000 симуляций, и мне нужно было просто указать количество совпадений, чтобы получить приблизительную оценку, но я получал только около 50-70, а не 500. Итак, я переписал код, чтобы он работал бесконечно. и просто создайте хороший процент.
Ответы 1
Здесь есть пара проблем. Первый — это цикл repeat until. Все, что это делает, — это просматривает список из 23 неотсортированных дней рождения и сравнивает каждый день рождения с тем, который находится непосредственно рядом с ним. Логика, которая вам действительно нужна, сравнивает каждый день рождения со всеми другими днями рождения, а не только с соседним.
Другая проблема заключается в том, что сравниваются не два дня рождения, а переменная счетчика i и день рождения. Вместо:
if i = birthday[i - 1]
вам нужно что-то вроде:
if birthday[i] = birthday[i - 1]
...кроме использования birthday[i] = birthday[j], где j — каждый второй день рождения в списке дней рождения.
Вот широко комментируемый код JavaScript, который вы можете попытаться адаптировать, чтобы исправить свой код Scratch. Вы можете относиться к нему как к псевдокоду, делая его немного более интересным, чем если бы я просто дал вам ответ в Scratch.
// Declare a variable to keep track of how
// many simulations returned a matching birthday.
let matchingBirthdays = 0;
// The total number of simulations, a constant.
const simulations = 1000;
// For each simulation, we will pick 23
// random birthdays for the year.
const numberOfBirthdaysToTest = 23;
// Now loop `simulations` times and run each simulation.
for (let i = 0; i < simulations; i++) {
// Start the simulation by making an empty
// array (list) of 23 birthdays.
const birthdays = [];
// For each of the 23 days...
for (let j = 0; j < numberOfBirthdaysToTest; j++) {
// ...pick a random day of the year
// and add it to the `birthdays` list.
birthdays.push(Math.floor(Math.random() * 365));
} // end random birthday array creation block
// Show the birthdays that were selected (if you want):
// console.info(birthdays)
// Now, let's find matching birthdays.
// Let's assume we won't find any matches:
let found = false;
// Then loop over every birthday to try to find a match...
for (let j = 0; !found && j < birthdays.length; j++) {
// For birthdays[j], see if there's a birthdays[k]
// later in the array that has the same value.
for (let k = j + 1; k < birthdays.length; k++) {
// Now we have two different birthdays
// pointed to by indices j and k.
// Determine if they are equal:
if (birthdays[j] === birthdays[k]) {
// We found a match! Add 1 to the
// total number of birthdays:
matchingBirthdays++;
// Optionally log the hit:
// console.info("Found match!");
// Then set `found` to true and break out of
// both loops to end the whole search.
// We'll move on to the next simulation.
found = true;
break;
} // end birthday match block
} // end search block
// If we got here and `found` is still false,
// then no match was found, and
// `matchingBirthdays` will not change.
} // end loop over all birthdays
} // end simulation block
// Print the final ratio of simulations that have
// at least a pair of matching birthdays over the
// total number of simulations. This should be around
// 0.5 assuming we've done at least 1000 simulations.
console.info(matchingBirthdays / simulations);Обратите внимание, что этот код намеренно избегает умных функций JavaScript, которые упрощают код, но плохо переводятся в Scratch.
Этот проект — отличная иллюстрация сложности (скорости роста) вложенных циклов. Причина, по которой это называется парадоксом дня рождения, заключается в том, что удивительно, что нужно всего 23 человека, чтобы с вероятностью 50% достичь хотя бы одной пары дней рождения. Вместо 23 сравнений доступно 253 сравнения, среди которых можно найти одно совпадение.
Говоря простым языком, на каждого человека приходится 22 человека, с которыми можно сравнивать. С точки зрения кода это будет вложенный цикл. Вложенные циклы выполняют гораздо больше работы, даже если вы увеличиваете количество элементов лишь на небольшую величину. Попробуйте увеличить переменную numberOfBirthdaysToTest, и вы увидите, что вероятность совпадения быстро приближается к 100%, даже не приближаясь к 365.
Это явление известно как O(n^2) или квадратичный алгоритм. Вот скорость роста квадратичного алгоритма:
const nestedLoop = n => {
let iterations = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
iterations++;
}
}
return iterations;
};
for (let n = 0; n < 15; n++) {
const iterations = nestedLoop(n);
console.info(`n = ${n}, iterations = ${iterations}`);
}В Википедии есть диаграмма , иллюстрирующая темпы роста по мере увеличения n (количества людей). Надеюсь, это поможет вам интуитивно определить, почему ваше решение неверно: не видя этого вложенного цикла в своем коде, вы не увидите того эффекта «взрывного роста», который характерен для проблемы дня рождения.
Не могу поверить, что забыл о вложенных циклах. Спасибо за напоминание. Прошло много времени с тех пор, как я что-либо кодировал, и я не проверял свой код должным образом. Теперь он работает правильно.
Я рекомендую объяснять свой код, в идеале в комментариях внутри самого кода. Таким образом, вы вынуждены выражать свои идеи словами. Это может привести к тому, что вы сами найдете ответ, или к тому, что людям будет легче вам помочь.