Josephus problem

http://en.wikipedia.org/wiki/Josephus_problem

This problem is also described in detail in Chapter 1.3
http://en.wikipedia.org/wiki/Concrete_Mathematics

Keeping long story short:

If we have N =  2^m+l persons than the number of person who survives is 2 * l+ 1 (first person in line has number 1).
It can be proved using induction.
But I decided to create small C++ program to verify it and prove the formula using "programmer proof".

Header:

http://code.google.com/p/javahotel/source/browse/trunk/examples/flavius/runflav.h

extern int CountFlavByExclusion(int no);

extern int CountFlavByFormula(int no)

First method counts "Josephus" number using direct algorithm, the second is using formula.

Implementation (STL std::vector is used) :
http://code.google.com/p/javahotel/source/browse/trunk/examples/flavius/runflav.cpp

Than finally test it ! (boost test framework is used)

http://code.google.com/p/javahotel/source/browse/trunk/examples/flavius/projflav.cpp
Result : !

Running 3 test cases...

*** No errors detected

Press Enter to continue!