C++ on Mars: Incorporating C++ into Mars Rover Flight Software

Josephus problem

At school we started with a basic algorithm called the Josephus problem.

A short explanation from Wikipedia:

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

Here is my short C++ version. The benchmarking was just a test and should actually replaced with something else 😛

/*
 * File:   main.cpp
 * Author: Teusje
 *
 *
 */

#include <stdlib.h>
#include <iostream>
#include <list>
#include <time.h>
using namespace std;

int josephus1(int n, int k) {
    list<int> myList;
    list<int>::iterator it;
    list<int>::iterator itNext;

    // filling myList with values
    for (int i = 1; i <= n; i++) {
        myList.push_back(i);
    }

	// do untill n == 1, n-- every iteration
    for (it = myList.begin(); n-- != 1; it = itNext) {

		// times to skip
        for (int i = 1; i < k; i++) {
            ++it;
			// reset if we are at the end
            if (it == myList.end()) {
                it = myList.begin();
            }
        }
        itNext = it;
		// placing the iterator at the right position otherwise we have problems when we remove
        ++itNext;

		// removing the value
        myList.erase(it);

		// reset the iterator if we are at the end
        if ( itNext == myList.end()) {
            itNext = myList.begin();
        }
    }
    // return value
    return *it;
}

/*
 *
 */
int main(int argc, char** argv) {
    // Benchmark (very basic and undetailed)
    // http://www.cplusplus.com/reference/clibrary/ctime/difftime/
    time_t start,end;
    double dif;
    time (&start);
    //--Benchmark

    int result = josephus1(10, 2);

    //Benchmark
    time(&end);
    dif = difftime(end, start);
    //--Benchmark

    cout << endl << "Result: " << result << endl;
    printf("\nTime needed: %.21f \n", dif);

    return (EXIT_SUCCESS);
}

Got a better solution? (and yes there are better solutions ;)) Feel free to post it.

/*
* File:   main.cpp
* Author: Wouter
*
* Created on 10 februari 2010, 21:05
*/

#include <stdlib.h>
#include <iostream>
#include <list>
#include <time.h>
using namespace std;

int josephus1(int n, int k) {
list<int> lijst;
list<int>::iterator it;
list<int>::iterator volgende;

// lijst opvullen met waarden
for (int i = 1; i <= n; i++) {
lijst.push_back(i);
}

// doen tot n == 1 is, n telkens met 1 verminderen
for (it = lijst.begin(); n– != 1; it = volgende) {

// aantal keer doorschuiven
for (int i = 1; i < k; i++) {
++it;
// resetten als we op het einde zijn
if (it == lijst.end()) {
it = lijst.begin();
}
}
volgende = it;
// iterator al goedzetten, anders probleem bij verwijderen
++volgende;

// verwijderen
lijst.erase(it);

// resetten als we op het einde zijn
if ( volgende == lijst.end()) {
volgende = lijst.begin();
}
}
// waarde terug geven
return *it;
}

/*
*
*/
int main(int argc, char** argv) {
//Benchmark
// http://www.cplusplus.com/reference/clibrary/ctime/difftime/
time_t start,end;
double dif;
time (&start);
//–Benchmark

int result = josephus1(10, 2);

//Bencmark
time(&end);
dif = difftime(end, start);
//–Benchmark

cout << endl << “Resultaat: ” << result << endl;
printf(“\nTijd nodig: %.21f \n”, dif);

return (EXIT_SUCCESS);
}