15.12.2006

Informatyka w I-szej A
Lista nr 8

Zadania obowiązkowe 

1.	Jeśli tego do tej pory nie zrobiłeś, prześlij swój adres emailowy prowadzącemu (na adres lorysster@gmail.com).

2.	Zmodyfikujmy nieco podaną na ostatniej lekcji funkcję rekurencyjną obliczającą n-tą liczbę Fibonacciego.
long long fib(int x)
{ if (x<=1) { cout<<”a”; return 1; }
  return (fib(x-1)+fib(x-2));
}
Ile liter „a” zostanie wypisanych, jeśli funkcję fib wywołamy z parametrem n? Spróbuj odpowiedzieć na to pytanie bez uruchamiania tej funkcji na komputerze. Odpowiedź uzasadnij.

3.	Napisz rekurencyjny program obliczający liczbę kombinacji k elementowych zbioru n elementowego. Specyfikacja we/wy: Twój program ma wczytać ze standardowego wejścia liczby naturalne n ,k (możesz przyjąć, że 0≤k≤n≤50) a wynik ma wypisać na wyjściu standardowym.

4.	Przypomnij sobie (lub naucz się, jeśli do tej pory nie zetknąłeś się z tym tematem) informacje o trójkącie Pascala. W szczególności:
a.	Jak się go buduje.
b.	Ile wynosi suma elementów w i-tym wierszu. Dlaczego tyle?

5.	Napisz program sortujący ciągi liczbowe metodą sortowania przez scalanie. Funkcja sortująca powinna być rekurencyjna.

Termin nadsyłania rozwiązań: 19.12.06; godz. 23.59. (Uwaga: Jeśli tym razem nawalicie – wracamy do terminu poniedziałkowego)

Uwagi i wskazówki.

Ad. 1. Za to zadanie skala punktów wynosi -10..0. Zgadnij, w jakim przypadku otrzymasz -10.
Ad. 2. Rozwiązanie umieść w pliku i prześlij do prof. Matli  i do mnie.
Ad. 3. Dla przypomnienia: liczba ta wyraża się wzorem n!/((n-k)!k!). Rekurencyjnie można ją wyrazić w następujący sposób:

n
k

n-1
k

n-1
k-1

+

=

1			jeśli k=0 lub n=k

w przeciwnym przypadku

Ad. 4. Przyślij tylko odpowiedź na punkt b).
Ad. 5. To zadanie potraktuj priorytetowo.

Zadania nadobowiązkowe 
1.	Janek ma 4 jednakowe klocki i 2 różne pudełka (białe i niebieskie). Zastanawia się, na ile sposobów może swoje klocki rozmieścić w pudełkach. To jest bajecznie proste. Istnieje 5 sposobów:
•	w białym pudełku mogą być 4 klocki, wówczas drugie będzie puste;
•	w białym pudełku mogą być 3 klocki, a w niebieskim – 1 klocek;
•	w białym  i niebieskim pudełku mogą być po 2 klocki;
•	w białym pudełku może być 1 klocek, a w niebieskim – 3 klocki;
•	białe pudełko może być puste, ponieważ wszystkie klocki znajdą się w niebieskim pudełku.

Janek jednak przeczuwa, że pod choinkę dostanie jeszcze kilka nowych (lecz identycznych ze starymi) klocków i kilka pudełek w rożnych kolorach. Trochę go martwi, że nie będzie w stanie wyliczyć liczby sposobów, na które będzie mógł rozmieścić klocki w pudełkach. Pomóż mu i napisz program, który to wyliczy za niego. 
Specyfikacja we/wy:
•	Dane (plik „klocki.in”):
o	W pierwszym i jedynym wierszu znajdują się dwie liczby naturalne n i k, oznaczające odpowiednio liczbę klocków i pudełek.
•	Wynik (wyjście standardowe, tj, ekran)
o	W jedynym wierszu ma znaleźć się liczba równa liczbie sposobów, na które można rozmieścić n klocków w k pudełkach.

Wskazówka. Jeśli się dobrze zastanowisz, to nie będziesz musiał pisać skomplikowanego programu