Informacje dla kandydatów

Układanka

Napisz program, który z poniższych siedmiu klocków składa kostkę 3x3x3:

klocki

Poniższa animacja przedstawia jedno z wielu rozwiązań:

przemko_12

Powyższe rozwiązanie znaleziono programem w SICStus Prologu z wykorzystaniem predykatu geost/3.

Bardzo trudne zadanie

Niech \(n \ge 1\) będzie liczbą całkowitą. Napisz program, który odpowiada na następujące pytanie:

Czy istnieje prostokąt, który można podzielić na \(n\) różnych kwadratów?



Dla \(n=1\) rozwiązanie jest trywialne gdyż każdy kwadrat spełnia warunek zadania.

Dla \(n = 2, 3, 4, 5, 6, 7, 8\) nie istnieje taki prostokąt. Dopiero dla \(n=9\) istnieje prostokąt np. taki jak poniższy:

kwadraty

Uwaga: całkiem zgrabny program rozwiązujący powyższe zadanie (32 linijki kodu) można napisać w języku programowania Prolog z wykorzystaniem technologii więzów. Program taki nie tylko odpowiada czy istnieje prostokąt ale podaje również jego wymiary i długości boków \(n\) kwadratów.

Łamigłówka arytmetyczna

Między liczbami wstawić operacje arytmetyczne +, -, *, / oraz nawiasy aby otrzymać zadaną wartość:
$$\begin{array}{rcl}
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 1 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 10 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 100 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 1000
\end{array}$$

Przykładowe rozwiązania:
$$\begin{array}{rcl}
1 + 2 + 3 + 4 + 5 - ( 6 + 7 ) + 8 - 9 & = & 1\\
1 + 2 + 3 + 4 + 5 * ( 6 - ( 7 + 8 ) + 9 ) & = & 10\\
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9 & = & 100\\
1 + 2 * ( ( 3 * ( 4 + 5 ) + 6 ) * ( 7 + 8 ) ) + 9 & = & 1000\\
\end{array}$$

Nie da się jednak w taki sposób z cyfr 1, 2, 3, 4, 5, 6, 7, 8, 9 uzyskać wartość 10000. Z tego powodu dopuścimy sklejanie sąsiadujących liczb (np. cyfry 1 2 można skleić w liczbę 12 a cyfry 1 2 3 w liczbę 123).

Dopuszczając sklejanie sąsiednich liczb znajdź rozwiązanie dla:
$$\begin{array}{rcl}
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 10000
\end{array}$$

Wskazówka: Napisz program, który tworzy w sposób systematyczny drzewa wyrażeń. W liściach tych drzew znajdują się zadane liczby (lub liczby będące sklejeniem sąsiednich liczb) a w wierzchołkach wewnętrznych znajdują się operacje +, -, * i /.

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ń.