Структуры данных и алгоритмы. Серия вопросов для интервью. Резюме случайных алгоритмов

задняя часть .NET алгоритм Linux

Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которым это нужно.Если есть какая-либо ошибка, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.

0 Обзор

Стохастические алгоритмы требуют большого знания теории вероятностей. Иногда трудно внимательно посмотреть на процесс вывода. Конечно, полезно иметь возможность полностью понять процесс вывода. Если вы не понимаете процесс вывода, это надо хотя бы вспомнить заключение. В этой статье обобщаются некоторые из наиболее распространенных тем по случайным алгоритмам, и она была написана несколько лет назад, когда я искал работу. Следует отметить, что использованная здесь случайная функцияrandInt(a, b)Предположим, что он может генерировать диапазон случайным образом[a,b]Целые числа внутри, то есть вероятность генерации каждого целого числа одинакова (хотя на практике это может быть невозможно, но не волнуйтесь, многое в этом мире случайно). Код этой статьи находится вздесь.

1 случайный массив

Предположим, вам дан массивA, который содержит элементы от 1 до N, и наша цель — построить равномерную случайную перестановку этого массива.

Общий подход заключается в создании массива для каждого элементаA[i]назначить случайный приоритетP[i], а затем отсортируйте массив по приоритету. Например, наш массивA = {1， 2， 3， 4}, если выбранный массив приоритетовP = {36， 3， 97， 19}, то можно получить последовательностьB={2, 4, 1, 3},так как3имеет наивысший приоритет (97), а2имеет самый низкий приоритет (3). Этот алгоритм должен генерировать массив приоритетов, а также должен использовать массив приоритетов для сортировки исходного массива, который здесь подробно описываться не будет, и есть лучший способ получить случайный массив.

Лучший способ генерировать случайные перестановочные массивы — это перестановка на месте (in-place) задан массив, который может бытьO(N)завершено в срок. Псевдокод выглядит следующим образом:

RANDOMIZE-IN-PLACE ( A , n ) 
	for i ←1 to n do 
		swap A[i] ↔ A[RANDOM(i , n )]

Как показано в коде,iНа итерациях элементA[i]из элементаA[i...n]случайно выбранный вiПосле итераций мы больше никогда не меняемсяA[i].

A[i] находится в любой позиции j с вероятностью 1/n. Это можно легко вывести, например.A[1]Вероятность оказаться на позиции 1 равна1/n, это очевидно потому, чтоA[1]Вероятность того, что элемент от 1 до n не будет заменен, равна1/n, а дальше не изменитсяA[1]. иA[1]Вероятность оказаться на позиции 2 также1/n,так какA[1]Чтобы быть в положении 2, он должен бытьA[k](k=2...n) поменять местами, а второйA[2]иA[k]заменить сначала наA[k]Вероятность обмена(n-1)/n, а вероятность второй замены равна1/(n-1), поэтому полная вероятность(n-1)/n * 1/(n-1) = 1/n. То же самое можно сделать и для других случаев.

Конечно, это условие может быть только необходимым условием случайного расположения массива, т. е. удовлетворения элементовA[i]в местеjВероятность1/nЭто не обязательно означает, что это создает массив случайных перестановок. потому что он может производить меньше перестановок, чемn!, хотя вероятности равны, но количество перестановок не удовлетворяет требованиям.Такой контрпример есть выше во введении к алгоритму.

алгоритмRANDOMIZE-IN-PLACEМожно сгенерировать равномерную случайную перестановку, и процесс ее доказательства выглядит следующим образом:

Во-первых, дается понятие расположения k. Так называемое расположение k — это расположение выбора k элементов из n элементов, тогда оно имеет в общей сложностиn!/(n-k)!к перестановок.

Инвариант цикла: до i-й итерации цикла for для каждой возможной перестановки i-1 вероятность того, что подмассив A[1...i-1] содержит перестановку i-1, равна(n-i+1)! / n!.

  • Инициализация: перед первой итерацией, i=1, инвариант цикла означает, что для каждой перестановки 0 вероятность того, что подмассив A[1...i-1] содержит перестановку 0, равна(n-1+1)! / n! = 1. A[1...0] — пустой массив, а перестановка 0 не содержит элементов, поэтому вероятность того, что A содержит все возможные перестановки 0, равна 1. Инвариант установлен.

  • Обслуживание: предположим, что до i-й итерации перестановка i-1 массива появляется вA[1...i-1]Вероятность(n-i+1) !/ n!, то после i-й итерации все i перестановок массива появляются вA[1...i]Вероятность(n-i)! / n!. Сделаны следующие выводы:

    • Рассмотрим специальную i перестановку p = {x1, x2, ... xi}, который упорядочен i-1 p' = {x1, x2,..., xя-1} с последующим xiсоставляют. Установите две переменные события E1 и E2:

  • E1 для алгоритма будет ранжироватьсяp'помещен вA[1...i-1]событий, вероятность известна по индуктивной гипотезе какPr(E1) = (n-i+1)! / n!.

  • E2 — изменить x на i-й итерацииiвставитьA[i]событие. Таким образом, мы получаем i перестановок, появляющихся вA[1...i]ВероятностьPr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}. иPr {E2 | E1} = 1/(n − i + 1),такPr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! / n! = (n − i )! / n!.

  • конец: когда это закончитсяi=n+1, поэтому мы можем получитьA[1...n]это заданные n перестановок с вероятностью1/n！.

Код реализации C выглядит следующим образом:

void randomInPlace(int a[], int n)
{
    int i;
    for (i = 0; i < n; i++) {
        int rand = randInt(i, n-1);
        swapInt(a, i, rand);
    }
}

расширять

Если приведенный выше алгоритм случайной перестановки написан следующим образом, может ли он также генерировать равномерную случайную перестановку?

PERMUTE-WITH-ALL( A , n ) 
	for i ←1 to n do 
		swap A[i] ↔A[RANDOM(1 , n )]

Обратите внимание, что этот алгоритм не может производить однородные случайные перестановки. предполагаемыйn=3, то алгоритм может дать3*3*3=27выходы, в то время как 3 элемента имеют только3!=6различные перестановки такие, что вероятность появления этих перестановок равна1/6, то число вхождений m каждой перестановки должно быть удовлетвореноm/27=1/6, очевидно, такое целое не подходит. На самом деле вероятность появления каждой комбинации такова, например:{1,2,3}Вероятность возникновения4/27, не равно1/6.

Договариваться вероятность
<1, 2, 3> 4/27
<1, 3, 2> 5/27
<2, 1, 3> 5/27
<2, 3, 1> 5/27
<3, 1, 2> 4/27
<3, 2, 1> 4/27

2 Выберите число наугад

вопрос:Учитывая поток целых чисел неизвестной длины, как мне случайным образом выбрать число? (Так называемый случайный выбор гарантирует, что каждое число будет выбрано с равной вероятностью)

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

Решение 2:Если поток данных очень длинный, это может быть так:

  • Если поток данных заканчивается после 1-го числа, то требуется 1-е число.
  • Если поток данных заканчивается после второго числа, то мы выбираем второе число с вероятностью 1/2, и заменяем ранее выбранное случайное число на второе число с вероятностью 1/2, чтобы получить новое случайное число.
  • ......
  • Если поток данных заканчивается после n-го числа, то мы выбираем n-е число с вероятностью 1/n, то есть заменяем ранее выбранное случайное число на n-е число с вероятностью 1/n, чтобы получить новое случайное номер .

Простой способ сделать это - использовать случайную функциюf(n)=bigrand()%n,вbigrand()Возвращает большое случайное целое число, когда поток данных достигает первогоnчисло, еслиf(n)==0, затем замените ранее выбранное случайное число, чтобы гарантировать, что вероятность каждого выбранного числа равна1/n. как когдаn=1время, тогдаf(1)=0, затем выберите первое число, когдаn=2, то вероятность того, что будет выбрано второе число, равна1/2и т. д., когда длина цифры равна n, вероятность того, что выбрана n-я цифра, равна1/n. Код выглядит следующим образом (Примечание: в Linux/MacOS,rand()Функция уже может возвращать большое случайное число, просто используйте его как biggrand()):

void randomOne(int n)
{
    int i, select = 0;
    for (i = 1; i < n; i++) {
        int rd = rand() % n;
        if (rd == 0) {
            select = i;
        }
    }
    printf("%d\n", select);
}

3 Произвольно выберите M номеров

вопрос: ввод программы состоит из двух целых чисел m и n, гдеm<n, выход0~n-1Упорядоченный список из m случайных целых чисел в диапазоне, дубликаты не допускаются. Вероятностно, мы хотим иметь упорядоченный выбор без повторений, где каждый выбор происходит с равной вероятностью.

Решение 1:Сначала рассмотрим простой пример, когдаm=2，n=5, нам нужно из0~4Эти 5 целых чисел с равной вероятностью выберут 2 упорядоченных целых числа и не могут повторяться. Если выбрано в соответствии со следующими условиями:bigrand() % 5 < 2, то мы выбираем 0 с вероятностью2/5. Но мы не можем с той же вероятностью выбрать 1, потому что после выбора 0 мы должны взять1/4вероятность выбрать 1, а в случае невыбора 0, мы должны использовать2/4Выбирается вероятность 1. Выбранный псевдокод выглядит следующим образом:

select = m
remaining = n
for i = [0, n)
    if (bigrand() % remaining < select)
         print i
         select--
    remaining--

пока условия соблюденыm<=n, то программа выводит m упорядоченных целых чисел, не больше и не меньше. Множественного выбора не будет, потому что каждый раз, когда вы выбираете номер,select--, так что, когда выбор уменьшен до 0, он не будет выбран снова. При этом меньшего я не выберу, потому что каждый раз будуremaining--,когдаselect/remaining=1, число должно быть выбрано. Вероятность выбора каждого подмножества одинакова, например, здесь 2 из 5.C(5,2)=10подмножества, такие как{0，1}，{0，2}...и т. д., вероятность выбора каждого подмножества равна1/10.

Более общий вывод: количество подмножеств n, выбранных m, составляет в общей сложностиC(n,m), рассмотрим конкретную m-последовательность, такую ​​как0...m-1, то вероятность его выбора равнаm/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m), видно, что вероятности равны.

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

void randomMKnuth(int n, int m)
{
    int i;
    for (i = 0; i < n; i++) {
        if ((rand() % (n-i)) < m) {
            printf("%d ", i);
            m--;
        }
    }
}

Решение 2:Вы также можете использовать предыдущую идею случайного расположения массивов, сначала случайным образом расположить первые m чисел, затем отсортировать m чисел и вывести их. код показывает, как показано ниже:

void randomMArray(int n, int m)
{
    int i, j;
    int *x = (int *)malloc(sizeof(int) * n);
    
    for (i = 0; i < n; i++)
        x[i] = i;

    // 随机数组
    for (i = 0; i < m; i++) {
        j = randInt(i, n-1);
        swapInt(x, i, j);
    }

    // 对数组前 m 个元素排序
    for (i = 0; i < m; i++) {
        for (j = i+1; j>0 && x[j-1]>x[j]; j--) {
            swapInt(x, j, j-1);
        }
    }

    for (i = 0; i < m; i++) {
        printf("%d ", x[i]);
    }

    printf("\n");
}

4 rand7 генерирует проблему rand10

вопрос:Известно, что функция rand7() может генерировать случайные числа от 1 до 7, и каждое число имеет одинаковую вероятность.Напишите пожалуйста функцию rand10(), которая может генерировать случайные числа от 1 до 10, и каждое число имеет равную вероятность вероятность.

Решение 1:Чтобы сгенерировать случайное число от 1 до 10, мы либо делаем rand7() дважды, либо просто умножаем число, чтобы получить желаемое значение диапазона. Такие, как следующие формулы (1) и (2).

idx = 7 * (rand7()-1) + rand7() ---(1) 正确
idx = 8 * rand7() - 7           ---(2) 错误

Приведенная выше формула (1) может дать1-49случайное число, почему? Поскольку возможные значения rand7() равны 1-7, два rand7() могут давать 49 комбинаций, которые представляют собой ровно 49 чисел от 1 до 49, а вероятность появления каждого числа равна1/49, поэтому мы можем отбросить те, что больше 40, а затем взять(idx-1) % 10 + 1Вот и все. Уравнение (2) неверно, потому что оно генерирует числа с неравными вероятностями, а также не может сгенерировать 49 чисел.

   1  2  3  4  5  6  7
1  1  2  3  4  5  6  7
2  8  9 10  1  2  3  4
3  5  6  7  8  9 10  1
4  2  3  4  5  6  7  8
5  9 10  1  2  3  4  5
6  6  7  8  9 10  *  *
7  *  *  *  *  *  *  *

Решение основано на методе, который называется выборкой отбраковки. Основная идея состоит в том, чтобы возвращаться напрямую, пока генерируется случайное число в пределах целевого диапазона. Если сгенерированное случайное число не находится в целевом диапазоне, отбросьте значение и выполните повторную выборку. Поскольку числа в целевом диапазоне выбираются с равной вероятностью, создается такое равномерное распределение. код показывает, как показано ниже:

int rand7ToRand10Sample() {
    int row, col, idx;
    do {
        row = rand7();
        col = rand7();
        idx = col + (row-1)*7;
    } while (idx > 40);

    return 1 + (idx-1) % 10;
}

Поскольку диапазон строк составляет 1–7, а диапазон столбцов — 1–7, диапазон значений idx — 1–49. Значения больше 40 отбрасываются, оставляя число в диапазоне 1-40, которое возвращается по модулю. Давайте рассчитаем ожидаемое значение количества выборок, необходимых для получения числа, удовлетворяющего диапазону 1-40:

E(# calls to rand7) = 2 * (40/49) +
                      4 * (9/49) * (40/49) +
                      6 * (9/49)2 * (40/49) +
                      ...

                      ∞
                    = ∑ 2k * (9/49)k-1 * (40/49)
                      k=1

                    = (80/49) / (1 - 9/49)2
                    = 2.45

Решение 2:Приведенный выше метод требует около 2,45 вызовов функции rand7, чтобы получить число в диапазоне от 1 до 10, которое можно повторно оптимизировать ниже. Если числа больше 40, их не нужно сразу отбрасывать, мы можем вычесть 40 из чисел 41-49, чтобы получить случайные числа от 1 до 9, а rand7 может генерировать случайные числа от 1 до 7, которые могут генерировать случайные числа. числа от 1 до 63. . Для 1-60 мы можем вернуться напрямую, а 61-63 отбрасываются, поэтому нужно отбросить только 3 числа, что более эффективно, чем предыдущие 9. А для числа 61-63 после вычитания 60 получается 1-3, а ранд7 дает 1-7, так что число 1-21 можно использовать повторно.Для 1-20 возвращаем напрямую, а для 21 , отбросить его. На данный момент количество сбросов всего 1, а оптимизация идет дальше. Конечно, здесь также увеличилось количество обращений к rand7. Код выглядит следующим образом, а оптимизированное ожидание составляет около 2,2123.

int rand7ToRand10UtilizeSample() {
    int a, b, idx;
    while (1) {
        a = randInt(1, 7);
        b = randInt(1, 7);
        idx = b + (a-1)*7;
        if (idx <= 40)
            return 1 + (idx-1)%10;

        a = idx-40;
        b = randInt(1, 7);
        // get uniform dist from 1 - 63
        idx = b + (a-1)*7;
        if (idx <= 60)
            return 1 + (idx-1)%10;

        a = idx-60;
        b = randInt(1, 7);
        // get uniform dist from 1-21
        idx = b + (a-1)*7;
        if (idx <= 20)
            return 1 + (idx-1)%10;
    }
}

5 интересных вопросов о вероятностях

1) Взвешивание мяча

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

развязать: Алгоритм бинарного поиска был кратко изложен ранее, и мы знаем, что бинарный метод может ускорить поиск отсортированных массивов. Аналогично, например, в игре с числами, если вас просят угадать1-64Числа между ними можно угадать в течение 6 раз, используя метод дихотомии. Но проблема взвешивания в другом. В задаче на взвешивание 12 маленьких мячей, и плохой мяч может быть любым из них, поэтому вариантов 12. И плохой мяч может быть тяжелым или легким, так что в этой задаче всего12*2 = 24Возможность. Каждый раз, когда весы используются, выход весов平衡、左重、右重3 возможности, то есть можно свести возможность проблемы к исходной1/3, то всего24Возможность может быть в3взвешивал(3^3 = 27).

Почему самый понятный термин6-6не оптимально? существует6-6При взвешивании вероятность того, что весы уравновешены, равна 0, и оптимальной стратегией должно быть уравнивание вероятности весов при каждом взвешивании, чтобы все возможности ответа можно было разделить на три равные части.

Как это реализовать? Пронумеруйте шары от 1 до 12, используя4, 4метод взвешивания.

  • Мы сначала1 2 3 4и5 6 7 8Проведите первое взвешивание.
  • Если 1-й баланс, плохой мяч должен быть в9-12номер. тогда только9-124 шара с вероятностью9- 10- 11- 12- 9+ 10+ 11+ 12+8 возможностей. Далее будет9 10 11и1 2 3Взвешивание 2-й раз: если сбалансировано, то12Плохой мяч № 1. Взвесьте мяч № 12 вместе с мячом № 1 в третий раз, чтобы убедиться, легкий он или тяжелый. Если он не уравновешен, если он тяжелый, это означает, что плохой шар тяжелый, продолжайте взвешивать 9 и 10 шары, тяжелый шар — плохой шар, а если он сбалансирован, 11 — плохой шар.
  • Если 1-й раз не уравновешен, плохой мяч должен быть в1-8номер. тогда остается возможность1+ 2+ 3+ 4+ 5- 6- 7- 8-или1- 2- 3- 4- 5+ 6+ 7+ 8+,если1 2 3 4Здесь тяжело, можно положить1 2 6и3 4 5Сказал, что если сбалансировано, то должно быть7 8Если он легче, снова взвесьте 7 и 1, и вы сможете определить, какой из 7 и 8 плохой. Если неуравновешенный, предположим1 2 6Здесь тяжело, можно судить, что1 2тяжелый или5свет, зачем? потому что если это3+ 4+ 6-,но1 2 3 4Сравнивать5 6 7 8тяжелый, но1 2 6должно быть лучше, чем3 4 5светлый. Точно так же и в других ситуациях плохой мяч можно найти не более 3 раз.

Рисунок ниже иллюстрирует этот принцип более наглядно.

称球问题图示

2) Проблема рождения мальчиков и девочек

вопрос:Каково соотношение мужчин и женщин в патриархальных странах? В патриархальной стране каждая семья хочет иметь мальчика, и если у них будет девочка, они будут рожать еще, пока не будет мальчик. Каково соотношение мужчин и женщин в такой стране?

развязать:Еще 1:1. Во всех первых рожденных детях соотношение мужского и женского пола составляет 1:1, во всех рожденных вторым детям соотношение мужского и женского пола составляет 1:1, .... Во всех рожденных n детях соотношение мужского и женского пола остается 1:1. Таким образом, общее соотношение мужчин и женщин составляет 1:1.

3) Вопросы о свиданиях

вопрос:Эти двое встречаются в определенном месте с 5:00 до 6:00, тот, кто приходит первым, ждет 20 минут, чтобы уйти, спрашивая вероятность того, что они могут встретиться.

развязать:Предположим, что два человека прибывают в пункт назначения в 5:00 X и 5:00 Y соответственно, тогда условие их выполнения таково:|X-Y| <= 20, а весь диапазонS={(x, y): 0 =< x <= 60,  0=< y <= 60}, если нарисована ось координат, ситуация встречи представляет собой область, представленную на оси координат, а вероятность равна(60^2 - 40^2) / 60^2 = 5/9.

4) Проблема со шляпой

вопрос:Есть n клиентов. Каждый из них дает шляпу официанту в ресторане. Официант возвращает ее посетителю в случайном порядке. Каково ожидаемое количество клиентов, которые получат свою шляпу?

развязать:Проще решить эту задачу с помощью индикаторной случайной величины. Определим случайную величину X, равную количеству покупателей, которые могут получить свои шляпы. Мы хотим вычислить следующее:E[X]. заi=1, 2 ... n, который определяет Xi=I {покупатель i получает свою шляпу}, тогда X=X1+X2+...Xn. Поскольку порядок возврата шляп случайный, вероятность того, что каждый покупатель получит свою шляпу, равна 1/n, а именно Pr(Xi=1)=1/n, поэтому E(Xi)=1/n, поэтому E(X)=E(X1 + X2 + ...Xn)= E(X1)+E(X2)+...E(Xn)=n*1/n = 1, то есть примерно 1 покупатель может получить свою шляпу.

5) Парадокс дня рождения

вопрос:Какое минимальное количество человек может находиться в комнате, чтобы у двух человек день рождения совпадал?

развязать:Определить индикаторную переменную X для каждой пары (i, j) из k человек в комнате.ij= {дни рождения i и j совпадают}, тогда, когда дни рождения i и j совпадают, Xij=1, иначе Xij=0. Вероятность того, что два человека родились в один день Pr(Xij=1)=1/n. Затем используйте X для представления количества пар двух людей с одинаковым днем ​​рождения, тогда E(X)=E(∑ki=1∑kj=i+1Xij) = C(k,2)*1/n = k(k-1)/2n, пустьk(k-1)/2n >=1,доступныйk>=28, то есть по крайней мере 28 человек, чтобы ожидать, что дни рождения двух людей будут в один и тот же день.

6) Вероятностная задача обращения

вопрос:Если вероятность увидеть машину, проезжающую по шоссе через 30 минут, равна 0,95, каковы шансы увидеть машину, проезжающую через 10 минут? (при условии постоянной вероятности)

развязать:Предположим, что вероятность увидеть машину за рулем через 10 минут равна x, тогда вероятность не увидеть машину за рулем равна 1-x, а вероятность не увидеть машину за рулем через 30 минут равна(1-x)^3, это,0.05. Итак, получите уравнение(1-x)^3 = 0.05, решение уравнения дает, что x составляет около 0,63.

использованная литература

Категории