Matematyka dyskretna 1/Ćwiczenia 2: Rekurencja

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Rekurencja

Ćwiczenie 1

Znajdź postać zwartą ciągu zadanego równaniem rekurencyjnym:



Wskazówka
Rozwiązanie

Ćwiczenie 2

Znajdź postać zwartą ciągu zadanego równaniem rekurencyjnym:


Wskazówka
Rozwiązanie

Ćwiczenie 3

Ciąg liczb Lucasa jest definiowany następującą zależnością rekurencyjną:



Udowodnij, że gdzie jest -tą liczbą Fibonacci'ego. (Dla precyzji obliczeń przyjmij, że .)

Wskazówka
Rozwiązanie

Ćwiczenie 4

Adam i Marek zabawiali się w następującą grę. Adam wymyślał liczbę z zakresu od do . Zadaniem Marka było odgadnąć tę liczbę zadając Adamowi pytania, na które mógł odpowiadać jedynie TAK lub NIE. Znajdź najmniejszą liczbę pytań, po której Marek zawsze odnajdzie szukaną liczbę.

Wskazówka
Rozwiązanie

Ćwiczenie 5

Talia składa się z kart. Sortujemy te karty poprzez rekurencyjne rozkładanie ich na dwie równe kupki w następujący sposób:

  • Jeśli kupka składa się z jednej karty, to kupka ta jest posortowana.
  • Kupkę zawierającą kart, gdzie ,

dzielimy na dwie kupki zawierające po kart. Każdą z tych mniejszych kupek sortujemy oddzielnie (powtarzając rekurencyjnie całą procedurę sortowania). Następnie kolejno zbieramy karty ze szczytów obu kupek, zawsze zabierając większą z dwu szczytowych kart.

Oblicz ile ruchów potrzebnych było do posortowania wszystkich kart, jeżeli rozdzielenie kart na dwie kupki wymaga ruchów, a złożenie dwu posortowanych kupek, o kartach, w jedną całość wymaga ruchów.

Wskazówka
Rozwiązanie

Ćwiczenie 6

Rozwiąż równanie rekurencyjne:



przy czym jest postaci , gdzie jest liczbą naturalną.

Wskazówka
Rozwiązanie