top-shop.ru
Фартук-накидка для детского
Комбинаторика списков

Головоломка с лилией

На пяти одинаковых на ощупь карточках написаны буквы: на двух "Л", на трех "И". Выкладываем наудачу все эти карточки подряд. Какова вероятность того, что мы выложим слово "Лилии"? Если решать эту задачу при помощи комбинаторных формул, то получится P = (3! * 2!) / 5! (число перестановок букв И на число перестановок букв Л - удовлетворяющих выпадению слова) разделить на общее число перестановок. Получаем 12/120 = 0.1

Попробуем проверить это, решив задачу на Прологе, путем перебора всех перестановок:

GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- [lilii].
compiling E:\lilii.pl for byte code...
E:\lilii.pl compiled, 7 lines read - 507 bytes written, 10 ms

yes
| ?- listing.

p(A) :-
 permutation(A, B),
 nth(1, B, l),
 nth(3, B, l).

yes
| ?- findall(X,p([l,i,l,i,i]),Y),length(Y,Z).

Y = [_,_,_,_,_,_,_,_,_,_,_,_]
Z = 12

(10 ms) yes
| ?- findall(X,p([l,l,l,l,l]),Y),length(Y,Z).

Y = [_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_]
Z = 120

yes
| ?- 

Итак, P = 12/120 = 0.1, т.е. число вариантов перестановки элементов списка, удовлетворяющих условию (выпадение слова ЛИЛИИ) определено верно. Заодно мы проверили и общее число вариантов перестановки.

Два белых шара

В ящике находится двадцать шаров, из них 12 белых и 8 черных. Какова вероятность вытащить два белых шара?

Понятно, что от того, вытащим мы оба шара одновременно, или по очереди, вероятность не изменится. Более того, исходная ситуация для обоих вытаскиваний строго определена. В самом деле, мы точно знаем сколько и каких шаров будет в ящике и к началу первого опыта (вынимаем первый белый шар) и второго (ведь мы знаем, что перед этим вынули один белый шар).
P1 - вероятность того, что первый шар - белый (12/20)
P2 - вероятность того, что второй шар - белый (11/19)
P3 = P1 * P2 ~ 0.347 (события независимые)

А вот попытка решить эту задачу методом перестановки списка на Прологе весьма затруднительна! Просто общее количество перестановок: 20! = астрономическая цифра. Очень жаль, что перестановка столь неэффективна, - ведь иначе мы смогли бы решить эту задачу практически такой же Пролог программой, что и для головоломки с лилиями. С другой стороны, это позволяет нам понять, что нужно думать своей головой, а не компьютером.
GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- [sphere].
compiling Z:\MyProject\prolog\sphere.pl for byte code...
Z:\MyProject\prolog\sphere.pl compiled, 7 lines read - 552 bytes written, 10 ms

(10 ms) yes
| ?- listing.

p(A) :-
 permutation(A, B),
 nth(1, B, 1),
 nth(2, B, 1).

yes
| ?- findall(X,p([0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1]),Y),length(Y,Z).
Я не стал ждать ответа от этой программы.
Блог изучающего Пролог

содержание