Wieże Hanoi :: 4programmers.net

1

Muszę napisać program "obliczający" wieże Hanoi iteracyjnie. Tak, program na zaliczenie. Algorytm napisałem na podstawie wikipedii:

przenieś najmniejszy krążek na kolejny (*) słupek.

wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego

powtarzaj punkty 1 i 2, aż do odpowiedniego ułożenia wszystkich krążków.

(*) Kolejny słupek wyznaczamy w zależności od liczby krążków. Jeśli liczba krążków jest parzysta, kolejnym słupkiem jest ten po prawej stronie (gdy dojdziemy do słupka C w następnym ruchu używamy słupka A). Natomiast jeśli liczba krążków jest nieparzysta, kolejnym słupkiem jest ten po lewej stronie (gdy dojdziemy do słupka A w następnym ruchu używamy słupka C)

Ok, super, wszystko działa. Dla 3 krążków i 3 drążków, program wykonuje się w 7 ruchach, czyli optymalnie. Problem pojawia się, gdy jest tego więcej.

Przy 4 drążkach i 4 krążkach, program nie wykonuje się nawet pomimo 150 000 ruchów.
Przy 3 drążkach i 4 krążkach, przy 5000 ruchach jeszcze się nie wykona, przy 10 000 już tak.

Co jest grane? Można to jakoś zoptymalizować?

Program jest wykonany na listach w taki sposób:

//- elementy listy są drążkami

każdy element posiada tablice krążków
tablica [0, 0, 0, 0] (dla 4 krążków) oznacza brak krążków na drążku
tablica [1, 2, 0, 0] oznacza że na drążku są krążki 1 i 2 (1 jest na krążku 2gim)//

Wkleję tylko funkcję odpowiedzialną na przenoszenie krążków:

void hanoi(rod **head, rod **tail)
{ 
	rod *temp, *temp2;
	int flag = 0, div = 0;
	
	for(int i = 0; i < 5000; i++)
	{
		temp = *head;
		flag = 0;

		if(div % 2 == 0) // move smallest disk to the right if odd, or left if even
		{
			while(temp != NULL)
			{
				if(flag == 1)
				{
					push(1, &temp->disks);
					break;
				}
				if(temp->disks[0] == 1 && flag == 0)
				{
					pop(&temp->disks);
					flag = 1;
				}
				if(n % 2 == 0)
				{
					if(temp->next == NULL && flag == 1)
					{
						temp = *head;
					}
					else
					{
						temp = temp->next;
					}
				}
				else
				{
					if(temp->prev == NULL)
					{
						temp = *tail;
					}
					else
					{
						temp = temp->prev;
					}
				}
			}
		}
		else // make first possible move
		{
			while(temp != NULL && flag == 0)
			{
				temp2 = *head;
				
				while(temp2 != NULL && flag == 0)
				{
					if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp2->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
					{
						int t = temp->disks[0];
						pop(&temp->disks);
						push(t, &temp2->disks);
						flag = 1;
					}
					
					temp2 = temp2->next;
				}
				
				temp = temp->next;
			}
		}
		
		div++;
	}
}

Wszystkie sugestie będą mile widziane :D Siedzę nad tym cały weekend i nie wiem co z tym można zrobić.

0

Jednak dla 3 drążków działa wszystko normalnie, błędy były wynikiem dodatkowych przełożeń po zakończeniu algorytmu. Pozostaje jednak kwestia 4 drążków, tutaj nic się nie zmieniło.

0

Ciekawi mnie co byś zrobił jakby drążków było n=1000 albo n=1000000. Też byś to tak napisał?

0

Tak, wiem, na razie chcę chociaż żeby to zaczęło działać, refaktoryzacja potem.

Czyli co, algorytm jest do du*y? Działa tylko dla 3 krążków, ale nie mogę nigdzie znaleźć algorytmów dla większej ilości, sam też na nic konstruktywnego nie wpadłem.

Znasz może jakiś sposób?

0

Wykonujesz przeniesienie krążków 1..(n-1) ze słupka 1 na słupek 2 używając słupka 3. Przenosisz krążek n na słupek 3. Przenosisz krążki 1..(n-1) ze słupka 2 na słupek 3 używając słupka 2. Masz algorytm rekurencyjny. Przez indukcję możesz dowieść jego poprawności.

0

Algorytm rekurencyjny to ja znam, szczególnie dla 3 drążków. A jaki jest algorytm iteracyjny dla n > 3 drążków?

0

Dla n drążków to dzielisz problem na n-2 problemy i rozwiązujesz je dzieląc sobie problem na problemy z 3 drążkami.

0

Dzięki :) Teraz wszystko dobrze działa, chociaż z optymalizacją i tak kiepsko bo przy 3 drążkach i 24 krążkach już nie oblicza wyniku tylko wywala program :P

0

Zoptymalizowałem jak się da, teraz dla 23 krążków jest 1,5s, dla 26 krążków 10s., dla 27 krążków 20s., dla 30 krążkó 5 minut czekałem itp, czyli już nie wywala.

Mam dwa pytania:

czy lepiej funkcje operujące na tablicach, ktore są wywolywane przy kazdym przelozeniu krazka (unshift, pop), umiescic w programie jako osobne funkcje (lepsza architektura), czy moze kod z tych funkcji bezposrednio w algorytmie?
zobaczcie whila przy komentarzu "// move smallest disk to the right if odd, or left if even". Idę tam po liscie w lewo albo w prawo zaleznie od parzystosci krążków, czyli troche warunkow sie wykonuje i pewnie wszystko spowalnia. To moze tak zostac, czy lepiej napisac dwa cale oddzielne algorytmy, dla parzystej liczby krazkow i nieparzystej? (kiepsko troche z DRY).

Kod wyglada obecnie tak:

void hanoi(rod **head, rod **tail)
{
	// Zaczynamy liczyc czas
	time_start();

	rod *temp, *temp2, *head_t = *head;
	int flag = 0, div = 0;

	for(int i = 0; i < rods - 2; i++)
	{
		while((*tail)->disks[n - 1] != n)
		{
			temp = *head, flag = 0;

			if(div % 2 == 0) // move smallest disk to the right if odd, or left if even
			{
				while(temp != (*tail)->next)
				{
					if(flag == 1)
					{
						unshift(1, &temp->disks);
						break;
					}
					if(temp->disks[0] == 1)
					{
						pop(&temp->disks);
						flag = 1;
					}

					if(n % 2 == 0)
					{
						temp = (temp->next == (*tail)->next) ? *head : temp->next;
					}
					else
					{
						temp = (temp->prev == (*head)->prev) ? *tail : temp->prev;
					}
				}
			}
			else // make first possible move
			{
				while(temp != (*tail)->next && flag == 0)
				{
					temp2 = *head;				
					while(temp2 != (*tail)->next)
					{
						if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
						{
							int t = temp->disks[0];
							pop(&temp->disks);
							unshift(t, &temp2->disks);
							flag = 1;
							break;
						}
				
						temp2 = temp2->next;
					}
			
					temp = temp->next;
				}
			}

			div++, moves++;
		}

		// divide and conquer
		if(i < n - 3)
		{
			if((*head)->num <= i + 1)
				*head = (*head)->next;
			if((*tail)->num <= i + 3)
				*tail = (*tail)->next;
		}
	}
	
	*head = head_t;

	// Algorytm zakonczony
	time_stop();
}

/**
 * Powieksza tablice o jeden element - dodaje go na poczatek tablicy, a 
 * wszystkie poprzednie elementy przesuwa o 1 indeks w prawo
 *
 * @param el Element do wstawienia na poczatek tablicy
 * @param **arr
 */
void unshift(int el, int **arr)
{
	for(int i = (int)n - 1; i > 0; i--)
	{
		(*arr)[i] = (*arr)[i - 1];
	}
    (*arr)[0] = el;
}

/**
 * Usuwa pierwszy element z tablicy i przesywa jej pozostale elementy
 * o jeden indeks w lewo
 *
 * @param **arr
 */
void pop(int **arr)
{
	for(int i = 0; i < (int)n - 1; i++)
	{
		(*arr)[i] = (*arr)[i + 1];
	}	
	(*arr)[n - 1] = 0;
}

0

@winterfresh - tak, wiem, ale jak inaczej choćby wyszukać dwa możliwe przełożenia na listach? Bez dwóch whili i warunku się nie obędzie. Chyba że usunę wcięcia tam gdzie przekraczają 3 tabulatory :)

1

Głowę sobie usuń a nie wcięcia. Podziel kod na normalne funkcje które mają < 20 linijek i < 2 poziomy zagłębienia.

0

Taki sposób byłby świetny, ale przy 10 milionach przełożeń, tyle odwołań do funkcji nie spowolni działania?

0

Optymalizowanie zostaw na koniec. Najpierw kod musi byc czytelny i działać. Potem można puścić profiler i zobaczyć gdzie faktycznie warto coś optymalizować ;]

0

void hanoi(rod **head, rod **tail)
{
    // Zaczynamy liczyc czas
    time_start();
	
    rod *temp, *temp2;
	rod *head_temp = *head; // zeby przelozyc *head na pierwszy element listy po wykonaniu algorytmu
	
    for(int i = 0, divider = 0; i < rods - 2; i++)
    {
        while((*tail)->disks[n - 1] != n)
        {
            temp = *head;

            if(divider % 2 == 0)
			{
				move_smallest(&(*head), &(*tail), temp); // przeloz najmniejwszy krazek w prawo lub w lewo
			}
			else
			{
				move_rest(&*(head), &(*tail), temp); // wykonaj jedyny mozliwy ruch nie ruszajac najmniejszego krazka
			}
			
            divider++, moves++;
        }
		
        // dziel i rządź jeśli rods > 3
        if(i < rods - 3)
        {
            if((*head)->num <= i + 1) *head = (*head)->next;
            if((*tail)->num <= i + 3) *tail = (*tail)->next;
        }
    }
    
    *head = head_temp;
	
    // Algorytm zakonczony
    time_stop();
}

void move_smallest(rod **head, rod **tail, rod *temp, int flag /* = 0 */)
{
	while(temp != (*tail)->next)
    {
		if(flag == 1)
		{
			unshift(1, &temp->disks);
			break;
		}
		if(temp->disks[0] == 1)
		{
			pop(&temp->disks);
			flag = 1;
		}
 
		if(n % 2 == 0)
		{
			temp = (temp->next == (*tail)->next) ? *head : temp->next;
		}
		else
		{
			temp = (temp->prev == (*head)->prev) ? *tail : temp->prev;
		}
    }
}

void move_rest(rod **head, rod **tail, rod *temp, int flag /* = 0 */)
{
	while(temp != (*tail)->next && flag == 0)
    {
		rod *temp2 = *head;
        while(temp2 != (*tail)->next)
        {
			if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
            {
				int t = temp->disks[0];
                pop(&temp->disks);
                unshift(t, &temp2->disks);
                flag = 1;
                break;
            }
                  
            temp2 = temp2->next;
        }
                        
        temp = temp->next;
    }
}

/**
 * Powieksza tablice o jeden element - dodaje go na poczatek tablicy, a 
 * wszystkie poprzednie elementy przesuwa o 1 indeks w prawo
 *
 * @param el Element do wstawienia na poczatek tablicy
 * @param **arr
 */
void unshift(int el, int **arr)
{
    for(int i = (int)n - 1; i > 0; i--)
    {
        (*arr)[i] = (*arr)[i - 1];
    }
    (*arr)[0] = el;
}
 
/**
 * Usuwa pierwszy element z tablicy i przesywa jej pozostale elementy
 * o jeden indeks w lewo
 *
 * @param **arr
 */
void pop(int **arr)
{
    for(int i = 0; i < (int)n - 1; i++)
    {
        (*arr)[i] = (*arr)[i + 1];
    }       
    (*arr)[n - 1] = 0;
}

Uff...dzięki za rady, działa i jakoś już wygląda. Może jakieś sugestie właśnie odnośnie samej optymalizacji? Bo w sumie chyba o tym jest temat :P

0

Moim zdaniem wygląda jak kupa. Zmienne temp, temp2, cuda jak *(arr)[], wielokrotnie zagnieżdżone pętle, metody z serii "doStuff". Jeśli nie umiesz nazwać metody prostą nazwą która jednoznacznie i zwięźle opisuje co ta metoda robi, to znaczy że metoda wymaga podzielenia.
Skompiluj to przez
g++ -ansi -pedantic -Wall -ggdb -pg
uruchom dla jakiegoś większego przykładu (wygeneruje się plik dla profilera) a potem uruchom gprof w tym katalogu i zobacz sobie szczególnie flat profile i call graph.
gprof i g++ sa dostępne i na linuxa i na windowsa (cygwin)

0

A jak teraz to wygląda? Funkcji za dużo zrobić nie mogę, bo robię ten program w jednym pliku, jak będzie za dużo funkcji to paradoksalnie stanie się nieczytelny. Temp i temp2 też raczej być muszą żeby jakoś na tej liście operować. A o co Ci chodzi z (*arr)[] to ja nie wiem, arr[] nie działa w przypadku tych funkcji, więc innego sposobu nie widzę/nie znam, jeśli Ty znasz to napisz, może jeszcze się coś uda poprawić.

/**
 * Algorytm przekladajacy krazki wg. nastepujacego sposobu:
 *
 *   1. Jesli ilosc krazkow jest parzysta, przesuj najmniejszy element w prawo,
 *      jestli nieparzysta przesuj w lewo
 *   2. Wykonaj pierwszy mozliwy ruch bez wykorzystywania najmniejszego krazka
 *   3. Powtarzaj punkty 1 i 2 az do uzyskania poprawnego wyniku
 *
 * Więcej drążków to już kwestia powtarzania algorytmu rods - 2 razy (rods - liczba drążków),
 * w tym celu *head i *tail przesuwane są co 1 pole w prawo przy każdym powtórzeniu.
 * 
 * @param **head
 * @param **tail
 */
void hanoi(rod **head, rod **tail)
{
    for(int i = 0, divider = 0; i < pegs - 2; i++)
    {
        while((*tail)->disks[n - 1] != n)
        {
            if(divider % 2 == 0)
			{
				// przeloz najmniejwszy krazek w prawo lub w lewo
				move_smallest(&(*head), &(*tail));
			}
			else
			{
				// wykonaj jedyny mozliwy ruch nie ruszajac najmniejszego krazka
				move_bigger(&(*head), &(*tail));
			}
			
            divider++, moves++;
        }
		
        // przesun w praco glowe i ogon jeśli rods > 3
        if(i < pegs - 3)
        {
            if((*head)->num <= i + 1) *head = (*head)->next;
            if((*tail)->num <= i + 3) *tail = (*tail)->next;
        }
    }
}

/**
 * Przenies najmniejszy krazek w prawo lub w lewo, w zaleznosci
 * od parzystosci krazkow
 *
 * @param **head
 * @param **tail
 */
void move_smallest(rod **head, rod **tail)
{
    rod *temp = *head;

    int flag = 0;
    while(temp != (*tail)->next)
    {
        if(temp->disks[0] == 1)
        {
            pop(&temp->disks); // zdejmij najmniejszy krazek
        }
        else if(flag == 0)
        {
            unshift(1, &temp->disks); // wrzuc najmniejszy krazek
            flag = 1;
        }

		// idziemy na koniec, albo na poczatek listy
        if(n % 2 == 0) 
            temp = (temp->next == (*tail)->next) ? *head : temp->next;
        else
            temp = (temp->prev == (*head)->prev) ? *tail : temp->prev;
    }
}

/**
 * Wykonaj jedyny mozliwy ruch za pomoca krazkow wiekszych od najmniejszego
 *
 * @param **head
 * @param **tail
 */
void move_bigger(rod **head, rod **tail)
{
    rod *temp = *head, *temp2 = *head;

    int flag = 0;
    while(temp != (*tail)->next && flag == 0) // tail->num = pegs - 2
    {
        temp2 = *head;
        while(temp2 != (*tail)->next)
        {
            if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
            {
                int t = temp->disks[0];
                pop(&temp->disks);
                unshift(t, &temp2->disks);
                flag = 1;
                break;
            }
            
            temp2 = temp2->next;
        }
        
        temp = temp->next;
    }
}

/**
 * Powieksza tablice o jeden element - dodaje go na poczatek tablicy, a 
 * wszystkie poprzednie elementy przesuwa o 1 indeks w prawo
 *
 * @param el Element do wstawienia na poczatek tablicy
 * @param **arr
 */
void unshift(int el, int **arr)
{
    for(int i = (int)n - 1; i > 0; i--)
    {
        (*arr)[i] = (*arr)[i - 1];
    }
    (*arr)[0] = el;
}
 
/**
 * Usuwa pierwszy element z tablicy i przesywa jej pozostale elementy
 * o jeden indeks w lewo
 *
 * @param **arr
 */
void pop(int **arr)
{
    for(int i = 0; i < (int)n - 1; i++)
    {
        (*arr)[i] = (*arr)[i + 1];
    }       
    (*arr)[n - 1] = 0;
}

0

Ech, kod powinien wyglądać tak czytelnie jak ten opis:

Jesli ilosc krazkow jest parzysta, przesuj najmniejszy element w prawo,
 jestli nieparzysta przesuj w lewo
Wykonaj pierwszy mozliwy ruch bez wykorzystywania najmniejszego krazka

Powtarzaj punkty 1 i 2 az do uzyskania poprawnego wyniku

czyli:

void hanoi(krazki){
  while(!finished(krazki)){
    singleSolveStep(krazki);
  }
}

void singleSolveStep(krazki){
  if(parzyste(krazki)){
    moveSmallestRight();
  }else{
    moveSmallestLeft();    
  }
  makeFirstPosibbleMove();
}

i tak dalej. KAŻDE miejsce w twoim kodzie które opatrzyłeś komentarzem powinno być osobną funkcją. W dobrym kodzie komentarze są w 99% przypadków zbędne, bo kod "sam sie komentuje". Widzisz, gdyby twoja glówna funkcja wyglądała tak jak to co napisałem wyżej to cały ten komentarz z opisem byłby zbędny bo od razy byłoby widać co się w kodzie dzieje. Chodzi o to żeby kod dzielił się na "poziomy abstakcji". Kiedy patrzę na funkcję rozwiązująca problem hanoi interesuje mnie jak działa algorytm i absolutnie nie chce tam widzieć operacji na jakichś tablicach wskaźników, bo w problemie hanoi wcale takich rzeczy nie ma.
Te operacje są oczywiście potrzebne, ale na dużo niższym poziomie abstrakcji. Jak wejdę do funkcji służącej do przesunięcia krążka X z dzidy Y na dzidę Z to tam może mnie interesować jak to przeniesienie wygląda, ale znów wolałbym tam zobaczyć:

void moveDisc(which, from, to){
  popDisc(which,from);
  putDisc(which,to);
}

a dopiero w funkcji popDisc() mógłbym zobaczyć jak to faktycznie jest zaimplementowane i że wyciągam tam coś z jakiejś tablicy.

Zapewniam ci że taki podzial na funkcje wcale nie sprawi że kod będzie nieczytelny. Wręcz przeciwnie.

Po co jeszcze się tak robi? Po to żeby szybko wyszukiwac błędy w kodzie. W twoim kodzie jeśli okaże się że coś nie działa to nie ma szans znaleźć błędu bez ślęczenia nad debugerem i rozkminiania nad tym jakie wartości powinno przyjmować temp w jakimś miejscu. W moim kodzie od razu widzisz jak coś jest nie tak, bo analizujesz konkretne fragmenty algorytmu. Jeśli zapomniałeś zdjętego dysku położyć na nowej dzidzie to od razu to będzie widać. Jak wepchniesz to wszystko w jedną funkcję i jeszcze upchniesz tam wszytskie niskopoziomowe operacje na wskaźnikach to w życiu tego błędu nie znajdziesz.

Wieże Hanoi

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami