Informacje dla kandydatów

W oczekiwaniu na koniec świata

Chyba wszystkim znana jest łamigłówka Wieże Hanoi, o której można poczytać np. na Wikipedii.

„Legenda“ mówi, że kiedy mnisi w świątyni Brahmy rozwiążą tę łamigłówkę dla 64 krążków nastąpi koniec świata.

Napisz program, który znajduje rozwiązanie dla n krążków ale przy założeniu, że możemy korzystać nie z jednego ale z dwóch dodatkowych słupków.

Poniżej przedstawiono przykład dla n=5 krążków, w którym wykonywanych jest 13 ruchów:


hanoi

Czy Twój program wykonuje najmniejszą możliwą liczbę ruchów?

Pętla potęgą jest i basta

Poniższa pętla oblicza wartość y=xn, dla nieujemnej wartości całkowitej n:

y = 1.0; for(i = 0; i < n ; i++) y *= x;

N-ta potęga zostaje obliczona za pomocą n mnożeń.

Napisz obliczanie n-tej potęgi jak najmniejszą liczbą mnożeń.

Wskazówka: x32  można policzyć za pomocą pięciu mnożeń.

Czy ta pętla zawsze kończy swoje działanie?

Czy dla dowolnej całkowitej dodatniej wartości n poniższa pętla w języku C kończy pracę?

while(n % 2 != 0) n = (3 * n + 1) / 2;

Wskazówka: aby pokazać, że pętla zawsze kończy pracę, należy wskazać taką całkowitą wielkość, która przyjmuje tylko nieujemne wartości i maleje po każdym wykonaniu instrukcji wewnątrz pętli (liczby naturalne nie mogą tworzyć nieskończonego ciągu malejącego).

Zadanie zaczerpnięto z książki S. Alagić, M.A. Arbib. Projektowanie programów poprawnych i dobrze zbudowanych. WNT, Warszawa 1982.