Last active
September 10, 2018 17:48
-
-
Save Desiment/8134a107d8052a3f713eafd57c033da3 to your computer and use it in GitHub Desktop.
Работает симуляцией (т.е. по факту мы просто запускаем охоту очень много раз и берем среднее) за приемлемое время (на моем компе).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <cmath> | |
#include <random> | |
#define denom 0.01 //Точность | |
#define loops 10000 //Количество циклов в симуляции | |
#define iter 5 //Количество симуляций | |
#define eps 10000 //Констнта event_p | |
//Время работы O(C*N); C = iter*loops*c; | |
//Меняя iter и loops таким образом, чтобы iter*loops неизменялось | |
//Можем повысить (или понизить) точность вычислений | |
//Согласно стандарту C++, принцип работы std::random_device отдаётся на откуп разработчикам компилятора | |
//Таким образом, в зависимости от компилятора, платформы может серьезно зависеть время работы и точность вычислений | |
//При тестировании использовался MVSC (cl.exe) версии 14.13.26128.0 в x64 Windows 10 | |
//Код работает только с C++11 и выше | |
using namespace std; | |
typedef unsigned long long ullint; | |
typedef unsigned short int usint; | |
//Глобальные структуры для randomer() | |
mt19937 engine; | |
random_device device; | |
ullint randomer() //Собственный рандом: генерация псевдослучайных чисел методом Вихря Мерсенна | |
{ | |
engine.seed(device()); | |
std::uniform_int_distribution<unsigned> distribution(0, eps); | |
return distribution(engine); | |
}; | |
bool event_p(double probability) //С вероятностью probability вернет true | |
{ | |
ullint border = probability * eps; | |
return (randomer()) < border; | |
} | |
double simulation(usint N, usint K, const vector<double> probs) //Симуляция охоты loops раз. Возвращает ~вероятность успешной охоты | |
{ | |
ullint good_hunts = 0; //Количество удавшихся охот | |
for (ullint hunts = 0; hunts < loops; hunts++) | |
{ | |
usint kills = 0; //Количество убийств за одну охоту | |
for (usint i = 0; i < N; i++) | |
{ | |
if (event_p(probs[i])) | |
kills++; | |
} | |
if (kills >= K) | |
good_hunts++; | |
}; | |
return (double)good_hunts / loops; //Чтобы посчитать вероятность успешной охоты делим количество хороших случаев на все случаи. | |
} | |
int main() { | |
usint N; | |
short int K; | |
cin >> N >> K; | |
//TEST | |
/* | |
ullint tests = 0; | |
for (ullint i = 0; i < loops; i++) | |
{ | |
if (event_p(0.5)) | |
{ | |
tests++; | |
}; | |
}; | |
cout << tests << endl; | |
*/ | |
vector<double> probs; | |
for (usint i = 0; i < N; i++) | |
{ | |
double input; | |
cin >> input; | |
if (input == 1) //Животное гарантировано умрет, следовательно убить надо на одного меньше | |
{ | |
K--; | |
} | |
else if (input != 0) //Если животное не подстрелить (p[i] == 0), то можно и не париться и игнорировать его | |
{ | |
probs.push_back(input); | |
}; | |
}; | |
//Обновляем N, с учетом отброшенных животных | |
N = probs.size(); | |
//Рассматриваем крайние случаи | |
if (K <= 0) | |
{ | |
cout << "Prob: " << 1 << endl; | |
system("pause"); | |
return 0; | |
}; | |
if (K > N) | |
{ | |
cout << "Prob: " << 0 << endl; | |
system("pause"); | |
return 0; | |
}; | |
double ans = 0; //Среднее арифмитеческое значений возвращаемых simulation; | |
for (usint i = 0; i < iter; i++) | |
{ | |
ans += simulation(N, K, probs); | |
}; | |
ans = ans / iter; | |
cout << "Prob: " << (ans - remainder(ans, denom))/*Округляем*/ << endl; | |
system("pause"); | |
return 0; | |
} |
Оптимизировал ввод, добавил рассмотрение краевых случаев
Тесты:
1:
N = 3. K = 2 P: [0.5; 0.5; 0.5] Output = 0.5 (Ans = 0.5)
2:
N = 3. K = 2 P: [1; 0.5; 0.5] Output = 0.5 (Ans = 0.5)
3:
N = 4. K = 2 P: [0.1; 0.3; 0.4; 0.7] Output = 0.49 (Ans = 0.4851)
4:
N = 9. K = 8 P: [0.1; 0.2; 0.3; 0.4; 0.5; 0.6; 0.7; 0.8; 0.9] Output = 0.01 (Ans = 0.007363)
5:
N = 20. K = 20 P: [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0.5] Output = 0.5 (Ans = 0.5)
6:
N = 5. K = 4 P: [1; 1; 0.5; 0.5; 0.5] Output = 0.5 (Ans = 0.5)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
В комментариях есть ошибки (сорян) :)
В коде (вроде как) нет.