Речь в основном будет идти...

четверг, 25 октября 2012 г.

Еще одна разновиднасть пародокса Монти-Холла

У нас есть три карты.
1. одна с обеих сторон черная
2. одна с обеих сторон белая
3. одна карта с одной стороны черная, а с другой белая
их кладут в шляпу, перемешивают, вытягивают одну наугад и кладут на стол
вы видите одну сторону этой карты - она черная
какая вероятность того, что другая сторона этой карты тоже черная?

Неплохая задачка из ЕГЭ для размитки

найдено на RSDN

В классе есть мальчики и девочки. Для них устроили 2 "культпохода" — в кино и в театр. Каждый хотя бы куда-нибудь сходил, кто-то побывал и в кино, и в театре. Известно, что доля мальчиков, среди всех учеников, посетивших театр, не превосходит 3/13, а доля мальчиков, среди всех учеников, посетивших кино, не превосходит 2/7. Вопрос — какова минимально возможная доля девочек в классе?

Выборы Венецианского Дожа.

Процедура выбора "дожа" (самый главный перец в Венеции) с 1268 года и до упразнения этого титула (в 1797).

1. Есть некий "Большой совет". В него входят люди с капиталом либо со связями.
2. Он каким-то образом выбирает 41 человека.
3. Эти 41 человек выбирают дожа.

Теперь веселое - как именно выбирались эти 41 человек.

1. Сначала голосованием из "Большого совета" выбирается 30 человек.
2. Из этих 30 как-то выбиралось 9.
3. Эти 9 человек выбирали 40 человек из "Большого совета".
4. "Большой совет" выбирал 12 человек из этих 40.
5. Выбранные на предыдущем этапе 12 человек выбирали 25 человек из "Большого совета".
6. "Большой совет" выбирал 9 человек из этих 25.
7. Эти 9 выбирали 45 человек.
8. Группу из 45 просеивали до 11.
9. Эта группа из 11 выбирала 41 человека.
10. Эти 41 человек выбирают дожа.

Думаю там еще были какие-то условия... Спасало их только одно - выбранный таким образом главарь Венеции рулил вплоть до своей скоропостижной.

пятница, 19 ноября 2010 г.

1000 лет истории Европы

четверг, 11 ноября 2010 г.

Ну и еще одна практически классическая задача

You are given an array X with n elements. Can you compute in linear time a new array A with n elements, where A[i] is the product of all elements in X, but X[i] is excluded. You cannot use division, you may use additional space

Ну и классическое решение примерно такое:

int* test(int* n,int size) 
{ 
    int* a = new int[size]; 
    for(int i = 0,temp = 1;i,size;temp*=n[i],++i) 
        a[i]=temp; 
    for(int i=size-1,temp=1;i>=0;temp*=n[i],--i) 
        a[i]*=temp; 
    return a; 
} 

а вот красивое функциональное O(N) решение я придумать не могу...

Еще одна почти стандартная задача

All numbers in an array repeat twice except two numbers which repeat only once. All the numbers are placed randomly. Find out efficiently the two numbers that have not repeated with O(1) extra memory.

O(1) extra memory - значит никаких хэшей.
очевидный ответ - отсортировать массив - слишком очевиден. А поскольку он выполняется за O(NlogN) можно предположить что это достичь результата можно за O(N) как минимум.

среда, 10 ноября 2010 г.

интересная задачка

Given two integer arrays and the size of each array.
Determine if arrays match.
Order of elements does not matter.
Number of occurrences does matter.
Return true for match, false for no match
Computational complexity is important.

Интересна она тем что первые пришедшие в голову решения - сортировка O(NlogN) либо хэш O(N) не оптимальны.

Гораздо эффективнее было бы посчитать какую-то характеристику этих массивов и затем сравнить эти характеристики. Возможный вариант - (сумма_элементов/произведение_элементов). Ну не без ограничений,да.
Но важна сама идея - вместо сравнения элементов сравнивать какую-то характеристику на основании этих элементов.