Skip to content

Instantly share code, notes, and snippets.

@Desiment
Last active September 10, 2018 17:48
Show Gist options
  • Save Desiment/8134a107d8052a3f713eafd57c033da3 to your computer and use it in GitHub Desktop.
Save Desiment/8134a107d8052a3f713eafd57c033da3 to your computer and use it in GitHub Desktop.
Работает симуляцией (т.е. по факту мы просто запускаем охоту очень много раз и берем среднее) за приемлемое время (на моем компе).
#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;
}
@Desiment
Copy link
Author

В комментариях есть ошибки (сорян) :)
В коде (вроде как) нет.

@Desiment
Copy link
Author

Оптимизировал ввод, добавил рассмотрение краевых случаев

@Desiment
Copy link
Author

Desiment commented Jul 22, 2018

Тесты:
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