Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »

задачка


картман ©   (20.04.18 11:00

Есть шарики k цветов. Вероятность выпадения шарика любого цвета - одинакова и со временем не меняется. Последовательно выбирается n шаров.
 Какова вероятность того, что в выборке присутствуют шары всех цветов?


Pavia ©   (20.04.18 18:56[1]

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


kilkennycat ©   (20.04.18 21:18[2]

50% - либо присутствуют, либо нет.


SergP ©   (20.04.18 22:01[3]

если n<k то 0%


ухты ©   (20.04.18 23:51[4]

это какие шары, из ореха чтоли?


Тимохов Дима ©   (21.04.18 16:21[5]

для K = 2

K! / K^K * (1 / K ^ (N - K + 1) - 1) / (1 / K - 1)

Конечно, можно красивее записать (К на 2 заменить), но лень.

Для K > 2 надо думать, хотя логика понятна.

Могу сказать, как для K = 2 делал.

1. Обозначим P1 и P2 - вероятности первого и второго шарика. Они равны 1/К, но пусть будет с номерами.

2. N=K
Успех - P1,P2 или P2,P1. В итоге успех 1/(P1*P2)+1/(P2*P1). Или 2/K^K

3. N=K+1
Успех:
из пред. примера 2/K^K
плюс
P1,P1,P2 или P2,P2,P1.
В итоге
2/K^K + 2/K^(K+1)
и т.д.

Для K > 2 сложнее, ибо больше вариантов.
Например
P1P1P2P3
P1P1P3P2
P1P2P2P3
P1P2P1P3
и т.д. надо считать.
Ключевые слова - сочетание, перестановка, размещение.

Кстати для N=K будет K! / K^K.


картман ©   (21.04.18 17:55[6]


> Ключевые слова - сочетание, перестановка, размещение.

есть еще термин - ключевой-таки))


Тимохов Дима ©   (21.04.18 18:07[7]

Ну вообще задача сложная. Думал для фана сделать. Что-то не сдюжил.
Могу только кодом экспериментальной проверки поделиться)))


procedure TForm1.Button1Click(Sender: TObject);
const
  cSteps = 1000000;
  cK = 2;
  cN = 20;

  function kFact(const aV: Integer): Integer;
  begin
      if aV < 1 then
        Result := 0
      else
        if aV = 1 then
           Result := 1
        else
           Result := aV * kFact(aV - 1);
  end;

  function kP(const aV, aP: Integer): Integer;
  begin
     if aP = 0 then
        Result := 1
     else
        if aP = 1 then
           Result := aV
        else
           Result := aV * kP(aV, aP-1);
  end;

var
  kI, kJ: Integer;
  kF: array[0..cK-1] of Boolean;
  kAll: Boolean;
  kFound: Integer;
  kExperiment, kFormula: Double;
begin
  kFound := 0;
  for kI := 1 to cSteps do
  begin
     FillChar(kF, SizeOf(kF), 0);
     for kJ := 1 to cN do
     begin
        kF[Random(cK)] := True;
     end;
     kAll := True;
     for kJ := 0 to High(kF) do
     begin
        if not kF[kJ] then
        begin
           kAll := False;
           Break;
        end;
     end;
     if kAll then
        Inc(kFound);
  end;

  kExperiment := kFound / cSteps;
  kFormula := kFact(cK) / kP(cK, cK) * (1 / kP(cK, cN-cK+1) - 1) / (1 / cK - 1);

  Memo1.Lines.Add(Format('Опыт=%.6f Формула=%.6f Разница=%.6f', [kExperiment, kFormula, kExperiment-kFormula]));
end;


Тимохов Дима ©   (21.04.18 18:16[8]

А тебе вообще зачем это?

ЗЫ
Тут понятно, как делать.
Например, К=3, N = 4.
Выписываешь все успешные комбинации из четырех шаров (из трех - понятно, это К!/К^К - кол-во успешных кобинаций это размещение от K, т.к. K!, 1/K - вероятность конкретного шара, 1/K^K - вероятность конкретной последовательности в одной успешной комбинации).

1123
1132
1213
1223
1332
1312
21...
22...
23...
31...
32...
33...

Пытаешься понять, что тут за комбинаторика.
Потом для N=5 и т.д.

Думаю, мат индукцией тут что-то нарисуется.
Но что-то не соображу на коленке, думать шибко нада....


картман ©   (21.04.18 20:31[9]


> А тебе вообще зачем это?

пятничная задачка - я решил, по работе нужно было.


Mystic ©   (21.04.18 21:06[10]

Я бы рекуррентно решал.

Пусть P(n, k) - вероятность того, что в выборке присутствуют шарики всех цветов. Пусть A(n, k) - вероятность того, что в выборке присутствует ровно k шариков заданного цвета.

Берём первый шарик. Пусть он цвета c. Тогда в оставшейся последовательности из n-1 шарика, шарик цвета c может появится 0, 1, ... n-1 раз. Это полная группа событий, вероятности этиз событий равны A(n-1, 0), A(n-1, 1), A(n-1, 2) ... A(n-1, n-1) соответственно.

В каждом из этих случаев надо умножить на верноятность присутствия k-1 шарика в оставшихся шариках, это будет P(n-1, k-1), P(n-2, k-1), P(n-3, k-1), ... P(0, k-1)

P(n, k) = P(n-1, k-1) * A(n-1, 0) + P(n-2, k-1) * A(n-1, 1) + ... A(n-1, n-1) * P(0, k-1)

Ну и теперь надо поднять формулы для A, упростить, ...


картман ©   (21.04.18 21:26[11]


> Но что-то не соображу на коленке, думать шибко нада....

допустим, в группе из 100 человек 60 любят пиво, 40 - вино, 30 - водку. Пиво и вино любят 20 человек. Вино и водку - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько трезвенников?

n := 100 - 60  - 40 - 30.
Но тут мы вычли по два раза тех, кто любит оба напитка, тогда нужно их прибавить:
n := n + 20 + 15 + 10
а теперь мы лишний раз приплюсовали любителей всего, значит:
n := n - 10

+-+-...


Тимохов Дима ©   (21.04.18 22:24[12]


> картман ©   (21.04.18 21:26) [11]

Я пас)
Будут формулы, поставлю в мой код выше. Проверим)
Пока понаблюдаю.


Тимохов Дима ©   (21.04.18 22:35[13]


> картман ©   (21.04.18 21:26) [11]
> допустим, в группе из 100 человек 60 любят пиво, 40 - вино,
>  30 - водку. Пиво и вино любят 20 человек. Вино и водку
> - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько
> трезвенников?

Вроде 5.
(наверное младенцы)


Тимохов Дима ©   (22.04.18 13:04[14]


> картман ©   (20.04.18 11:00) 


Решил для случаев:
1. N=K
P(K,N) = K!/K^K

2. N=K+1
P(K,N) = K!/K^K + K! * K * (K-1) / 2 / K ^ (K+1)
И что интересно, первый раз в жизни подобную задачу решал численно. Хороший метод. Надо будет на будущее запомнить.
Вся проблема была в коэффициенте K! * K * (K-1) / 2 - т.е. сколько удачных успешных комбинаций из К+1 шаров. Исходя из моего кода выше подобрал коэффициент для K=2,3,4,5 (это 2,18, 144, 1200), увидел зависимость (K! * сумма арифм. прогрессии), вывел формулу. Проверил для для К до 15. Все сходится. Но объяснить K! * K * (K-1) / 2 не могу - мозгов не хватает.

3. Думаю для N=K+2 тоже можно подбором формулу увидеть. А потом по индукции доказать в общем случае.


картман ©   (22.04.18 16:25[15]


> K! * K * (K-1) / 2

К! - ну, это кол-во перестановок
K * (K-1) / 2 - если привести к одному знаменателю ф-лу:
K!/K^K + K! * K * (K-1) / 2 / K ^ (K+1)
в числителе получится
К!* К(К+1)/2, второй множитель - кол-во вариантов выбрать два шарика одного цвета(при n = k+1 один из цветов же будет выбран дважды) и это не ариф.прогрессия, а Це из ка по два.


картман ©   (22.04.18 17:10[16]


> Це из ка по два.

из ка плюс один


Тимохов Дима ©   (22.04.18 18:23[17]


> картман ©   (22.04.18 16:25) [15]

Спасибо за разъяснения. Я пока не понял, но разберусь. Ибо интересно.
Комбинаторика и вообще тервер не были моими любимыми. Учился на потоке матметодов - конкретно, выпуклая конечномерная оптимизация.

Тем не менее, хочу пояснить про арифм. прогрессию. Решил то верно для N=K+1. И потом, считаю интересным, что из компьютерного моделирования можно сделать качественный вывод.

Итак, было понятно, что д.б. K!/K^K+M/K^(K+1).
Знаменатель степень 1/K, т.к. выборы независимы.
А что с M?
Экспериментально программой выше нашел, что:
K N M
1 2 1
2 3 2    = 2! * 1 = 2! * (1)
3 4 18   = 3! * 3 = 3! * (1+2)
4 5 144  = 4! * 6 = 4! * (1+2+3)
5 6 1200 = 5! * 10 = 5! * (1+2+3+4)

Из чего сделал предположение, что:
K N M
6 7 10800 = 6! * 15 = 6! * (1+2+3+4+5)
7 8 105840 = 7! * 21 = 7! * (1+2+3+4+5+6)
8 9 1128960 = 8! * 28 = 8! * (1+2+3+4+5+6+7)

И оказался прав - до K=15 проверил, все верно.

Дальше дело техники получить M как K!*K*(K-1)/2, где K*(K-1)/2 - как раз сумма арфим. прогрессии от 1 до K-1.


картман ©   (22.04.18 20:54[18]

Шикарно)) осталось для любого случая(там, кстати, сумма с интересными свойствами получается: при к > n равна нулю, насколько бы эти числа не отличались)


Тимохов Дима ©   (22.04.18 20:56[19]


> картман ©   (22.04.18 20:54) [18]
> Шикарно)) осталось для любого случая(там, кстати, сумма
> с интересными свойствами получается: при к > n равна нулю,
>  насколько бы эти числа не отличались)


Будет время, сделаю. Все же "завело" меня то, что из количественного численного анализа можно получить качественный вывод.
Чувствуешь себя ученым))) Гипотезы и т.д.


SergP ©   (23.04.18 01:12[20]


> Mystic ©   (21.04.18 21:06) [10]


Хм. Насчет рекурсии я думал так:
Пусть k - общее количество цветов, как в условии
n - длина последовательности
r - количество цветов в последовательности.

тогда:

function p(k,n,r:integer):extended;
begin
if r>n
  then Result:=0
  else if r=1
    then  Result:=1/power(k,n-1)
    else result:=p(k,n-1,r-1)*(k-r+1)/k+p(k,n-1,r)*r/k;
end;


т.е. если например имеется 5 цветов и последовательность из 7 шариков то вызываем функцию так:
px:=p(5,7,5);

Вот только как теперь с него сделать общую формулу - пока не придумал.


SergP ©   (23.04.18 10:28[21]

В таком виде понятнее должно быть:
function P(k,n:integer):extended;
 function SubP(n,r:integer):extended;
 begin
   if r>n  then Result:=0
   else if r=1 then  Result:=1/power(k,n-1)
   else Result:=((k-r+1)*SubP(n-1,r-1) + r*SubP(n-1,r))/k;
 end;
begin
 Result:=SubP(n,k);
end;


KSergey ©   (24.04.18 09:06[22]

Всегда было любопытно: почему большинство задач - про комбинаторику и т.п. тервер?
у кого-то в жизни встречаются такого рода задачи? или это просто типичная тема для интеллектуалов, типа как шахматы?
в самом деле интересно (про реальные задачи у вас на работе, связанные с этим)


картман ©   (24.04.18 11:41[23]


> в самом деле интересно (про реальные задачи у вас на работе,
>  связанные с этим)



> картман ©   (21.04.18 20:31) [9]
>
>
> > А тебе вообще зачем это?
>
> пятничная задачка - я решил, по работе нужно было.


KSergey ©   (24.04.18 11:45[24]

В какой области жизнедеятельности применяется ваш софт?


картман ©   (24.04.18 12:34[25]

логистика


картман ©   (24.04.18 12:39[26]

в общем, такая вот формулка получается: https://yadi.sk/i/P2A-0_Zv3UiLtc


картман ©   (24.04.18 12:45[27]

интересно, что числитель при k>n равен нулю))


SergP ©   (24.04.18 13:04[28]

А можно интереса формулу сюда написать, или выложить на что-то более доступное? А то самому интересно, но яндекс у нас в/на Украине заблокирован, а искать какой-нить прокси-сервер или делать что-то другое для обхода - как-то лень.


xayam ©   (24.04.18 13:16[29]


> а искать какой-нить прокси-сервер или делать что-то другое
> для обхода - как-то лень

во времена, когда блокируют рутрекер и телеграм, прокси должны быть под рукой :)


SergP ©   (24.04.18 14:04[30]


> во времена, когда блокируют рутрекер и телеграм, прокси
> должны быть под рукой :)


Ок. ты меня убедил. Пришлось найти все-таки проксик. Посмотрел формулу.


Тимохов Дима ©   (24.04.18 15:00[31]


> картман ©   (24.04.18 12:39) [26]
> в общем, такая вот формулка получается: https://yadi.sk/i/P2A-
> 0_Zv3UiLtc

C - это что?

C(n,k) = n! * / (k!*(n-k)!)

?


KSergey ©   (24.04.18 15:42[32]

> SergP ©   (24.04.18 14:04) [30]
> Ок. ты меня убедил. Пришлось найти все-таки проксик.

Opera с её vpn
Самое простое и готовое "из коробки"
поражаюсь тому, что её не блокируют


SergP ©   (24.04.18 16:44[33]


> KSergey ©   (24.04.18 15:42) [32]


Да просто не так часто и бывает необходимость лазить по яндексу, за время действия блокировки он мне первый раз понадобился... Ну и еще ранее один раз была необходимость зайти на сайт drweb.  Посему и не обзавелся чем-нить постоянным для обхода блокировки, оба раза просто искал прокси, находил и заходил через них. А что касается остального заблокированного, то вконтакте и одноклассники мне и не нужны (вообще не перевариваю такие вещи, как вконтакте, одноклассники, твиттер, фейсбук, телеграм, и прочие, т.е. все что называется "социальные сети"). А mail.ru - ИМХО вообще правильно сделали, что заблокировали (вот только потом его почему-то разблокировали), ибо это рассадник различной гадости, той что в инете люди называют "вирусы от mail.ru" (спутник, "браузер" Амиго и пр.). А все остальные российские сайты, которые бывают мне нужны нормально работают, их никто не блокировал.


картман ©   (24.04.18 16:56[34]


> C(n,k) = n! * / (k!*(n-k)!)

да


Тимохов Дима ©   (24.04.18 17:38[35]


> картман ©   (24.04.18 16:56) [34]

Да, все верно) Формулу не понял, но мой тестовый стенд показал правильность.
Будет время своим способом попытаюсь вывести твою формулу.


Sha ©   (24.04.18 17:55[36]

>Тимохов Дима ©   (24.04.18 17:38) [35]
>Будет время своим способом попытаюсь вывести твою формулу.

гугли "формула включений-исключений"


Sha ©   (25.04.18 09:38[37]

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


Тимохов Дима ©   (25.04.18 11:11[38]

какие вы все умные))
я вот только аналитически для N=K решил.
и численно для N=K+1.


DayGaykin ©   (21.05.18 13:26[39]


> Sha ©   (25.04.18 09:38) [37]
> Кроме прямого подсчета с раскрытием скобок методом включений-
> исключений, также легко получить результат по индукции.

Если не сложно, распиши, пожалуйста


Sha ©   (21.05.18 23:07[40]

>DayGaykin ©   (21.05.18 13:26) [39]

Шар одного из K цветов может оказаться на каждом из N мест. Поэтому имеем всего K^N различных исходов (это первое слагаемое).

Нас интересуют только исходы, использующие шары ровно K цветов. Поэтому из общего числа надо вычесть исходы, содержащие шары K-1 или менее цветов. Если просто вычесть C(K,K-1)*(K-1)^N (это второе слагаемое), то вместе с однократным вычитанием исходов для K-1 цветов мы ошибочно многократно вычтем исходы для K-2 и меньшего числа цветов, поэтому надо компенсировать ошибку. Затем компенсировать ошибку компенсации, и т.д.

Идею легче будет понять, если нарисовать овалы, как обычно это делают, изображая множества для иллюстрации включений-исключений.


aka ©   (22.05.18 20:10[41]

Вообще эта задача легко решается в 11-мерном многообразии методом Колывагина-Флаха


версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо