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

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

задачка


картман ©   (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 равна нулю,
>  насколько бы эти числа не отличались)


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


Страницы: 1 2 3 версия для печати

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

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







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


Наверх

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