Problem Józefa Flawiusza bądź permutacja Józefa Flawiusza

Witam wszystkich. Pierwszym postem związanym z tematyką naszego bloga, będzie dawno temu zapomniany projekt z programowania strukturalnego.

Postanowiłem go tu umieścić ponieważ w mojej opinii stanowi on ciekawe zagadnienie algorytmiczne jak i programistyczne.  Do rzeczy…

W okręgu umieszczonych jest n obiektów, następnie eliminowany jest co k-ty obiekt, aż pozostanie tylko jeden. Problem polega na wskazaniu tego obiektu, który pozostanie.

Nazwa nawiązuje do postaci historyka Józefa Flawiusza, który w trakcie wojny rzymskorzydowskiej został, wraz z grupą 40 żydowskich powstańców (czyli razem 41 osób), otoczony przez Rzymian w jaskini. Powstańcy od pojmania woleli samobójstwo, dlatego też zdecydowali się utworzyć krąg i zabijać co trzecią osobę, aż zostanie tylko jedna, która popełni samobójstwo. Flawiusz chcąc uniknąć śmierci wyliczył, w którym miejscu powinien stanąć. Ustawił się na miejscu 16., dzięki czemu pozostał, jako przedostatnia osoba, przy życiu. Następnie, wraz z osobą z numerem 31., oddał się w ręce Rzymian i przeżył.

Pisząc ten program postawiłem pewne wymagania -użytkownik programu może podać liczbę straceńców, skok(co który), oraz od którego egzekucja ma się zacząć. Wymusiło to potrzebę korzystania z dynamicznych struktur danych:

int *starcency=malloc(N*(sizeof (int)));

Skutkiem tego jest to, iż kompilator nie musi znać stałych przed kompilacją. Poprawia to szybkość algorytmu, ułatwia pracę nad kodem i jest zgodne z „duchem C” (mimo, że program został napisany z naciskiem na wydajność a nie na estetykę – to nie ASP).

Omawiając po kolei strukturę kodu możemy zauważyć funkcję:

void show_array(int tab[], int N)

{
    int i;
    for(i=0; i<N; i++)
        printf("%d,", tab[i]);
    return;
}

Jest ona odpowiedzialna za przedstawienie naszych straceńców w formie tablicy. Kolejnym blokiem na jaki natrafiamy jest funkcja sprawdzająca kiedy nasz algorytm należy zatrzymać.

int czy_sa_zywe(int tab[], int N)
{
    int i;
    for(i=0; i<N; i++)
{
    if(tab[i]!=0)
    return 1;
}
    return 0;
}

Ostatnim a za razem najbardziej interesującym blokiem jest główna funkcja main.

int main ()
{
    int start;
    int N;
    int M;
    printf("Podaj ilosc stracencow:\t ");
    scanf("%d",&N);
    printf("Podaj co ktorego:\t ");
    scanf("%d",&M);
    printf("Od ktorego:\t ");
    scanf("%d",&start);
    info();
    int i;
    int *starcency=malloc(N*(sizeof (int)));
    for(i=0;i<N;++i)
    starcency[i]=i+1;
    show_array(starcency,N);
    int licznik = start;
    int a = 0;
    while(czy_sa_zywe(starcency,N))
    {
        if(starcency[licznik]!=0)
    {
        if(licznik<N)
    {
        starcency[licznik]=0;
        printf("\n\nStracenie nr. %d Zabity nr:          %d\n\n",++a,licznik+1);
        show_array(starcency,N);
        licznik+=M;
    }
     else
    {
     licznik = licznik%N;
    }
}
     else{
     licznik++;
}
}
free(starcency);
return 0;
}

Następne linijki pokazują dynamikę tablic i zastosowanie wskaźników:

for(i=0;i<N;++i)
        starcency[i]=i+1; 

W tej pętli for widzimy, że i jest zwiększane o jeden. Jest to wymuszone tym, iż tablice są numerowane od liczby 0. Idąc dalej natrafiamy na pętlę while, zagnieżdżenie if oraz else.  Są one odpowiedzialne z warunkowość naszego programu.

A teraz trochę pogderam o tym co wszystkim zazwyczaj wisi… Mowa tu o optymalności kodu. W dobie dzisiejszego sprzętu mało kto widział napis bad_alloc. I nie mówię tu o takich psujach jak jak :3

W opisie zadania projektowego wskazano na wydajność algorytmu. Dostosowałem się do tej uwagi. Do programu zamieszczam również dodatkowy program pokazujący ilość przebiegów pętli w funkcji main. Początkowe wersje programu wykazywały ok. 600 obiegów a ostatnia (przy tych samych danych wejściowych) nieco ponad 100.

Podsumowując:

Program nie działa w momencie podania mu znaku innego niż liczba jako daną wejściową oraz w memencie podania liczby ujemnej. Kolejnym ograniczeniem jest ilość pamięci RAM. Przy liczbach dużych (rzędu 10⁷ skazańców) system zabija program.

Pracując nad tym projektem niewiele informacji znalazłem o algorytmice tego problemu. W związku z tym będę wdzięczny za wszelkie słowa krytyki. Mam nadzieję, że post ten wniósł coś ciekawego. Zachęcam do obserwowania „świeżego” blogu.

Kod całościowy:

//Radoslaw Sakowicz 
//www.uengineering.net

#include<stdio.h>
#include<stdlib.h>
#include<math.h>


void info()
{
    printf("\n\nRadoslaw Sakowicz\n");
    printf("Wariacja na temat problemu Jozefa Flawiusza.\n\n\n");
}

void show_array(int tab[], int N)
{
    int i;
    for(i=0; i<N; i++)
        printf("%d,", tab[i]);
    return;
}

int czy_sa_zywe(int tab[], int N)
{
    int i;
    for(i=0; i<N; i++)
    {
        if(tab[i]!=0)
            return 1; // zywe

    }
    return 0; //nie na zywych
}

int main ()
{
    unsigned long long int q = 0;
    int start;
    int N;
    int M;
    printf("Podaj ilosc stracencow:\t ");
    scanf("%d",&N);

    printf("Podaj co ktorego:\t ");
    scanf("%d",&M);

    printf("Od ktorego:\t ");
    scanf("%d",&start);
    info();
    int i;
    int *starcency=malloc(N*(sizeof (int)));
    for(i=0;i<N;++i)
        starcency[i]=i+1;
    show_array(starcency,N);

    int licznik = start;
    int a = 0;

    while(czy_sa_zywe(starcency,N))
    {
        q++;
        if(starcency[licznik]!=0)
        {
            if(licznik<N)
            {
                starcency[licznik]=0;
                printf("\n\nstracenie nr. %d zabity nr: %d\n\n",++a,licznik+1);
                show_array(starcency,N);
                licznik+=M;
            }
            else
            {
                licznik = licznik%N;
            }
        }
        else{
            licznik++;
        }
    }
    printf("\n\nIlosc obiegow petli: %d",q);
    free(*starcency);
    return 0;
}