Lista 9

Zadanie 1

Prześledzić wykonanie programu `fib2.c' dla kilku małych `n'. Dodać do programu instrukcję wypisującą informację o aktualnej wartości `n' (nie zmieniać obliczeń!), tak by wynik był identyczny jak wynik programu `fib1.c' z dodanym wypisywaniem informacji o wywołaniach.

Zadanie 2

Zagadnienie wież z Hanoi polega na tym że dane są trzy pręty. Początkowo na pręcie 1 znajduje się n krążków. Krążki mają rózne wielkości. Należy przełożyć krążki z preta 1 na pręt 2. Można się przy tym posługiwać pomocniczym prętem 3. Krążki należy prezkładać po jednym. Nie wolno położyć wiekszego krążka na mniejszy, ani kłaść krążków w inne miejsce. Program `hanoi.c' (rekursywny) wypisuje legalny ciąg ruchów. Zmodyfikować program `fib2.c' tak by uzyskać nierekursywne rozwiązanie zagadnienia wież z Hanoi.

Zadanie 3

Co wypiszą poniższe programy:

#include <stdio.h>
void fun(int * a, int * b)
{
        int tmp=*a;
        *a = *b;
        *b = tmp;
}
int main(void)
{
        int a=5, b=2;
        fun(&a, &b);
        printf("%d, %d\n", a, b);
        return 0;
}

#include <stdio.h>
void fun(int * * a, int * * b)
{
        int * tmp=*a;
        *a = *b;
        *b = tmp;
}
int main(void)
{
        int a=5, b=2;
	int * ap = &a, * bp = &b;
        fun(&ap, &bp);
        printf("%d, %d\n", a, b);
        return 0;
}

Zadanie 4

Co robią poniższe funkcje (zakładamy że komputer jest 32-bitowy):

unsigned int fun1(unsigned int arg)
{
        arg = (arg<<16)|(arg>>16);
        return ((0xff00ff&arg)<<8)|((arg>>8)&0xff00ff);
}

unsigned int fun2(unsigned int arg)
{
        arg = ((0xf0f0f0f&arg)<<4)|((arg>>4)&0xf0f0f0f);
        arg = ((0x33333333&arg)<<2)|((arg>>2)&0x33333333);
        return ((0x55555555&arg)<<1)|((arg>>1)&0x55555555);
}

Uwaga: Programy przykładowe są w podkatalogach katalogu

/home/s/prow/p-wyk4/wdi/wdi_pr/
Nazwa katalogu to data odpowiedniego wykładu zapisana bez
przerw w postaci rok, miesiąc, dzień.