123456789101112131415161718192021222324252627282930313233343536373839 |
- #include <QCoreApplication>
- int whoGoesFree(int n, int k);
- int main(int argc, char *argv[])
- {
- QCoreApplication a(argc, argv);
- whoGoesFree(7,2);
- return a.exec();
- }
- /* A group of n prisoners stand in a circle awaiting execution.
- * Starting from an arbitrary position(0), the executioner kills
- * every kth person until one person remains standing, who is then granted
- * freedom (see examples).
- * Create a function that takes 2 arguments — the number of people to
- * be executed n, and the step size k, and returns the original position
- * (index) of the person who survives.
- */
- int whoGoesFree(int n, int k) {
- // create an index of positions
- std::vector<int> indexP(n) ;
- std::iota (std::begin(indexP), std::end(indexP), 0);
- // position of last person killed; c is count to k;
- int lastkill = 0, c = 0, target = 0;
- // kill everybody
- while(n){
- // if killing, kill and advance target
- if(++c == k){
- lastkill = indexP[target];
- // this advances the target
- indexP.erase(indexP.begin() + target);
- c = 0;
- n--;
- }
- // advance the target
- else{// determine who might get killed next
- target = ++target % indexP.size();}
- }
- return lastkill;
- }
|