Директан начин да се израчуна тражена вероватноћа је да се израчуна збир серије бројева која се добија тако што се за свако \(k\) од 0 до \(n\) израчуна вредност \(\frac{(-1)^k}{k!}\). Степен \((-1)^k\) се може израчунати функцијом pow или се може одредити гранањем, пошто је \((-1)^k = 1\) за парне вредности \(k\) и \((-1)^k = -1\) за непарне вредности \(k\). Факторијел \(k!\) се може израчунати множењем серије бројева од \(1\) до \(k\).
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
// faktorijel broja n
double faktorijel(int n) {
double p = 1.0;
for (int i = 2; i <= n; i++)
p *= i;
return p;
}
// verovatnoca da nijedna devojcica nije uzela iste klizaljke:
// zbir 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 0.0;
for (int k = 0; k <= n; k++)
p += pow(-1, k) / faktorijel(k);
return p;
}
int main() {
int n;
cin >> n;
cout << fixed << showpoint << setprecision(14)
<< verovatnoca(n) << endl;
return 0;
}Сложеност. Израчунавање \(k\)-тог сабирка захтева \(O(k)\) операција, па је за сабирање \(n\) сабирака потребно време \(O(n^2)\).
Ефикасније решење се може добити ако се уочи да бројеви \(1 = \frac{(-1)^0}{0!}\), \(-1 = \frac{(-1)^1}{1!}\), \(\frac{1}{2} = \frac{(-1)^2}{2!}\), \(-\frac{1}{6} = \frac{(-1)^3}{3!}\) итд. чине веома правилну серију у којој се сваки наредни члан може добити инкрементално, множењем претходног члана вредношћу \(-\frac{1}{k}\). Дакле, у овом задатку се користи како инкременталност серије парцијалних збирова (у склопу алгоритма сабирања), тако и инкременталност серије самих сабирака, који су заправо парцијални производи правилне серије \(-\frac{1}{1}, -\frac{1}{2}, -\frac{1}{3}, -\frac{1}{4}, \ldots\) Ако са \(x_k\) обележимо сабирак \(k\), тада је \(x_0 = \frac{(-1)^0}{0!} = 1\), док је \(x_{k+1} = -\frac{1}{k} \cdot x_k\).
Током имплементације ћемо одржавати две променљиве. Прва ће да представља збир до сада сабраних сабирака, а друга текући сабирак. Збир и текући члан иницијализоваћемо на вредност 1 (то је вредност \(\frac{(-1)^0}{0!}\)). У сваком кораку петље у којој \(k\) узима вредности од 1 до \(n\) текући члан ћемо ажурирати множењем са вредношћу \(-\frac{1}{k}\) и додаваћемо га на збир. Након завршетка петље, збир ће садржати тражену вероватноћу коју ћемо исписати са траженим бројем децимала.
Добар савет приликом израчунавања збирова овог типа је да се израчуна количник два суседна сабирка и да се провери да ли се он можда веома једноставно израчунава у функцији од \(k\) (у овом случају тај количник је \(\frac{-1}{k}\)). Уместо количника, могуће је користити и разлику два узастопна сабирка.
#include <iostream>
#include <iomanip>
using namespace std;
// verovatnoca da nijedna devojcica nije uzela iste klizaljke:
// zbir 1 - 1/1! + 1/2! + ... + (-1)^n/n!
double verovatnoca(int n) {
double p = 1.0;
// tekuci element zbira (-1)^k/k!
double xk = 1.0;
for (int k = 1; k <= n; k++) {
// izracunavamo sledeci clan mnozenjem prethodnog sa -1/k
xk *= -1.0/k;
// dodajemo ga na z
p += xk;
}
return p;
}
int main() {
// broj devojcica
int n;
cin >> n;
// ispisujemo trazenu verovatnocu
cout << fixed << showpoint << setprecision(14)
<< verovatnoca(n) << endl;
return 0;
}Сложеност. Израчунавање \(k\)-тог сабирка на основу претходног захтева само \(O(1)\) операција, па се израчунавање збира \(n\) сабирака врши у времену \(O(n)\). Додуше, у овом задатку \(n\) је веома мали број, па се на овај начин не постиже значајно убрзање, али у другим сличним задацима оптимизација на основу инкременталности може бити веома значајна.
Доказ коректности. Ко жели да зна више?
На крају, образложимо и како се дошло до формуле која је у задатку дата. Пермутације у којима ни један елемент није на свом месту се називају деранжмани. Њихов број је могуће одредити на основу формуле укључивања-искључивања. Размотримо скуп пермутација од 4 елемента. Њега чине пермутације \(1234\), \(1243\), \(1324\), \(1342\), \(1423\), \(1432\), \(2134\), \(2143\), \(2314\), \(2341\), \(2413\), \(2431\), \(3124\), \(3142\), \(3214\), \(3241\), \(3412\), \(3421\), \(4123\), \(4132\), \(4213\), \(4231\), \(4312\), \(4321\) од чега су деранжмани \(2143\), \(2341\), \(2413\), \(3142\), \(3412\), \(3421\), \(4123\), \(4312\) и \(4321\). Укупно пермутација има \(4!\). Од тог броја треба одузети број пермутација којима се бар један елемент налази на свом месту. Можемо разматрати пермутације у којима се 1 налази на свом месту, а остали бројеви су произвољно испермутовани (то су \(1234\), \(1243\), \(1324\), \(1342\), \(1423\), \(1432\)), у којима се број 2 налази на свом месту, а остали бројеви су произвољно испермутовани (то су \(1234\), \(1243\), \(3214\), \(3241\), \(4213\), \(4231\)), у којима се број 3 налази на свом месту, а остали бројеви су произвољно испермутовани (то су \(1234\), \(1432\), \(2134\), \(2431\), \(4132\), \(4231\)) и оне у којима је 4 на свом месту, а остали бројеви су произвољно испермутовани (то су \(1234\), \(1324\), \(2134\), \(2314\), \(3124\), \(3214\)). Њих има \(4 \cdot 3!\). Преостале пермутације су деранжмани и број деранжмана се може добити тако што се од укупног броја пермутација одузме број оних пермутација које фиксирају неки елемент. Проблем настаје због тога што су неке пермутације бројане више пута (на пример, пермутација \(1243\) је бројана и у оквиру пермутација које елемент 1 остављају на свом месту и у оквиру пермутација које остављају број 2 на свом месту). Пермутације које су бројане бар два пута су оне које остављају нека два елемента на свом месту. Ако су то елементи \(1\) и \(2\), то су пермутације \(1234\) и \(1243\), ако су то елементи \(1\) и \(3\) то су пермутације \(1234\) и \(1432\), ако су то елементи \(1\) и \(4\) то су пермутације \(1234\) и \(1324\), ако су то елементи \(2\) и \(3\) то су пермутације \(1234\) и \(4231\), ако су то елементи \(2\) и \(4\) то су пермутације \(1234\) и \(3214\) и ако су то елементи \(3\) и \(4\) то су пермутације \(1234\) и \(2134\). Парова елемената има \({4\choose 2} = 6\), а сваки од њих даје две пермутације. Њихов број можемо одузети од броја пермутација са фиксираним једним елементом, али је проблем да се међу њима неке пермутације понављају тако да смо онда одузели више него што је потребно. Пермутације које се понављају више пута су оне које фиксирају 3 елемента. Која год да су три елемента у питању то је пермутација \(1234\). Три елемента можемо одабрати на \({4\choose 3} = 4\) начина тако да треба додати 4 пермутације. Међутим, тада је пермутација која фиксира сва 4 елемента урачуната два пута, тако да њу на крају треба одузети. Дакле број деранжмана једнак је \(4! - 4\cdot 3! + 6\cdot 2! - 4\cdot 1! + 1 = 24 - 24 + 12 - 4 + 1 = 9\).
Овом логиком долазимо до тога да се број деранжмана може израчунати као
\[n! - {n\choose 1}(n-1)! + {n\choose 2}(n-2)! - \ldots + (-1)^{n-1}{n\choose n-1} 1! + (-1)^n\]
Зато је вероватноћа да се насумично одабере деранжман једнака количнику броја деранжмана и укупног броја пермутација. Пошто је \({n \choose k} = \frac{n!}{k!(n-k)!}\), добијамо
\[\frac{n! - \frac{n!}{1!(n-1)!}(n-1)! + \frac{n!}{2!(n-2)!}(n-2)! + \ldots + (-1)^{n-1}\frac{n!}{(n-1)!1!}1! + (-1)^n}{n!}\]
тј.
\(1 - \frac{1}{1!} + \frac{1}{2!} - \ldots + \frac{(-1)^{n-1}}{(n-1)!} + \frac{(-1)^n}{n!}\)