Wejściówka – Pętle i konwersja zmiennych
Napisz program w języku C++, który wczyta od użytkownika wartość n i obliczy sumę szeregu 1 + 1/2 + 1/3 + … + 1/n.
Rozwiązanie:
#include <iostream>
using namespace std;
int main() {
int n;
float sum = 0;
cin >> n;
for(int i = 1; i<=n; ++i)
sum += 1/(float)i;
cout << sum << endl;
return 0;
}
Zadanie 1
Napisz program w języku C++, który wczyta od użytkownika przedział lewo stronnie domknięty w formacie <a;b). Następnie program powinien wyświetlić wszystkie liczby niepodzielne przez 3 i 5 w tym przedziale. Przykład: <3;16) 4, 7, 8, 11, 13, 14
Rozwiązanie:
//Version 1.0
#include <cstdio>
int main() {
int a, b;
scanf("<%d;%d)", &a, &b);
for(int i = a; i < b; ++i) {
if(i % 3 == 0 || i % 5 == 0) continue;
printf("%d, ", i);
}
return 0;
}
//Version 2.0
#include <cstdio>
int main() {
int a, b;
scanf("<%d;%d)", &a, &b);
for(int i = a; i < b; ++i) {
if(!(i % 3) || !(i % 5)) continue;
printf("%d, ", i);
}
return 0;
}
//Version 3.0
#include <cstdio>
int main() {
int a, b;
scanf("<%d;%d)", &a, &b);
for(int i = a; i < b; ++i) {
if(i % 3 != 0 && i % 5 != 0) printf("%d, ", i);
}
return 0;
}
//Version 4.0
#include <cstdio>
int main() {
int a, b;
scanf("<%d;%d)", &a, &b);
for(int i = a; i < b; ++i)
if(i % 3 && i % 5) printf("%d, ", i);
return 0;
}
Zadanie 2 – funkcje
Napisz funkcję w języku C++, która przyjmuje dwie liczby całkowite i zwraca ich iloczyn.
Rozwiązanie:
//Version 1.0
#include <iostream>
using namespace std;
// Rozwiązaniem dla tego zadania jest jedynie poniższa funkcja.
int product(int a, int b) {
return a * b;
}
int main() {
int a, b, result;
cin >> a >> b;
result = product(a, b);
cout << result << endl;
return 0;
}
//Version 2.0
#include <iostream>
using namespace std;
// Rozwiązaniem dla tego zadania jest jedynie poniższa funkcja.
int product(int a, int b) {
return a * b;
}
int main() {
int a, b;
cin >> a >> b;
cout << product(a, b) << endl;
return 0;
}
Omówienie:
Funkcja, uproszczając jest to fragment programu, któremu nadano nazwę i który możemy wykonać poprzez podanie jego nazwy oraz ewentualnych argumentów (o ile istnieją zdefiniowane parametry) w okrągłych nawiasach. Ujmując to bardziej formalnie, funkcja to samodzielny blok kodu, który realizuje określone zadanie. Funkcje można wywoływać wielokrotnie w różnych miejscach programu, co pozwala unikać duplikacji kodu i poprawia jego czytelność. Podstawowymi elementami funkcji są:
zwracany typ – typ wartości, którą funkcja zwróci po zakończeniu działania. W przypadku funkcji, która nie zwraca wartości, używa się void,
nazwa funkcji (identyfikator) – służy do wywołania funkcji i jej identyfikacji,
parametry – to zmienne zdefiniowane w nagłówku funkcji, które funkcja wykorzystuje do przechowywania wartości przekazywanych podczas jej wywołania, parametry są częścią definicji funkcji i są opcjonalne,
ciało funkcji – zawiera instrukcje, które funkcja wykonuje.
Składnia funkcji w języku C/C++ jest następująca:
typ identyfikator(typ1 parametr_1, typ2 parametr_2, typ_n parametr_n)
{
/* instrukcje funkcji */
}
Funkcja nie musi posiadać parametrów. Taką funkcją definiujemy, jak funkcję z parametrami z tą tylko różnicą, że między okrągłymi nawiasami nie znajduje się żaden parametr. Należy pamiętać, że funkcje definiuje się poza główną funkcją programu main. Język C/C++ nie umożliwia tworzenia zagnieżdżonych funkcji (funkcja wewnątrz bloku innej funkcji).
int main() {
void funkcja() { // Błąd: Funkcje nie mogą być definiowane wewnątrz innych funkcji
// Kod funkcji
}
}
W programowaniu możemy spotkać jeszcze pojęcie procedury. Przyjęło się, że procedurami nazywane są funkcje, które nie zwracają żadnej wartości, jednakże w terminologii języka C/C++ częściej mówi się o funkcji zwracającej void.
void identyfikator(typ1 parametr_1, typ2 parametr_2, typ_n parametr_n)
{
/* instrukcje funkcji */
}
Słowo kluczowe void ma kilka znaczeń, a w tym przypadku oznacza brak wartości.
W kontekście funkcji należy również nadmienić o wspomnianych już argumentach. Argumenty to rzeczywiste wartości (lub wyrażenia), które są przekazywane do funkcji w momencie jej wywołania. Innymi słowy są to dane, które funkcja otrzymuje, gdy jest wywołana, a ich typ i ilość jest zgodna z definicją parametrów. Aby wywołać funkcję należy po jej identyfikatorze dodać nawiasy okrągłe, a w nich ewentualne argumenty funkcji. Użycie samej nazwy funkcji ma zupełnie inne znaczenie – oznacza pobranie jej adresu.
/* inne instrukcje */ identyfikator(argument_1, argument_2, argument_n); //lub dla funkcji bez argumentów identyfikator(); /* inne instrukcje */
Zgodnie z informacjami przedstawionymi na poprzednich laboratoriach, w przypadku funkcji również możemy mówić o deklaracji. Deklaracja funkcji powinna znajdować się przed pierwszym jej użyciem i służy ona do poinformowania kompilatora, że dana funkcja istnieje. Podczas deklaracji można pominąć nazwy parametrów funkcji i wymienić jedynie ich typy. Deklaracja funkcji, nazywana również prototypem funkcji, informuje kompilator o istnieniu funkcji przed jej właściwą definicją, czyli implementacją jej ciała.
typ identyfikator(typ1, typ2, typ_n); //Prototyp funkcji / deklaracja funkcji
Bardzo częstym zwyczajem jest wypisanie przed główną funkcją programu main samych prototypów funkcji, by ich definicje umieścić po definicji funkcji main. Definicja funkcji to określenie ciała funkcji, czyli zaimplementowania instrukcji, które funkcja będzie wykonywać.
int a();
int b(int p);
int main() {
return b(1);
}
int a() {
return b(0);
}
int b(int p) {
if( p == 0 )
return 1;
else
return a();
}
Funkcje mogą zwracać wartości, aby to umożliwić używamy słowa kluczowego return. Instrukcja return służy do przerwania funkcji i zwrócenie określonej wartości. W przypadku funkcji zwracającej typ void służy do przerwania działania funkcji bez zwracania wartości.
Ponadto możliwe jest użycie kilku instrukcji return w obrębie jednej funkcji. Część programistów uważa, że wiele instrukcji return w obrębie bloku jednej funkcji jest złą praktyką programowania, ponieważ komplikuje śledzenie przebiegu programu. Twierdzą, że lepsze jest użycie jednej instrukcji return na końcu funkcji.
Dodatkowo instrukcja return służy czasami do zwracania kodów błędu, zaś rezultat / wynik funkcji przekazywany jest za pomocą argumentów (więcej o tym podczas omówienia referencji).
Może pojawić się pytanie: Jak zwrócić kilka wartości? Generalnie możliwe są dwa podejścia:
– możemy stworzyć strukturę / klasę i zwrócić rezultat za pomocą obiektu i instrukcji return,
– zwrócić wyniki za pomocą parametrów funkcji, używając referencji lub wskaźników.
Zadanie 3 – czas życia zmiennych, zmienne globalne
Napisz program w języku C++, który wyświetla zmienną całkowitą wczytaną od użytkownika. Wartość tej zmiennej powinna być modyfikowana za pomocą funkcji f, która przyjmuje jeden argument całkowity. Funkcja powinna ustawiać wartość zmiennej na wartość przekazaną w argumencie.
Rozwiązanie:
#include <iostream>
using namespace std;
int value;
void setValue(int a) {
value = a;
}
int main() {
cin >> value;
cout << value;
setValue(10);
cout << value;
return 0;
}
Omówienie:
Zadanie można by rozwiązać za pomocą wskaźników lub referencji, ale tych jeszcze nie poznaliśmy. W związku z powyższym użyto zmiennej globalnej.
Przejdźmy do kolejnych kwestii, pierwszą z nich jest czas życia zmiennych. Czas życia zmiennych to czas od momentu przydzielenia dla zmiennej miejsca w pamięci (stworzenie obiektu) do momentu zwolnienia miejsca w pamięci (likwidacja obiektu). Innym istotnym aspektem dotyczącym zmiennych jest ich zakres ważności. Zakres ważności to część programu, w której nazwa zmiennej znana jest kompilatorowi. Zgodnie z tym co pojawiło się na poprzednich laboratoriach, w C++ istnieją różne typy zmiennych, które mają różny czas życia i zakres ważności.
Zmienne lokalne (automatyczne) – są tworzone, gdy program wchodzi do bloku, w którym zostały zadeklarowane, a usuwane, gdy ten blok zostaje opuszczony. Można się do nich odwoływać tylko w obrębie tego bloku.
Zmienne globalne – są tworzone, gdy program się rozpoczyna, i usuwane po zakończeniu programu. Mogą być używane w całym programie.
Zmienne statyczne – mają czas życia trwający przez cały czas działania programu, ale ich zakres ważności jest ograniczony do miejsca, w którym zostały zadeklarowane. Do ich tworzenia używamy słowa kluczowego static.
#include <iostream>
using namespace std;
int main() {
int a = 10;
{ /* otwarcie lokalnego bloku */
int b = 10;
cout << a << " " << b << endl;
} /* zamknięcie lokalnego bloku, zmienna b jest usuwana */
cout << a << " " << b << endl; /* BŁĄD: b już nie istnieje */
return 0;
} /* tu usuwana jest zmienna a */
Powyższy przykład przedstawia program, w którym zdefiniowaliśmy dwie zmienne typu int. Zarówno a i b istnieją przez cały program (czas życia). Nazwa zmiennej a jest znana kompilatorowi przez cały program, zaś nazwa zmiennej b jest znana jedynie w bloku lokalnym, dlatego wystąpił błąd w linii 11.
Podobnie jest w przypadku rozwiązania naszego zadania. Zmienne stworzone w funkcji, bądź jej argumenty są zmiennymi tymczasowymi. Zmienne te pojawiają się do użytku przy każdym wywołaniu funkcji i znikają po jej opuszczeniu. Zmienne te nie przechowują stanu z poprzedniego wywołania funkcji.
Zadanie 4
Napisz program w języku C++, który wyświetla informację, czy jest możliwe skonstruowanie trójkąta z krawędzi o długościach wczytanych od użytkownika.
Rozwiązanie:
//Version 1.0
#include <iostream>
using namespace std;
void validateTriangle(float a, float b, float c) {
if( a + b <= c || b + c <= a || a + c <= b ) cout << "not ";
cout << "valid" << endl;
}
int main() {
float a, b, c;
cin >> a >> b >> c;
validateTriangle(a, b, c);
return 0;
}
//Version 2.0
#include <iostream>
using namespace std;
bool validateTriangle(float a, float b, float c) {
return !(a + b <= c || b + c <= a || a + c <= b);
}
int main() {
float a, b, c;
cin >> a >> b >> c;
cout << (validateTriangle(a, b, c) ? "valid" : "not valid");
return 0;
}
Zadanie 5
Napisz program w języku C++, który obliczy największy wspólny dzielnik i najmniejszą wspólną wielokrotność. Stwórz do tego dwie odpowiednie funkcje.
Rozwiązanie:
#include <iostream>
using namespace std;
int gcd(int x, int y) {
int t;
while(y != 0) {
t = y;
y = x % y;
x = t;
}
return x;
}
int lcm(int x, int y) {
return x * y / gcd(x, y);
}
int main() {
int x, y;
cin >> x >> y;
cout << "gcd=" << gcd(x, y) << "\tlcm=" << lcm(x, y) << endl;
return 0;
}
Zadanie 6
Zadeklaruj funkcję w języku C++, która przyjmuje typ figury szachowej, jej pozycję na szachownicy oraz pozycję docelową. Typ powinien być liczbą całkowitą, zaś każda z pozycji parą: liczba, znak. Funkcja powinna sprawdzać, czy dany typ figury można przemieścić na daną pozycję.
Rozwiązanie:
bool check(int, int, char, int, char);
Zadanie 7
Napisz funkcję, która przyjmie w argumencie liczbę zmiennoprzecinkową. Funkcja powinna zwrócić jej część ułamkową.
Rozwiązanie:
float f(float n) {
if(n < 0)
n = -n;
return n - (int)n;
}
Omówienie:
Rozwiązanie poprawne jedynie dla wartości zmiennej n mniejszej niż INT_MAX.
Zadanie 8 – liczby pseudolosowe
Napisz funkcję w języku C++, która oblicza wartość liczby PI metodą Monte Carlo.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>
float pi(int n) {
float x, y;
int counter = 0;
for(int i = 0; i < n; ++i) {
x= std::rand() / (1.f * RAND_MAX);
y= std::rand() / (1.f * RAND_MAX);
if((x - 0.5f) * (x - 0.5f) + (y - 0.5f) * (y - 0.5f) <= 0.5f * 0.5f)
counter++;
}
return 4. * counter / n;
}
int main() {
srand(time(0));
std::cout << pi(100000) << std::endl;
return 0;
}
Omówienie:
Linia 20: konfiguracja maszyny losowej.
W tej linii inicjujemy stan maszyny liczb pseudolosowych. Funkcja srand ustawia punkt startowy (ziarno) dla mechanizmu generowania kolejnych liczb całkowitych. Oczywiście tzw. zarodek/ziarno liczb pseudolosowych może być dowolny (może to być dowolna liczba całkowita), jednakże ustawienie czasu jest jedną z lepszych praktyk, ponieważ powoduje, że za każdym razem program generuje inną sekwencję liczb. Nie można o tym zapomnieć, ponieważ w innym przypadku uruchamiając ten program kilka razy, wartości wygenerowanych liczb pseudolosowych, dla kolejnych instancji naszego programu, były by takie same. Takie zachowanie oczywiście nie jest pożądane. Stąd aby każdorazowo otrzymać inne wylosowane wartości w skompilowanym programie, należy powiązać funkcję srand z czasem rzeczywistym, ustawionym obecnie w komputerze. W związku z tym, zmuszeni będziemy dodać kolejny plik nagłówkowy ctime. Biblioteka ctime dostarczy nam mi. funkcję time, która zwraca obecny czas na komputerze w postaci liczby.
Przykłady:
Poniżej przedstawiono przykłady generowania liczb pseudolosowych w różnych zakresach.
//zwraca całkowitą liczbę pseudolosową z zakresu 0..RAND_MAX
int rand1() {
return rand();
}
//zwraca całkowitą liczbę pseudolosową z zakresu 0..max, gdzie max<RAND_MAX
int rand2(int max) {
return rand() % (max + 1);
}
//zwraca całkowitą liczbę pseudolosową z zakresu min..max, gdzie min < max < RAND_MAX
int rand3(int min, int max){
return rand() % (max - min + 1) + min;
}
//zwraca zmiennoprzecinkową liczbę pseudolosową z zakresu 0..1
float rand4(){
return (float)rand() / RAND_MAX;
}
//zwraca zmiennoprzecinkową liczbę pseudolosową z dowolnego przedziału: [M;N) obustronnie domkniętego
float rand5(int M, int N) {
return (float)rand() / RAND_MAX * (N - M) + M;
}
/* Tutaj istotna uwaga
Teoretycznie, największa wartość wygenerowana przez rand() to RAND_MAX, co daje wynik bliski 1, ale nie równy dokładnie 1 po podzieleniu przez RAND_MAX. Dlatego liczba wygenerowana przez tę funkcję będzie bliska N, ale nigdy dokładnie równa N. Stąd uzyskanie przedziału obustronnie domkniętego dla liczb zmiennoprzecinkowych jest problematyczne podczas używania rand() z cstdlib. W związku z tym w takich sytuacjach należałoby użyć bardziej nowoczesnych generatorów liczb pseudolosowych np. z biblioteki random lub manualnie dostosować wynik, co może okazać się dużym wyzwaniem.
*/
float rand5(float M, float N) {
std::random_device rd; // urządzenie do losowego ziarna
std::mt19937 gen(rd()); // generator Mersenne Twister
std::uniform_real_distribution<float> dist(M, std::nextafter(N, N + 1.0f)); // rozkład jednorodny [M, N]
return dist(gen); // zwraca liczbę losową z zakresu [M, N] włącznie
}
/*
Funkcja std::nextafter zwraca najbliższą reprezentację zmiennoprzecinkową większą niż N w kierunku N +1.0f. W ten sposób rozkład obejmuje także N, ponieważ standardowy rozkład jednorodny w C++ generuje liczby w przedziale lewostronnie domkniętym i prawostronnie otwartym [M,N).
*/
Wskazówka: Użycie operacji na liczbach rzeczywistych jest często sugerowane, gdyż w przeciwieństwie do operacji modulo bierze pod uwagę bardziej znaczące bity wygenerowanej liczby, które teoretycznie są bardziej losowe od bitów mniej znaczących. Istotnie może to być prawdą, jednak nie ma to i tak większego znaczenia, gdyż jeżeli zależy nam na dużej losowości generatora powinniśmy w programie użyć innej implementacji generatora.
Generalnie generator z biblioteki standardowej nie nadaje się do bardzo poważnych zastosowań.
Należy pamiętać, że jeżeli górny zakres, do którego losujemy jest bliski wartości RAND_MAX to liczby nie będą miały równomiernego rozkładu prawdopodobieństwa. Jest to prawdą dla każdej granicy, która nie jest dzielnikiem RAND_MAX+1, jednak przy małych wartościach niedokładność jest pomijalna.
W nowoczesnym C++ możesz skorzystać z bardziej zaawansowanych generatorów pseudolosowych z biblioteki <random>, które oferują lepsze algorytmy i większą kontrolę nad rozkładem. Biblioteka ta oferuje szeroki wybór generatorów (np. Mersenne Twister) i rozkładów (np. jednorodny, normalny, wykładniczy). Są one bardziej odpowiednie do zaawansowanych obliczeń statystycznych i symulacji.
#include <iostream>
#include <random>
float pi(int n) {
std::random_device rd; // Seed dla generatora
std::mt19937 gen(rd()); // Generator Mersenne Twister
std::uniform_real_distribution<> dis(0, 1); // Rozkład jednorodny w zakresie [0, 1]
int counter = 0;
for(int i = 0; i < n; ++i) {
float x = dis(gen);
float y = dis(gen);
if((x - 0.5f) * (x - 0.5f) + (y - 0.5f) * (y - 0.5f) <= 0.5f * 0.5f)
counter++;
}
return 4.0 * counter / n;
}
int main() {
std::cout << pi(1000000) << std::endl;
return 0;
}
Zadanie 9 – tablice
Napisz program w języku C++, który stworzy 10-cio elementową tablicę liczb całkowitych i wypełni ją pseudolosowymi liczbami z przedziału <0,100>. Na koniec program powinien wyświetlić elementy tej tablicy.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define N 10
//lub
//const int N = 10
int f(int max) {
return rand() % (max + 1);
}
int main() {
srand(time(0));
int arr[N];
for(int i = 0; i < N; ++i)
arr[i] = f(100);
for(int i = 0; i < N; ++i)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Omówienie:
Tablicę deklarujemy w następujący sposób:
typ nazwa_tablicy[rozmiar];
,gdzie rozmiar oznacza ile zmiennych danego typu możemy zmieścić w tablicy. Dla przykładu aby zadeklarować tablicę, mieszczącą 10 liczb całkowitych możemy napisać tak:
int arr[10];
Ważne: Tworząc tablicę za pomocą powyższego zapisu należy pamiętać, że rozmiar musi być wartością stałą, która będzie znana w chwili kompilacji programu. Oznacza to, że użytkownik nie może określać rozmiaru tablicy w trakcie działania aplikacji (wspomniane ograniczenie dotyczy tylko i wyłącznie tablicy tworzonej w powyższy sposób). Poniższy kod prezentuje nieprawidłowe tworzenie tablicy, którego nie można stosować w kodzie.
int rozmiar; std::cin >> rozmiar; int arr[rozmiar];
Powyższy zapis jest NIEPRAWIDŁOWY! Nie można używać zmiennej do tworzenia tablicy automatycznej. Natomiast można użyć stałej. W przyszłości poznamy metody, jak tworzyć tablice, których rozmiar będzie mógł być określony przez użytkownika w trakcie działania aplikacji, w takiej sytuacji będziemy mówili o dynamicznej alokacji pamięci.
Podobnie jak przy deklaracji zmiennych, także przy deklaracji tablicy możemy nadać jej wartości początkowe. Odbywa się to przez umieszczenie wartości kolejnych elementów oddzielonych przecinkami, wewnątrz nawiasów klamrowych:
int arr[3] = {0,1,2};
, wtedy niekoniecznie trzeba podawać rozmiar tablicy (kompilator sam ustali rozmiar tablicy):
int arr[] = {0,1,2,3,4,5};
Należy nadmienić, że nie jest to jedyny sposób na inicjalizację tablicy wartościami. Deklarując tablicę i podając jej wartości początkowe, możemy podać tylko część wartości (mniej niż rozmiar tablicy), pozostałe zainicjowane zostaną zerami. Kontynuując można zainicjować tablicę samymi zerami za pomocą {} lub {0}.
Może to się wydać dziwne, ale po ostatnim elemencie tablicy może występować przecinek.
int arr_1[10] = {1,2,3,};
int arr_2[10] = {};
int arr_3[10] = {0};
Przejdźmy do tematu odczytu i zapisu wartości do tablicy.
Tablicami posługujemy się tak samo jak zwykłymi zmiennymi. Różnica polega jedynie na podawaniu indeksu tablicy. Określa on, z którego elementu (wartości) chcemy skorzystać spośród wszystkich umieszczonych w tablicy. Numeracja indeksów rozpoczyna się od zera, co oznacza, że pierwszy element tablicy ma indeks równy 0, drugi 1, trzeci 2, itd. Tym samym chcąc odwołać się do drugiego elementu tablicy użyjemy następującej składni: arr[1].
Ciekawostka: Przy odwoływaniu się do konkretnej komórki tablicy, używanym indeksem powinna być liczba całkowita, choć istnieje możliwość indeksowania za pomocą np. pojedynczych znaków (a, b, itp.), jednak w języku C/C++ dokonuje się wewnętrzna konwersja takich znaków na liczby im odpowiadające, zatem tablica indeksowana znakami byłaby niepraktyczna i musiałaby mieć odpowiednio większy rozmiar (numerem ASCII dla a jest 97).
Skoro każdy element tablicy można traktować, jak pojedyncza zmienna, to poza nadawaniem wartości konkretnym elementom tablicy, można wczytać je od użytkownika std::cin>>arr[0]; lub scanf("%d", &arr[0]);
Uwaga: Przy używaniu tablic trzeba być szczególnie ostrożnym podczas konstruowaniu pętli, ponieważ ani kompilator, ani skompilowany program nie będą w stanie wychwycić przekroczenia przez indeks rozmiaru tablicy. Efektem będzie odczyt lub zapis pamięci, znajdującej się poza tablicą, lub zakończenie programu błędem.
Pisząc poza tablicą modyfikujemy wartości innych zmiennych lub kodu maszynowego aplikacji – w efekcie można uszkodzić kod swojego programu, co prowadzi do błędu krytycznego aplikacji. Wychodząc poza zakres tablicy może się zdarzyć również, że zostanie podjęta próba pisania po pamięci innej aplikacji, na co współczesne systemy operacyjne nie pozwalają. Wtedy system operacyjny zakończy działanie naszego programu, który zakończy się błędem krytycznym, zapobiegając jednocześnie możliwości modyfikacji zasobów, które nie należały do naszego programu.
Aby sprawdzić rozmiar tablicy automatycznej możemy użyć operatora sizeof oraz następującej konstrukcji:
(sizeof(arr) / sizeof(*arr)); //lub (sizeof(arr) / sizeof(arr[0]));
Powyżej sizeof arr zwraca cały rozmiar pamięciowy tablicy, natomiast sizeof *arr poda nam jaki jest rozmiar typu int (ponieważ takiego typu jest element tablicy, *arr). Dzieląc rozmiar pamięciowy tablicy przez rozmiar pojedynczego elementu uzyskujemy ilość elementów.
Zadanie 10 – sortowanie
Do poprzedniego programu dopisz funkcję, która posortuje stworzoną tablicę. Program powinien wyświetlać posortowaną tablicę.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define N 10 // możemy użyć słowa kluczowego const do stworzenia stałej
void bubble_sort(int arr[], int n) {
int temp;
for (int i = 0 ; i < n - 1; ++i) {
for (int j = 0 ; j < n - i - 1; ++j) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void print_arr(int arr[], int n) {
for(int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
}
int f(int max) {
return rand() % (max + 1);
}
void init_array(int arr[], int n) {
for(int i = 0; i < n; ++i)
arr[i] = f(100);
}
int main() {
srand(time(0));
int arr[N];
init_array(arr, N);
print_arr(arr, N);
bubble_sort(arr, N);
print_arr(arr, N);;
return 0;
}
Omówienie:
Warto zaznaczyć, że nazwa tablicy jest wskaźnikiem na jej pierwszy element. Tym samym przekazując tablicę, jako argument funkcji, będziemy modyfikować dane znajdujące się pod oryginalnym adresem. Mówiąc prościej, wszelkie modyfikacje tablicy w ciele funkcji będą widoczne także poza blokiem funkcji. Szerzej zostanie to omówione w kolejnych laboratoriach.
Zadanie 11
Napisz funkcję w języku C++, która przyjmie jako argumenty automatyczną tablicę wartości całkowitych i ilość jej komórek. Funkcja powinna wyświetlać wszystkie unikalne wartości w tej tablicy.
Rozwiązanie:
//Version 1.0
#include <iostream>
#include <climits>
void unique(int arr[], int n) {
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
if(arr[i] == arr[j])
arr[j] = INT_MAX;
for(int i = 0; i < n; ++i)
if(arr[i] != INT_MAX)
std::cout << arr[i] << std::endl;
}
//Version 2.0
void unique(int arr[], int n) {
int counter;
for(int i = 0; i < n; ++i) {
counter = 0;
for(int j = i; j < n; ++j) if(arr[i] == arr[j]) counter++;
if(counter == 1) std::cout << arr[i] << " ";
}
}
//Version 3.0
#include <iostream>
#include <cstdlib>
void bubble_sort(int arr[], int n) {
for (int i = 0 ; i < n - 1; ++i) {
for (int j = 0 ; j < n - i - 1; ++j) {
if (arr[j] > arr[j+1]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
void unique(int arr[], int n) {
bubble_sort(arr, n);
for(int i = 0; i < n - 1; ++i)
if(arr[i] != arr[i+1])
std::cout << arr[i] << std::endl;
for(int i = n - 2; i >= 0; --i)
if(arr[n - 1] != arr[i]) {
std::cout << arr[n - 1] << " ";
break;
}
if(arr[0] == arr[n - 1]) std::cout << arr[0] << " ";
}
Omówienie:
Warto zastanowić się, czy powyższe zadanie da się rozwiązać nie modyfikując oryginalnej tablicy.
Zadanie 12
Napisz program w języku C++, który odwraca kolejność elementów w tablicy.
Rozwiązanie:
#include <iostream>
void reverse_arr(int arr[], unsigned int n) {
int tmp;
unsigned int s = 0, e = n - 1;
while(s < e) {
tmp = arr[s];
arr[s++] = arr[e];
arr[e--] = tmp;
}
}
void print_arr(int arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
const unsigned int size = 5;
int arr[size] = {1, 2, 3, 4, 5};
print_arr(arr, size);
reverse_arr(arr, size);
print_arr(arr, size);
return 0;
}
Zadanie 13
Napisz program w języku C++, który obliczy sumę wszystkich elementów tablicy, jej średnie arytmetyczną, geometryczną i harmoniczną oraz odchylenie standardowe.
Rozwiązanie:
#include <iostream>
#include <cmath>
float calculate_sum(int arr[], unsigned int n) {
float sum = 0.f;
for(unsigned int i = 0; i < n; ++i) sum += arr[i];
return sum;
}
float calculate_mean(int arr[], unsigned int n) {
return calculate_sum(arr, n) / n;
}
float calculate_geometric_mean(int arr[], unsigned int n) {
float product = 1.f;
for(unsigned int i = 0; i < n; ++i) product *= arr[i];
return std::pow(product, 1.f / n);
}
float calculate_harmonic_mean(int arr[], unsigned int n) {
float reciprocal = 0.f;
for(unsigned int i = 0; i < n; ++i) reciprocal += 1.f / arr[i];
return n / reciprocal;
}
float calculate_std(int arr[], unsigned int n) {
float sum_of_squares = 0.f;
float mean = calculate_mean(arr, n);
for(unsigned int i = 0; i < n; ++i)
sum_of_squares += std::pow(arr[i] - mean, 2);
return std::sqrt(sum_of_squares / n);
}
int main() {
const unsigned int size = 5;
int arr[size] = {1, 2, 3, 4, 5};
std::cout << "Suma: " << calculate_sum(arr, size) << std::endl;
std::cout << "Średnia arytmetyczna: " << calculate_mean(arr, size) << std::endl;
std::cout << "Średnia geometryczna: " << calculate_geometric_mean(arr, size) << std::endl;
std::cout << "Średnia harmoniczna: " << calculate_harmonic_mean(arr, size) << std::endl;
std::cout << "Standardowe odchylenie: " << calculate_std(arr, size) << std::endl;
return 0;
}
Zadanie 14
Napisz program w języku C++, który wykona dla dwóch N-elementowych tablic liczb zmiennoprzecinkowych operację iloczynu skalarnego i wyświetli wynik. Iloczyn skalarny jest operacją zdefiniowaną jako suma iloczynów elementów o tych samych współrzędnych.
Rozwiązanie:
#include <iostream>
float dot_product(float arr_0[], float arr_1[], unsigned int n) {
float result = 0.f;
for(unsigned int i = 0; i < n; ++i) result += arr_0[i] * arr_1[i];
return result;
}
int main() {
const unsigned int n = 5;
float arr_0[n] = {1.f, 2.f, 3.f, 4.f, 5.f}, arr_1[n] = {1.f, 2.f, 3.f, 4.f, 5.f};
std::cout << "Iloczyn skalarny: " << dot_product(arr_0, arr_1, n) << std::endl;
return 0;
}
Zadanie 15
Napisz program w języku C++, który dla tablicy liczb całkowitych przesuwa o 1 w prawo wszystkie elementy tablicy (tak, żeby wartość elementu o indeksie 0 znalazła się w elemencie o indeksie 1, wartość elementu o indeksie 1 znalazła się w elemencie o indeksie 2, zaś wartość elementu o indeksie n-1 w elemencie o indeksie 0).
Rozwiązanie:
#include <iostream>
void print_arr(int arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
void move_arr(int arr[], unsigned int n) {
int tmp = arr[n - 1];
for (unsigned int i = n - 1; i > 0; i--) arr[i] = arr[i - 1];
arr[0] = tmp;
}
int main() {
const unsigned int n = 5;
int arr[n] = {1, 2, 3, 4, 5};
print_arr(arr, n);
move_arr(arr, n);
print_arr(arr, n);
return 0;
}
Zadanie 16
Napisz program w języku C++, który rozbudowuje funkcjonalność poprzedniego programu o możliwość przesuwania o dowolną ilość indeksów (również dla przesunięć ujemnych).
Rozwiązanie:
#include <iostream>
void print_arr(int arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
void move_arr(int arr[], int n, int tmp[], int m) {
for (int i = 0; i < n; ++i) {
int idx = (i + m) % n;
if (idx < 0) idx += n;
tmp[idx] = arr[i];
}
for (int i = 0; i < n; ++i) arr[i] = tmp[i];
}
int main() {
const unsigned int n = 5;
int m, arr[n] = {1, 2, 3, 4, 5}, tmp[n] = {};
std::cin >> m;
print_arr(arr, n);
move_arr(arr, n, tmp, m);
print_arr(arr, n);
return 0;
}
Zadanie 17
Napisz program w języku C++, który utworzy 5-elementową tablicę liczb całkowitych i zapisze w jej komórkach 5 liczb podanych ze standardowego wejścia. Na koniec program powinien wyświetlić elementy tablicy.
Rozwiązanie:
#include <iostream>
void print_arr(int arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
int arr[5];
for (int i = 0; i < 5; ++i) std::cin >> arr[i];
print_arr(arr, 5);
return 0;
}
Zadanie 18
Napisz program w języku C++, który utworzy dwie tablice liczb całkowitych n- i m-elementową. Rozmiary n i m zdefiniuj w kodzie z użyciem stałych. Zapełnij te tablice danymi (w dowolny sposób, np. wprowadzonymi ze standardowego wejścia, kolejnymi lub pseudolosowymi liczbami). Następnie utwórz tablicę o rozmiarze n + m i zapisz w jej n początkowych komórkach zawartość tablicy n-elementowej, a w pozostałych zawartość tablicy m-elementowej.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>
const int n = 5;
const int m = 3;
void fill_arr(int arr[], int n) {
for (int i = 0; i < n; ++i) arr[i] = rand() % 10;
}
void print_arr(int arr[], int n) {
for (int i = 0; i < n; ++i) std::cout << arr[i] << " ";
std::cout << std::endl;
}
void merge_arrs(int arr_n[], int n, int arr_m[], int m, int arr_nm[]) {
for (int i = 0; i < n; ++i) arr_nm[i] = arr_n[i];
for (int i = 0; i < m; ++i) arr_nm[n + i] = arr_m[i];
}
int main() {
srand(time(0));
int arr_n[n], arr_m[m], arr_nm[n + m] = {};
fill_arr(arr_n, n);
print_arr(arr_n, n);
fill_arr(arr_m, m);
print_arr(arr_m, m);
print_arr(arr_nm, n + m);
merge_arrs(arr_n, n, arr_m, m, arr_nm);
print_arr(arr_nm, n + m);
return 0;
}
Zadanie 19
Napisz program w języku C++, który utworzy n-elementową tablicę liczb całkowitych i zapełni ją danymi. Program powinien wyświetlić indeks komórki tablicy, w której została znaleziona liczba o największej wartości. Jeżeli ta sama liczba pojawia się w większej liczbie komórek, należy wyświetlić indeks dowolnej z nich.
Rozwiązanie:
#include <iostream>
unsigned int max_value_idx(int arr[], unsigned int n) {
int max = arr[0];
unsigned int idx = 0;
for(unsigned int i = 1; i < n; ++i)
if(max < arr[i])
max = arr[i], idx = i;
return idx;
}
int main() {
const unsigned int n = 5;
int arr[n] = {1, 5, 2, 3, 4};
std::cout << "Indeks komórki z największą wartością: " << max_value_idx(arr, n) << std::endl;
return 0;
}
Zadanie 20
Zmodyfikuj program z poprzedniego zadania tak, aby w przypadku, gdy liczba o największej wartości pojawia się w tablicy wielokrotnie, program wyświetlił indeksy wszystkich komórek, w których znajduje się ta liczba.
Rozwiązanie:
#include <iostream>
void max_value_indexes(int arr[], unsigned int n, bool result[]) {
int max = arr[0];
for(unsigned int i = 1; i < n; ++i)
if(max < arr[i]) max = arr[i];
for(unsigned int i = 0; i < n; ++i)
if(max == arr[i]) result[i] = true;
}
void print_results(bool result[], unsigned int n) {
for(unsigned int i = 0; i < n; ++i)
if(result[i]) std::cout << i << " ";
std::cout << std::endl;
}
int main() {
const unsigned int n = 5;
int arr[n] = {1, 5, 2, 5, 4};
bool result[n] = {};
max_value_indexes(arr, n, result);
print_results(result, n);
return 0;
}
Zadanie 21
Napisz program w języku C++, który utworzy n-elementową tablicę liczb całkowitych i zapełni ją danymi. Program powinien zmodyfikować zawartość tablicy tak, aby liczby parzyste znalazły się w początkowej, a liczby nieparzyste w końcowej części tablicy. Kolejność liczb w ramach grupy parzystych i nieparzystych jest dowolna.
Rozwiązanie:
#include <iostream>
void my_swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
void rearrange_arr(int arr[], unsigned int n) {
unsigned int even_idx =0, odd_idx = n - 1;
while (even_idx < odd_idx) {
while (!(arr[even_idx] % 2) && even_idx < odd_idx) even_idx++;
while (arr[odd_idx] % 2&& even_idx < odd_idx) odd_idx--;
if (even_idx < odd_idx) my_swap(arr[even_idx], arr[odd_idx]);
}
}
void print_arr(int arr[], unsigned int n) {
for (int i = 0; i < n; ++i) std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
const unsigned int n = 10;
int arr[n] = {1, 5, 2, 5, 4, 6, 7, 0, 10, 9};
rearrange_arr(arr, n);
print_arr(arr, n);
return 0;
}
Przygotuj się na kolejne laboratorium!
W celu przygotowania się na kolejne zajęcia, spróbuj wykonać poniższe zadania samodzielnie.
Zadanie 1
Napisz funkcję w języku C++, która przyjmie referencje na dwie liczby zmiennoprzecinkowe. Funkcja powinna zamienić wartościami zmienne, do których przekazane zostały referencje i nic nie zwracać.
Zadanie 2
Napisz dwie, niezależne funkcje w języku C++ obliczające silnię liczby naturalnej podanej w argumencie funkcji. Pierwsza z funkcji powinna do rozwiązania wykorzystywać pętlę, druga funkcja powinna być rekurencyjna.
Zadanie 3
Napisz funkcję w języku C++, która przyjmie jako argumenty jednowymiarową tablicę liczb zmiennoprzecinkowych, jej rozmiar oraz dwie liczby całkowite określające zakres domkniętego przedziału. Funkcja powinna wyzerować komórki nie zawierające liczb z tego przedziału.
Zadanie 4
Napisz funkcję w języku C++, która przyjmie jako argumenty jednowymiarową tablicę liczb zmiennoprzecinkowych oraz jej rozmiar. Funkcja powinna zmodyfikować tablicę tak, aby komórki zawierające zero znalazły się na końcu tablicy.
Przykład:
WE: 0 5 3 7 6 0 0 3 1 2 6 0 4 1 2
WY: 5 3 7 6 3 1 2 6 4 1 2 0 0 0 0
Zadanie 5
Napisz funkcję w języku C++, która przyjmie jako argumenty tablicę dwuwymiarową liczb całkowitych o n wierszach i 10 kolumnach oraz liczbę n. Funkcja powinna sprawdzić, czy tablica spełnia warunek, że suma wartości komórek z każdej kolumny, jest większa od sumy wartości z kolumny ją poprzedzającej. Funkcja powinna zwrócić wartośc logiczną informującą, czy warunek został spełniony.
