i tried using dynamic programming to get a solution to Secretary Problem, seems to me its working with with expected result. i really didnt want to use Vector and things like that, because i wanted to learn about c-style arrays. things i want to know:
if there is any problem with the code
commenting
readability
use of c-style array
constants
splinting code into functions
performance
#include <iostream>
#include <cstdlib>
const unsigned int SEED = 42; // seed for srand()
const unsigned int SEQUENCE_LENGTH = 100; // participants count
const unsigned int CYCLES_COUNT = 1000000; // simulation cycles
void prime_sequence(unsigned int *data)
{
// fill data with values 0 to SEQUENCE_LENGTH-1 in
for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
{
data[i] = i;
}
}
void generate_sequence(unsigned int *data)
{
// generate random sequence using Fisher–Yates shuffle
for (unsigned int i = SEQUENCE_LENGTH; i > 0; i--)
{
unsigned int position = rand() % i;
if ((i - 1) != position)
{
unsigned int temp = data[i - 1];
data[i - 1] = data[position];
data[position] = temp;
}
}
}
void simulate(unsigned int *data, unsigned int *max_history, unsigned int *cum_history)
{
unsigned int rejected_max = 0;
for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
{
// reject choices up to i
if (data[i] > rejected_max)
{
// maximum of rejected choices
rejected_max = data[i];
}
for (unsigned int j = i + 1; j < SEQUENCE_LENGTH; j++)
{
// continue evaluvating choices and choosing first one that higher than rejected max
if (data[j] > rejected_max)
{
if (data[j] == SEQUENCE_LENGTH - 1)
{
// record only if chosen is best option
max_history[i] += 1;
}
// record chosen with its own weight
cum_history[i] += data[j];
break;
}
}
}
}
int main()
{
srand(SEED);
unsigned int data[SEQUENCE_LENGTH] = {0};
unsigned int max_history[SEQUENCE_LENGTH] = {0};
unsigned int cum_history[SEQUENCE_LENGTH] = {0};
prime_sequence(data);
for (unsigned int i = 0; i < CYCLES_COUNT; i++)
{
// simulation
generate_sequence(data);
simulate(data, max_history, cum_history);
}
unsigned int cum_sum = 0;
unsigned int max_sum = 0;
for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
{
// sum history enteries
cum_sum += cum_history[i];
max_sum += max_history[i];
}
for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
{
printf("at [%i] max: %.4f cum: %.4f\n", i, max_history[i] / (double)max_sum * 100, cum_history[i] / (double)cum_sum * 100);
}
std::cout << "max_sum: " << max_sum << " cum_sum: " << cum_sum << std::endl;
return 0;
}