Problem 1

Napisz program znajdujący maksymalny niemalejący, spójny podciąg w ciągu liczb. Przetestuj jego działanie dla tablicy [6, 7, 1, 3, 4] .

Specyfikacja problemu:

Dane:

  • liczby – tablica liczb naturalnych

  • rozmiarTablicy – liczba naturalna

Wynik:

Na standardowym wyjściu program wyświetla maksymalny niemalejący spójny podciąg.

Rc7hUeTN7fO7k
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Polecenie 1

Porównaj swoje rozwiązanie z przedstawionym w filmie.

RL9cgcjkmLuUW1
Film nawiązujący do treści materiału

Tablica jednowymiarowa – przypomnienie

Tablica jednowymiarowa jest uporządkowanym zbiorem elementów tego samego typu. Są one numerowane (indeksowane). Pierwszy element ma numer 0.

Tablica jednowymiarowa w języku C++

Oto deklaracja – i zarazem definicja – tablicy jednowymiarowej w języku C++:

Linia 1. int przykladowaTablica otwórz nawias kwadratowy 10 zamknij nawias kwadratowy średnik.

Definiowanie tablicy rozpoczynamy od wskazania typu danych, które będą w niej przechowywane – w tym przypadku są to liczby całkowite (int).

Następnie nadajemy nazwę tablicy – niech będzie to przykladowaTablica. Do nazwy tej będziemy się odwoływać, aby odczytać zawartość tablicy, wpisać konkretną liczbę w określonym miejscu albo wykonać operację na wybranym elemencie.

Za nazwą, w nawiasach kwadratowych, określamy rozmiar tablicy. Jest to liczba elementów, które da się zapisać w tablicy.

W języku C++ istnieją dwa rodzaje tablic. Jednym z nich są tablice statyczne, a drugim – tablice dynamiczne. Rozmiar tablicy statycznej jest ustalany podczas jej tworzenia i nie można go zmienić. W przypadku tablic dynamicznych jest inaczej – ich rozmiar zmienia się w zależności od liczby przechowywanych elementów. W tym e‑materiale będziemy zajmować się tylko tablicami statycznymi.

Ciekawostka

Przy tworzeniu nowej tablicy, możemy od razu ją wypełnić. Robimy to w następujący sposób:

Linia 1. int liczby otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 5 przecinek 9 zamknij nawias klamrowy średnik.

Jeżeli liczba podanych elementów będzie mniejsza niż rozmiar tablicy, puste pola zostaną wypełnione zerami:

Linia 1. int liczby otwórz nawias kwadratowy 4 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 przecinek 6 przecinek 9 zamknij nawias klamrowy średnik.

Przedstawiona tablica będzie wyglądać następująco: [3, 6, 9, 0].

Ciekawostka

Warto zdefiniować zmienną służącą do przechowywania rozmiaru tablicy. Ułatwi to później operowanie na tablicy (np. w pętli for):

Linia 1. int rozmiar znak równości 10 średnik. Linia 2. int cyfry otwórz nawias kwadratowy 10 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 przecinek 8 przecinek 9 zamknij nawias klamrowy średnik.

Jeżeli chcielibyśmy podać naszą zmienną rozmiar bezpośrednio w deklaracji tablicy, musiałaby ona być zadeklarowana jako stała, czyli const – jej rozmiar nie mógłby zostać zmieniony w trakcie działania programu.

Linia 1. const int rozmiar znak równości 10 średnik. Linia 2. int cyfry otwórz nawias kwadratowy rozmiar zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 przecinek 8 przecinek 9 zamknij nawias klamrowy średnik.

Aby korzystać z tablic, musimy wiedzieć, jak umieszczać w nich dane i w jaki sposób odczytywać zapisane informacje. Przyjmijmy, że na pierwszym miejscu – w zdefiniowanej wcześniej tablicy przykladowaTablica – chcemy przechować liczbę 33. Robimy to, przypisując elementowi o indeksie 0 wartość 33:

Linia 1. przykladowaTablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 33 średnik.

Pamiętajmy, że elementy tablic są numerowane od zera. W przypadku naszej przykładowej tablicy pierwszy element ma indeks 0, a ostatni 9. A zatem po podaniu nazwy tablicy i wprowadzeniu w kwadratowych nawiasach indeksu 0 przypiszemy pierwszemu elementowi wartość 33.

Aby wypisać dane z wybranego elementu tablicy, należy podać jej nazwę wraz z odpowiednim indeksem w nawiasach kwadratowych:

Linia 1. std dwukropek dwukropek cout otwórz nawias ostrokątny otwórz nawias ostrokątny przykladowaTablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek endl średnik.
Ważne!

<<< std::endl; to manipulator strumienia; wstawia znak nowej linii i wymusza zapisanie danych z bufora.

Tablica jednowymiarowa – przykład

Wykonajmy proste zadanie. Z tablicy jednowymiarowej, wypełnionej liczbami, wypiszmy tylko te elementy, które są parzyste. Użyjemy operatora modulooperator modulooperatora modulo oraz instrukcji warunkowejinstrukcja warunkowainstrukcji warunkowej.

Oto szkic rozwiązania w pseudokodzie:

Linia 1. tablica znak równości otwórz nawias kwadratowy 3 przecinek 6 przecinek 9 przecinek 4 przecinek 8 zamknij nawias kwadratowy. Linia 2. rozmiarTablicy znak równości 5. Linia 4. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek rozmiarTablicy minus 1 wykonuj dwukropek. Linia 5. jeżeli tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy procent 2 znak równości 0 wykonaj dwukropek. Linia 6. wypisz tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy.

Odczytujemy kolejne elementy tablicy, korzystając z pętli for i za pomocą instrukcji warunkowej sprawdzamy, czy reszta z dzielenia poszczególnych liczb przez 2 wynosi zero. Jeżeli tak właśnie jest, wypisujemy sprawdzany element na ekranie:

Linia 1. int tablica otwórz nawias kwadratowy 5 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 3 przecinek 6 przecinek 9 przecinek 4 przecinek 8 zamknij nawias klamrowy średnik. Linia 2. int rozmiarTablicy znak równości 5 średnik. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny rozmiarTablicy średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy procent 2 znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. std dwukropek dwukropek cout otwórz nawias ostrokątny otwórz nawias ostrokątny tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek endl średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy.

Słownik

instrukcja warunkowa
instrukcja warunkowa

element sterujący, który w zależności od spełnienia określonego warunku pozwala dokonać wyboru między różnymi zestawami poleceń

operator modulo
operator modulo

zwraca resztę z dzielenia liczb całkowitych; w języku C++ jest zapisywany za pomocą symbolu %