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 2n na 2n (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.
kod # (pierwsza ćwiartka
ćwiartka 1
ćwiartka 2
2x2 z pierwszej ćwiartki)
kod 0 (trzecia ćwiartka
2x2 z pierwszej ćwiartki)
ćwiartka 3
ćwiartka 4
kod # (pierwsza ćwiartka 4x4)
(a)
kod # (cała kostka 8x8)
(b)
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 2n wierszy. Każdy wiersz składa się z 2n 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
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.
nie ma przejścia
najkrótsza droga
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
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