Blog do projektu Open Source JavaHotel

czwartek, 12 listopada 2009

Josephus problem

This problem is also described in detail in Chapter 1.3

Keeping long story short:
If we have N =  2m+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".

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) :

Than finally test it ! (boost test framework is used)
Result : !
Running 3 test cases...

*** No errors detected

Press Enter to continue!

Brak komentarzy:

Publikowanie komentarza