Propozycje tematów projektowych – inne zadania

1. Napisz klasę ulonglong,

taką która daje możliwość operacji na liczbach naturalnych z zakresu od 0 do 2128-1 (liczby 128-
bitowe bez znaku), wykorzystaj do tego celu operacje na typie wbudowanym unsigned long int.
[2] Napisz:

a. konstruktory,

destruktor,

b. wszystkie

możliwe operacje arytmetyczne (+,+=,*,*=,%...itd),

c. funkcje

obliczającą silnie,

d. przeciążenie operatorów strumienia wejścia wyjścia

2. Program do nauki słówek np. języka angielskiego.

Program stanowiący prymitywna wersje SuperMemo, ma umożliwiać tworzenie bazy danych
słówek, ich naukę, odpytywanie i wyznaczanie powtórek.

3. Minimalna ścieżka

Mając macierz liczb int, napisz program, który wyszuka ścieżkę o minimalnej wartości. Ścieżka
można rozpocząć w dowolnym rzędzie pierwszej kolumny i prowadzić sekwencyjnie do
ostatniej kolumny. Z i kolumny można się przesuwać do i+1 kolumny tylko do komórki
sąsiedniej. Sposób przemieszczania się przedstawia poniższy rysunek.

Pierwszy i ostatni rząd macierzy są rzędami sąsiadującymi stanowiąc cylindryczną
reprezentacje macierzy.
Wartość ścieżki stanowi sumę wartości liczb w każdej komórki macierzy, którą odwiedzimy.
Np.

Dla dwóch macierzy 5x6 szare pola pokazują ścieżki o najmniej wartości.

3 4 1 2 8 6 3 4 1 2 8 6
6 1 8 2 7 4 6 1 8 2 7 4
5 9 3 9 9 5 5 9 3 9 9 5
8 4 1 3 2 6 8 4 1 3 2 6
3 7 2 8 6 4 3 7 2 1 2 3

Dane: Dane dla programu znajdują się w pliku. W pierwszym wierszu podane są liczby m -
liczba wierszy macierzy, i n - liczba kolumn macierzy. W kolejnych m wierszach podane
wartości int dla każdego wiersza macierzy.
Np.
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10
9 10

Wyniki: W pliku wynikowym w pierwszym wierszu powinno się znaleźć wartość minimalnej
ścieżki, w drugim wierszu powinno znaleźć się n – wartości numerów rzędów (odseparowanych
spacjami) opisujące minimalną ścieżkę.

Dla powyższych danych powinniśmy otrzymać:
16
1 2 3 4 4 5
11
1 2 1 5 4 5
19
1 1

4. Ogródek królewny (Kodowanie i dekodowanie)

Za górami za lasami żyła sobie królewna. Przy pałacu królewna miała ogródek, a w ogródku,

jak to w ogródku, rosły sobie na grządkach w równych rządkach rzodkiewki. Królewski ogrodnik
prowadził dokładny rejestr plantacji rzodkiewek. Plantacja ma kształt szachownicy o wymiarach 2

n

na

2

n

(n=1, 2, 3..., 9) - w każdym kwadraciku plantacji może rosnąć co najwyżej jedna rzodkiewka.

Ponieważ rzodkiewki rosną często grupami ogrodnik doszedł do wniosku, że warto "skompresować"
opis plantacji. Zrobił to tworząc następujący ciąg, w którym pojedyncze znaki mogą opisywać całe
kwadratowe poletka w ogródku:

• jeżeli w kwadracie nie rośnie ani jedna rzodkiewka, to kodujemy go jako 0,
• jeżeli na całym poletku rosną wszędzie rzodkiewki, to kodujemy go jako l,
• jeżeli na poletku są i rzodkiewki i puste miejsca, to kodujemy go jako #.

Aby zakodować całą plantację w pierwszej kolejności kodujemy całe pole, a następnie rekurencyjnie
kodujemy każdą z ćwiartek pola w kolejności pokazanej na rysunku la.

(b)

kod # (pierwsza ćwiartka
2x2 z pierwszej ćwiartki)

kod # (pierwsza ćwiartka 4x4)

kod # (cała kostka 8x8)

kod 0 (trzecia ćwiartka
2x2 z pierwszej ćwiartki)

ćwiartka 2

ćwiartka 4

ćwiartka 3

ćwiartka 1

(a)

Rysunek l.

W ten sposób plantacja pokazana na rysunku 1b (rozmiar 8x8, n=3) zostanie zakodowana ciągiem:
##000100#0111##1000#0011#01111#0#001100#11#00110.

Napisz program, który zakoduje obraz plantacji za ogrodnika. Program powinien czytać dane z pliku.
Dane zawierają opisy kilku plantacji. Opis każdej plantacji składa się z rozmiaru plantacji ‘n’ i 2

n

wierszy. Każdy wiersz składa się z 2

n

znaków opisujących kolejne rzędy plantacji. Znak l oznacza, że

na danej pozycji rośnie rzodkiewka, a znak 0 oznacza, że miejsce jest puste. Wynik Twój program
powinien zapisywać w pliku wynik kodowania. Dla każdej plantacji należy podać jej kodowanie w
oddzielnym wierszu. Np. dla danych (podobnie jak poprzednio w przykładzie dla plantacji 8x8):

3
00001000
01000011
00010111
00111111
00001111
00111111
00000000
00001100

2

1100
1110
1001
1111
W pliku wynikowym powinny się znaleźć dwa wiersze:
3 ##000100#0111##1000#0011#01111#0#001100#11#00110
2 #1#0010#1011#0111

Program powinien też pozwolić rozkodować zapis ogrodnika, który pozwoli królewnie poznać
rozmieszenie rzodkiewek na plantacji i obliczyć na tej podstawie, ile rzodkiewek rośnie na jej
plantacji.
I tak na przykład dla kodów:
5 1
4 #10#111000##1011011##0101#101011
2 #10#00101
Wynik powinien wyglądać następująco:
1024
60
9

5. Labirynt
Dana jest prostokątna plansza podzielona na kwadratowe pola. Część pól planszy została zamalowana
na czarno, a część pozostała biała. Po planszy będziemy poruszać się od jej górnego brzegu do
dolnego. Po planszy można poruszać się tylko po białych polach. Aby przesunąć się o jedno pole,
sąsiadujące pola muszą się stykać krawędziami.

najkrótsza droga

nie ma przejścia

Przykład a)

Przykład b)

Napisz program, który sprawdzi czy przy danym zamalowaniu pól planszy można przejść od górnego
brzegu do dolnego jedynie po białych polach. W przypadku gdy istnieje droga z góry na dół należy
podać najkrótszą drogę, czyli taką, której pokonanie wymagało przejścia najmniejszej ilości pól
białych.
Dane: Dane dla programu znajdują się w pliku. W pierwszym wierszu podane są liczby m -liczba
wierszy planszy i n -liczba kolumn planszy. W kolejnych m wierszach podany jest opis każdego pola
wiersza planszy. Jest to łańcuch długości n złożony ze znaków ‘B’ i ‘C’, gdzie ‘C’ oznacza pole
czarne, a ‘B’ pole białe. Dla plansz podanych na rysunkach opis wygląda następująco:
Przykład a)

9 9
BBCBBBBBB
BBCBBBBBB
BBBCBBCBB
BBCBBBCBB
BCCBBCBBB
CBBCBBCBB
BBBBCBCCB
BBBBBCCBC
BBBBBCBBC
Przykład b)

9 11

BBBBBBBCBBB
BBBCBBCCBBB
CBBCBCBBCCB
BCBBCBBBBBC
BBCBCBCBCBB
BBCBBBCCBBB
BBCBBCBBBCB
BBCCCBBCCBB
BBBBBBCBBBB

Wyniki: W pliku wynikowym w pierwszym wierszu powinno się znaleźć słowo tak lub nie, w
zależności od tego czy istnieje droga na planszy, czy nie. Jeżeli droga istnieje, to w następnym wierszu
powinna zostać wypisana najkrótsza z dróg (jeśli jest ich kilka) w następujący sposób. Jako pierwszy
podajemy numer pola w pierwszym wierszu (licząc od góry) planszy, od którego rozpoczynamy
przechodzenie. Następnie opisujemy drogę w dół planszy za pomocą liter L, P, D i G rozdzielonych
spacjami. Litery te oznaczają, że przechodzimy z pola, na którym aktualnie jesteśmy w (L) lewo, (P)
prawo, (D) dół lub (G) górę.
Np. dla przykładu a) i b) z rysunku wynik ma być następujący:
nie
tak 3 D D D P D D P P G G P P P P D D P D D D

6. Opracowanie interpretatora wyrażeń arytmetycznych (parser).
7. Kalkulator numeryczny na wzór aplikacji z akcesoriów systemu Windows z dodatkową

możliwością obliczenia wartości liczbowej na podstawie wpisywanego wyrażenia
arytmetycznego w postacie ciągu znaków.

8. Opracuj klasę doubledouble,

taką która daje możliwość operacji na liczbach o podwojonej precyzji w stosunku do double
wykorzystaj do tego celu operacje na typie wbudowanym double. Napisz:
o

konstruktory, destruktor,

o

wszystkie możliwe operacje arytmetyczne (+,+=,*,*=,%...itd),

o

funkcje matematyczne takie jak w bibliotece math.h,

o

przeciążenie operatorów strumienia wejścia wyjścia