Wejściówka – funkcje, tablice i liczby pseudolosowe
Napisz funkcję w języku C++, która przyjmuje jako argument automatyczną tablicę wartości całkowitych oraz jej rozmiar. Funkcja powinna wypełnić tablicę wartościami pseudolosowymi z przedziału <20;40>.
Rozwiązanie:
#include <cstdlib>
const int MIN = 20;
const int MAX = 40;
void f(int arr[], int n) {
for(int i=0; i<n; ++i)
arr[i] = MIN + rand() / (RAND_MAX / (MAX - MIN + 1));
}
Zadanie 1 – makrodefinicje
Napisz funkcję w języku C++, która zwraca kwadrat liczby podanej w argumencie. Skorzystaj z dyrektywy preprocesora #define.
Rozwiązanie:
#include <iostream>
#define SQUARE(x) ((x)*(x))
int main () {
int v;
std::cin >> v;
std::cout << SQUARE(v) << std::endl;
return 0;
}
Omówienie:
Dyrektywa preprocesora #define już pojawiła się w tym kursie. Warto o niej przypomnieć w kontekście funkcji.
W linii 2 przedstawiono inną postać dyrektywy preprocesora #define, która służy do definicji tzw. makrodefinicji. Makrodefinicje, podobnie jak mechanizm stałych, pozwala na przyśpieszenie procesu tworzenia kodu przez tworzenie szablonów, według których części kodu generowane są przez preprocesor. Stałe definiowane za pomocą tej dyrektywy preprocesora są szczególnym przypadkiem makra, które nie posiada argumentów. Dodatkowo należy pamiętać, że dyrektywa preprocesora #define zastępuje wszystkie wystąpienia zdefiniowanego symbolu odpowiadającym mu ciągiem znaków aż do znacznika końca linii. Z tego powodu za makro definicją nie pojawia się średnik ;. Preprocesor wykonuje wyżej wspomniane zastąpienia przed właściwą kompilacją kodu, tym samym do kompilatora trafi kod z już rozwiniętymi makrami.
Aby stworzyć makrodefinicję, należy użyć dyrektywy preprocesora #define, następnie podać identyfikator i w okrągłych nawiasach ( ) nazwy kolejnych argumentów, które tak jak w funkcji możemy wykorzystać do wykonywania wybranych instrukcji (np. obliczeń arytmetycznych).
W momencie wystąpienia makrodefinicji w kodzie, preprocesor automatycznie zamieni makro na wyrażenie lub instrukcje. Makra mogą być pewnego rodzaju alternatywą dla funkcji, ale powinno się ich używać tylko w specjalnych przypadkach. Ponieważ makro sprowadza się do prostego zastąpienia przez preprocesor wywołania makra przez jego tekst, jest bardzo podatne na trudne do zlokalizowania błędy (kompilator będzie podawał błędy w miejscach, w których nic nie widzimy, bo preprocesor wstawił tam tekst). Podsumowując, należy pamiętać, że makra są szybsze, ale też mniej bezpieczne i elastyczne niż funkcje.
Preprocesor miejsce wystąpienia makra SQUARE(v) zastąpi przez ciąg znaków ((v)*(v)).
Zastanówmy się, co stałoby się, gdybyśmy napisali SQUARE("2"). Preprocesor po prostu wstawi napis do kodu, co da wyrażenie (("2")*("2")), które jest nieprawidłowe. Kompilator zgłosi błąd, ale programista widzi tylko w kodzie użycie makra a nie prawdziwą przyczynę błędu. Widać tu, że bezpieczniejsze jest użycie funkcji, które dają możliwość wyspecyfikowania typów argumentów.
Nawet jeżeli program się skompiluje to makro może dawać nieoczekiwany wynik. Jest tak w przypadku poniższego kodu:
int result = SQUARE(++v);
Dzieje się tak dlatego, że makra rozwijane są przez preprocesor i kompilator widzi kod:
int result = ((++v) * (++v));
Przykłady innych makrodefinicji, które mogą prowadzić do błędu:
#define SUM(a, b) a + b #define PRODUCT(a, b) a * b SUM(2, 2) * 2; /* 6 zamiast 8 */ PRODUCT(2 + 2, 2 + 2); /* 8 zamiast 16 */
Zadanie 2 – inline
Zmodyfikuj poprzedni program tak, aby skorzystać z funkcji inline.
Rozwiązanie:
#include <iostream>
inline int square(int a) {
return a * a;
}
int main() {
int a = 2, c;
c = square(a);
std::cout << c << std::endl;
return 0;
}
Omówienie:
W rzeczywistości powyższy kod działa nieco podobnie do omawianych już makrodefinicji. W miejsce wywołania funkcji nie zostaje wstawiony wskaźnik do tej funkcji (tak jak ma to miejsce podczas wywołania funkcji bez specyfiaktora inline), a wprowadzany jest jej kod, co zaprezentowano poniżej. Jednakże funkcje z tym specyfiaktorem dalej występująca w pamięci i możemy tworzyć do nich wskaźniki.
int main () {
int a = 2, c;
{
c = a * a; //podstawianie kodu funkcji
}
std::cout << c << std::endl;
return 0;
}
Specyfikator inline stosowany jest, gdy zależy nam na szybkości działania programu, wykonaniu tej funkcji. inline zazwyczaj dodaje się krótkim funkcjom, nie mającym więcej niż kilkanaście linijek kodu. Czasami gdy kompilator uzna, że nasza funkcja jest zbyt długa lub wywołuje się rekurencyjnie ignoruje nasze inline.
Sprawdźmy, czy funkcje inline dostępne od standardu C99, są podatne na te same problemy co makrodefinicje.
#include <iostream>
inline int square(int a)
{
return a*a;
}
int main() {
int a = 2, c;
c = square(++a);
std::cout << c << std::endl;
return 0;
}
Otrzymaliśmy wynik równy 9, czyli to czego moglibyśmy się spodziewać. Wniosek jest prosty, funkcje inline nie są podatne na te same problemy, co makrodefinicje.
Przewagi funkcji inline:
- czytelność,
- konwersja argumentów, sprawdzanie typów (funkcje
inlineimitują zwykłe funkcje zachowując wszystkie zasady C++), - argumenty jako zmienne.
Uwaga: Kod funkcji inline jest wstawiany w miejsce wywołania, np. jeśli wywołamy tę funkcję 6 razy, dostaniemy 6 kopii kodu tejże funkcji. Tym samym możemy doprowadzić do sytuacji, w której przy zbyt częstym dodawaniu specyfikatora inline do zbyt wielu funkcji, plik wykonywalny może zajmować bardzo dużo pamięci, a to wydłuża czas jego uruchamiania. Z drugiej strony wstawienie kodu funkcji bezpośrednio w miejscu wywołania redukuje liczbę wywołań funkcji, co może zmniejszyć obciążenie stosu w przypadku częstych, prostych funkcji.
Zadanie 3 – własny generator liczb pseudolosowych
Napisz funkcję w języku C++, która będzie własną implementacją generatora liczb pseudolosowych np. generator liniowy Lehmara. Napisz program w języku C++, który przetestuje ten generator.
Rozwiązanie:
#include <iostream>
#include <ctime>
int lcg(int a, int b, int m, int seed, int n) {
if(n == 1) return seed % m;
return (a * lcg(a, b, m, seed, n - 1) + b) % m;
}
int main() {
int seed = time(0), a = 403, b = 43, m = 201; //int a = 3, b = 4, m = 16;
for(int i = 1; i < 200; ++i)
std::cout << lcg(a, b, m, seed, i) << "\t";
std::cout << std::endl;
return 0;
}
Omówienie:
W powyższym rozwiązaniu zaimplementowano uproszczony liniowy generator kongruencyjny (Linear Congruential Generator). Określony jest on następującym algorytmem (a, b i m to odpowiednio dobrane znane stałe):
- stan początkowy (wartość ziarna, żeby generować bit):
time(0) % m; - kolejny stan obliczony następującą metodą:
nowy_stan = (a * stary_stan + b) % m;
Generator ten nie jest bezpieczny – dla pewnych kombinacji parametrów jest prawie losowy, dla innych bardzo szybko staje się okresowy. Dodatkowo, znane są ogólne metody obliczania parametrów i przewidywania zachowania takich generatorów liczb pseudolosowych na podstawie obserwacji wyników.
Zadanie 4 – rekurencja
Napisz funkcję w języku C++, która wyświetla wartości od 1 do N, bez użycia pętli. Zaimplementuj odpowiedni program, który sprawdzi działanie funkcji i wczyta od użytkownika wartość zmiennej N.
Rozwiązanie:
#include <iostream>
using namespace std;
void print(int current, int max) {
if(current <= max) {
cout << current << endl;
print(current + 1, max);
}
}
int main() {
int N;
cin >> N;
print(1, N);
return 0;
}
Omówienie:
Rekurencja (rekursja, ang. recursion), polega na wywołaniu przez funkcję samej siebie. Algorytmy rekurencyjne zastępują w pewnym sensie iteracje. Niekiedy problemy rozwiązywane tą techniką będą miały nieznacznie wolniejszy czas od iteracyjnego odpowiednika (wiąże się to z wywoływaniem funkcji), natomiast rozwiązanie niektórych problemów jest znacznie wygodniejsze. Najbardziej klasycznym przykładem takiej funkcji może być silnia.
Zadanie 5 – silnia
Napisz funkcję w języku C++, która przyjmuje w argumencie liczbę całkowitą bez znaku. Funkcja powinna obliczyć wartość silni dla argumentu i zwrócić wynik. Napisz program w języku C++, który sprawdzi działanie tej funkcji.
Rozwiązanie:
//Version 1.0
#include <iostream>
using namespace std;
typedef unsigned int uint;
uint factorial(uint i) {
if(i <= 1) {
return 1;
}
return i * factorial(i - 1);
}
int main() {
uint n;
cin >> n;
cout << factorial(n) << endl;
return 0;
}
//Version 2.0
#include <iostream>
using namespace std;
typedef unsigned int uint;
uint factorial(uint i) {
return i <= 1 ? 1 : i * factorial(i - 1);
}
int main() {
uint n;
cin >> n;
cout << factorial(n) << endl;
return 0;
}
//Version 3.0
#include <iostream>
using namespace std;
typedef unsigned int uint;
uint factorial(uint value) {
uint result;
if(value == 0) return 1;
else for(result = 1; value > 0; --value) result *= value;
return result;
}
int main() {
uint n;
cin >> n;
cout << factorial(n) << endl;
return 0;
}
Omówienie:
Musimy być ostrożni przy funkcjach rekurencyjnych, gdyż łatwo za ich pomocą utworzyć funkcję, która będzie sama siebie wywoływała w nieskończoność, a co za tym idzie będzie zawieszała program.
Version 1.0, 2.0 i 3.0:
Aby tego uniknąć należy użyć instrukcji warunkowej, która ustali warunek stopu, gdzie kończy się wywoływanie funkcji przez samą siebie, a następnie określamy, jak funkcja będzie wywoływać samą siebie.
Warto też zauważyć, że funkcje rekurencyjne czasami mogą być znacznie wolniejsze niż podejście nierekurencyjne (iteracyjne, przy użyciu pętli). Innym flagowym przykładem może tu być funkcja obliczająca wyrazy ciągu Fibonacciego, którą omówimy w kolejnym zadaniu.
Zadanie 6 – ciąg Fibonacciego
Napisz funkcję w języku C++, która przyjmuje w argumencie liczbę całkowitą bez znaku K. Funkcja powinna zwracać wartość K-tego wyrazu ciągu Fibonacciego. Napisz program w języku C++, który sprawdzi działanie tej funkcji.
Rozwiązanie:
#include <cstdio>
#include <ctime>
typedef unsigned int uint;
uint count;
uint fib_rec(uint n) {
++count;
return n < 2 ? n : (fib_rec(n - 2) + fib_rec(n - 1));
}
uint fib_it (uint n) {
uint a = 0, b = 0, c = 1;
++count;
if (!n) return 0;
while (--n) {
++count;
a = b;
b = c;
c = a + b;
}
return c;
}
int main() {
uint n, result;
while(scanf("%d", &n) == 1) {
count = 0;
clock_t start = clock();
result = fib_rec(n);
clock_t end = clock();
printf("fib_rec: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
count = 0;
start = clock();
result = fib_it(n);
end = clock();
printf("fib_it: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
}
return 0;
}
Omówienie:
Jak zostało to zaprezentowane wyżej, funkcja rekurencyjna ma znacznie łatwiejszy i krótszy zapis, jednakże ma to swoje konsekwencje: gorszą wydajność.
Dużą zaletą rekurencja jest możliwość przedstawienia niektórych skomplikowanych problemów w bardziej czytelny sposób, szczególnie problemów, których rozwiązania są naturalnie (albo z definicji) rekurencyjne np. problemy matematyczne, struktury drzewiaste, czy problemy finansowe.
Pułapką stosowania rekurencji jest to, że łatwo napisać coś, co będzie wymagało dużej ilości zasobów (pamięci i mocy obliczeniowej) do rozwiązania wybranego problemu obliczeniowego. Przykładem może być przedstawiona wyżej rekurencyjna implementacja funkcji, która oblicza kolejne wyrazy ciągu Fibonacciego. Wygląda niewinnie, jest wręcz skopiowana z matematycznej definicji, a jednak jest to prawdopodobnie najgorsza możliwa implementacja.
Uzupełniając, dla osób zainteresowanych szczegółami, innym ograniczeniem jest ilość miejsca na stosie*, więc da się go przepełnić i wywołać błąd krytyczny aplikacji. Większe i cięższe argumenty i zmienne lokalne funkcji przyspieszają ten proces, bo zwiększają ilość miejsca, które jest zajmowane na stosie z każdym wywołaniem. Podsumowując jest pewien limit wywołań rekurencyjnych.
*Nie wchodząc w szczegóły stos, to struktura danych (LIFO – Last In, First Out), która w kontekście funkcji jest fragmentem obszaru pamięci przydzielonego wykonującemu się programowi, gdzie umieszczane są informacje niezbędne do działania funkcji.
Zadanie 7 – rekurencja ogonowa*
Zoptymalizuj rozwiązanie rekurencyjne zwracające wartość K-tego wyrazu ciągu Fibonacciego.
Rozwiązanie:
#include <cstdio>
#include <ctime>
typedef unsigned int uint;
uint count;
uint fib_rec(uint n) {
++count;
return n < 2 ? n : (fib_rec(n - 2) + fib_rec(n - 1));
}
uint fib_it (uint n) {
uint a = 0, b = 0, c = 1;
++count;
if (!n) return 0;
while (--n) {
++count;
a = b;
b = c;
c = a + b;
}
return c;
}
uint fib_tail_rec (uint n, uint a, uint b) {
++count;
if (n == 0) return a;
if (n == 1) return b;
return fib_tail_rec(n - 1, b, a + b);
}
int main() {
uint n, result;
while(scanf("%d", &n) == 1) {
count = 0;
clock_t start = clock();
result = fib_rec(n);
clock_t end = clock();
printf("fib_rec: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
count = 0;
start = clock();
result = fib_it(n);
end = clock();
printf("fib_it: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
count = 0;
start = clock();
result = fib_tail_rec(n, 0 , 1);
end = clock();
printf("fib_tail_rec: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
}
return 0;
}
Omówienie:
Rekurencja ogonowa jest jedną z form optymalizacji rekurencji, drugą może być programowanie dynamiczne, jednak w to nie będziemy się zagłębiać na tych zajęciach.
Ilość kroków wynika z tego, jak rozwijana i składana jest rekurencja. Różnica pomiędzy rekurencją, a rekurencją ogonową jest taka, że pierwsza rozwija się i się zwija, zaś druga działa od razu od końca, co wynika z wywołania fib_tail_rec(n, 0, 1), można by powiedzieć, że od razu się zwija.
Zadanie 8
Napisz funkcję w języku C++, która rekurencyjnie liczy wartość elementów wielomianu Czybyszewa pierwszego rodzaju. Zaimplementuj odpowiednie funkcje i program, który sprawdza działanie tych funkcji. Rozwiązanie powinno być rozwiązaniem optymalnym.
Rozwiązanie:
#include <cstdio>
#include <ctime>
typedef unsigned int uint;
uint count;
float rec(int k, float x) {
count++;
if(k == 0) return 1;
if(k == 1) return x;
return 2 * x * rec(k - 1, x) - rec(k - 2, x);
}
float tail_rec(int k, float x, float a, float b) {
count++;
if(k == 0) return a;
return k == 1 ? b : tail_rec(k - 1, x, b, 2 * x * b - a);
}
int main() {
uint n, result;
while(scanf("%d", &n) == 1) {
count = 0;
clock_t start = clock();
result = rec(n, 2.f);
clock_t end = clock();
printf("rec: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
count = 0;
start = clock();
result = tail_rec(n, 2.f, 1.f, 2.f);
end = clock();
printf("tail_rec: %u, %u, %f\n", result, count, (float)(end - start) / CLOCKS_PER_SEC);
}
return 0;
}
Omówienie:
W powyższym kodzie przedstawiliśmy rozwiązania nieoptymalne i optymalne, które porównano. Krok po kroku przekształciliśmy rekurencyjną metodę liczenia elementów wielomianu Czybyszewa pierwszego rodzaju.
float rec(int k, float x) {
if(k == 0) return 1;
if(k == 1) return x;
return 2 * x * rec(k - 1, x) - rec(k - 2, x);
}
Należy teraz zoptymalizować powyższą rekurencję do rekurencji ogonowej. Jak widać musimy zapamiętywać dwa elementy podobnie do Fibonacciego k - 1, k - 2.
float tail_rec(int k, float x, float a, float b) {
if(k == 0) return a;
if(k == 1) return b;
return tail_rec(k - 1, x, b, 2 * x * b - a);
}
Warto dodać, że zaproponowana w tym wpisie weryfikacja czasu służy tylko do porównania naszych funkcji i jest wystarczająca, aby zobaczyć różnice pomiędzy rozwiązaniem rekurencyjnym i iteracyjnym. Jednakże nie jest to implementacja, która bardzo dokładnie wykonuje pomiar czasu. Szczegółowe omówienie i inne metody mierzenia czasu pojawią się w oddzielnym wpisie, niedotyczącym kursu „Podstawy programowania” (Pomiary czasu).
Zadanie 9
Napisz funkcję w języku C++, która przyjmie jako argumenty automatyczną tablicę wartości całkowitych oraz jej rozmiar. Funkcja powinna zwracać wartość z tej tablicy, która jest najbliższa średniej arytmetycznej wszystkich wartości z tej tablicy. Napisz program w języku C++, który przetestuje działanie tej funkcji.
Rozwiązanie:
#include <iostream>
#include <cmath>
using namespace std;
float avg(int arr[], int n) {
float sum = 0;
for(int i = 0; i < n; ++i) sum += arr[i];
return sum / n;
}
int closest_to_avg(int arr[], int n) {
float av = avg(arr, n);
float min = fabs(arr[0] - av);
int index = 0;
for(int i = 1; i < n; ++i) {
float value = fabs(arr[i] - av);
if(value < min) {
min = value;
index = i;
}
}
return arr[index];
}
int main() {
int arr[10] = {0, 1, 2, 3, 5, 6, 7, 8, 11, 12};
cout << closest_to_avg(arr, 10) << endl;
return 0;
}
Zadanie 10
Zmodyfikuj poprzedni program tak, aby zwracał wynik za pomocą argumentu funkcji.
Rozwiązanie:
#include <iostream>
#include <cmath>
using namespace std;
float avg(int arr[], int n) {
float sum = 0;
for(int i = 0; i < n; ++i) sum += arr[i];
return sum / n;
}
void closest_to_avg(int arr[], int n, int &result) {
float av = avg(arr, n);
float min = fabs(arr[0] - av);
int index = 0;
for(int i = 1; i < n; ++i) {
float value = fabs(arr[i] - av);
if(value < min) {
min = value;
index = i;
}
}
result = arr[index];
}
int main() {
int result, arr[10] = {0, 1, 2, 3, 5, 6, 7, 8, 11, 12};
closest_to_avg(arr, 10, result);
cout << result << endl;
return 0;
}
Omówienie:
Przekazywanie argumentów przez referencję jest kolejnym sposobem przekazywania argumentów do funkcji. Aby przekazać argument przez referencję należy poprzedzić nazwę argumentu symbolem &, wtedy zmienne wewnątrz funkcji nie są kopią. Oznacza to, że operując na zmiennych referencyjnych operujemy także na zmiennej oryginalnej. Referencja występuje jedynie w języku C++ (oraz innych językach wysokiego poziomu tj. C# i Java). Mechanizm ten bardziej szczegółowo zostanie omówiony podczas podejmowania tematu wskaźników. Na ten moment należy pamiętać, że przekazywanie argumentów przez referencję umożliwia modyfikowanie oryginalnej zmiennej w ciele funkcji. (Zmiany widoczne będą wszędzie, tak samo jak ma to miejsce w przypadku tablic przekazywanych w argumencie funkcji.)
Zadanie 11
Napisz funkcję w języku C++, która przyjmie jako argumenty dwuwymiarową automatyczną tablicę wartości całkowitych i zwraca największą wartość z tej tablicy. Napisz program w języku C++, który przetestuje działanie tej funkcji.
Rozwiązanie:
#include <iostream>
using namespace std;
#define N 5
#define M 10
int max_2d_array(int arr[][M], int n, int m) { //Wszystkie rozmiary poza skrajnie lewym muszą zostać podane arr[][m]
int max = arr[0][0];
for(int i = 0; i < n; ++i)
for(int j = 0; j< m; ++j)
if(arr[i][j] > max)
max = arr[i][j];
return max;
}
int main() {
int arr[N][M];
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j)
arr[i][j] = i * j;
cout << max_2d_array(arr, N, M) << endl;
return 0;
}
Omówienie:
Inicjalizacja tablic wielowymiarowych = {{},{},{}}; można zrobić to również = {}; ale jest to mniej czytelne.
Zadanie 12
Zmodyfikuj poprzednią funkcję tak, aby przyjmowała dwuwymiarową automatyczną tablicę, jako jednowymiarową automatyczną tablicę wartości całkowitych.
Rozwiązanie:
#include <iostream>
using namespace std;
#define N 5
#define M 10
int max_2d_array(int *arr, int n, int m) {
int max = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(arr[i * m + j] > max)
max = arr[i * m + j];
return max;
}
int main() {
int arr[N][M];
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j)
arr[i][j] = i * j;
cout << max_2d_array((int *)arr, N, M) << endl;
return 0;
}
Omówienie:
W powyższym rozwiązaniu w linii 21 użyto konwersji dwuwymiarowej tablicy automatycznej na wskaźnik int *. Konwersja ta zostanie szerzej omówienia we wpisie o wskaźnikach.
Dla osób zainteresowanych szczegółami, w większości kontekstów nazwy tablic zmieniają się na wskaźniki. To jest powód, dla którego można używać wskaźników, aby uzyskać dostęp do elementów tablic. Należy jednak pamiętać, że wskaźniki i tablice to nie to samo. W naszym rozwiązaniu arr jest adresem pamięci pierwszego elementu dwuwymiarowej tablicy automatycznej, która stanowi spójny blok danych w pamięci naszego programu. Właśnie ta ostatnia cecha wpływa na to, że możemy poruszać się po tej tablicy, jak po tablicy jednowymiarowej o wielkości N * M.
Zadanie 13
Napisz funkcję w języku C++, która przyjmie w argumencie liczbę zmiennoprzecinkową i „zwróci” jej wartość całkowitą i ułamkową.
Rozwiązanie:
#include <iostream>
#include <cmath>
void split_number(float number, float &integer_part, float &fractional_part) {
integer_part = std::floor(number);
fractional_part = number - integer_part;
}
int main() {
float integer_part, fractional_part, number = 3.14;
split_number(number, integer_part, fractional_part);
std::cout << "Część całkowita: " << integer_part << std::endl;
std::cout << "Część ułamkowa: " << fractional_part << std::endl;
return 0;
}
Zadanie 14
Napisz funkcję w języku C++, która dostaje jako argument liczbę całkowitą k i zwraca jako wartość największą możliwą liczbę n taką że 2n < k (możliwie najbliższa wartość kolejnej potęgi dwójki)
Przykład:
WE: k = 1100
WY: n = 10, bo 210 (1024) < 1100 i jednocześnie 10 jest największą liczba spełniającą warunek 210<k.
Rozwiązanie:
#include <iostream>
#include <cmath>
int greates_pow_of_two(int k) {
int n = 0;
do ++n; while(pow(2, n) < k);
return n - 1;
}
int main() {
int k = 1100;
std::cout << greates_pow_of_two(k) << std::endl;
return 0;
}
Zadanie 15
Napisz funkcję w języku C++, która przyjmie w argumencie dwie 3-elementowe tablice liczb zmiennoprzecinkowych (interpretowane jako wektory 3d) a zwróci tablicę będącą iloczynem wektorowym wejściowych wektorów.
Rozwiązanie:
#include <iostream>
void cross_product(const float vec_0[], const float vec_1[], float result[]) {
result[0] = vec_0[1] * vec_1[2] - vec_0[2] * vec_1[1];
result[1] = vec_0[2] * vec_1[0] - vec_0[0] * vec_1[2];
result[2] = vec_0[0] * vec_1[1] - vec_0[1] * vec_1[0];
}
int main() {
float vec_0[3] = {1.0, 2.0, 3.0}, vec_1[3] = {4.0, 5.0, 6.0}, result[3] = {};
cross_product(vec_0, vec_1, result);
std::cout << "Wynik iloczynu wektorowego: [" << result[0] << ", " << result[1] << ", " << result[2] << "]" << std::endl;
return 0;
}
Zadanie 16
Napisz funkcję w języku C++, która przyjmie jako argumenty jednowymiarową tablicę liczb całkowitych oraz jej rozmiar. Funkcja powinna zwrócić wartość drugiej co do wielkości liczby w tej tablicy. Zakładamy rozmiar tablicy większy lub równy 2.
Rozwiązanie:
#include <iostream>
int find_second_larges(const int arr[], unsigned int n) {
int largest = arr[0], second_largest = arr[1];
if (second_largest > largest) {
std::swap(largest, second_largest);
}
for (int i = 2; i < n; ++i) {
if (arr[i] > largest) {
second_largest = largest;
largest = arr[i];
} else if (arr[i] > second_largest && arr[i] < largest) {
second_largest = arr[i];
}
}
return second_largest;
}
int main() {
int arr[] = {9, 5, 7, 8, 3, 2, 6, 1, 4};
unsigned int size = sizeof(arr) / sizeof(arr[0]);
int result = find_second_larges(arr, size);
std::cout << "Druga największa wartość w tablicy to: " << result << std::endl;
return 0;
}
Zadanie 17
Napisz funkcję w języku C++, która posortuje przekazaną w argumencie tablicę dowolną metodą. Dodatkowo napisz program, który wykona test jednostkowy tej funkcji, tj. taki, który pobierze ze standardowego wejścia tablicę liczb do posortowania oraz tablicę liczb już posortowanych i na wyjściu zwróci wynik (0 lub 1) porównania z działania funkcji sortującej z wczytaną posortowaną tablicą.
Rozwiązanie:
#include <iostream>
void bubble_sort(int arr[], unsigned 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]);
}
bool compare_arrs(const int arr_0[], const int arr_1[], unsigned int n) {
for (int i = 0; i < n; ++i)
if (arr_0[i] != arr_1[i])
return false;
return true;
}
int main() {
int arr[] = {9, 5, 7, 8, 3, 2, 6, 1, 4};
int sorted_arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
unsigned int size = sizeof(arr) / sizeof(arr[0]);
std::cout << compare_arrs(arr, sorted_arr, size) << std::endl;
bubble_sort(arr, size);
std::cout << compare_arrs(arr, sorted_arr, size) << std::endl;
return 0;
}
Zadanie 18
Napisz funkcję w języku C++ wyświetlającą cyfry, z których składa się liczba całkowita przekazana w argumencie do tej funkcji.
Rozwiązanie:
#include <iostream>
#include <cmath>
void displayigits(int number) {
number = abs(number);
do {
std::cout << number % 10 << " ";
number /= 10;
} while(number);
std::cout << std::endl;
}
int main() {
int number = -12345;
displayigits(number);
return 0;
}
Zadanie 19
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.
Rozwiązanie:
#include <iostream>
void zero_out_of_range(float arr[], unsigned int n, int range_start, int range_end) {
for (unsigned int i = 0; i < n; ++i)
if (arr[i] < range_start || arr[i] > range_end)
arr[i] = 0;
}
void print_arr(float arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
float arr[] = {1.5f, 2.6f, 1.1f, 3.7f, 4.8f, 5.9f}, range_start = 2.f, range_end = 5.f;
int size = sizeof(arr) / sizeof(arr[0]);
zero_out_of_range(arr, size, range_start, range_end);
print_arr(arr, size);
return 0;
}
Zadanie 20
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
Rozwiązanie:
#include <iostream>
void move_zeros_to_end(float arr[], unsigned int n) {
int insert_idx = 0;
for (unsigned int i = 0; i < n; ++i)
if (arr[i] != 0)
arr[insert_idx++] = arr[i];
while (insert_idx < n)
arr[insert_idx++] = 0;
}
void print_arr(float arr[], unsigned int n) {
for (unsigned int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
float arr[] = {0.f, 5.f, 3.f, 7.f, 6.f, 0.f, 0.f, 3.f, 1.f, 2.f, 6.f, 0.f, 4.f, 1.f, 2.f};
unsigned int size = sizeof(arr) / sizeof(arr[0]);
print_arr(arr, size);
move_zeros_to_end(arr, size);
print_arr(arr, size);
return 0;
}
Zadanie 21
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ść logiczną informującą, czy warunek został spełniony.
Rozwiązanie:
#include <iostream>
bool check_condition(int arr[][10], unsigned int n) {
for (unsigned int i = 0; i < n - 1; ++i) {
int sum_0 = 0, sum_1 = 0;
for (unsigned int j = 0; j < 10; ++j) {
sum_0 += arr[i][j];
sum_1 += arr[i + 1][j];
}
if (sum_0 >= sum_1) return false;
}
return true;
}
int main() {
int arr[3][10] = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
{11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
{21, 22, 23, 24, 25, 26, 27, 28, 29, 30}};
unsigned int n = 3;
std::cout << (check_condition(arr, n) ? "Warunek został spełniony." : "Warunek nie został spełniony.") << std::endl;
return 0;
}
Zadanie 22
Zmodyfikuj poprzednie zadanie tak, żeby funkcja przyjmowała w argumencie macierz w postaci tablicy jednowymiarowej, w której są zapisane kolejno po sobie wiersze tej macierzy. Dodatkowo funkcja ma dostać jeszcze liczbę wierszy i kolumn tej macierzy w argumentach.
Rozwiązanie:
#include <iostream>
bool check_condition(int arr[], unsigned int n, unsigned int m) {
for (unsigned int i = 0; i < n - 1; ++i) {
int sum_0 = 0, sum_1 = 0;
for (unsigned int j = 0; j < 10; ++j) {
sum_0 += arr[i * m + j];
sum_1 += arr[(i + 1) * m + j];
}
if (sum_0 >= sum_1) return false;
}
return true;
}
int main() {
unsigned int n = 3, m = 10;
int arr[n * m] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
std::cout << (check_condition(arr, n, m) ? "Warunek został spełniony." : "Warunek nie został spełniony.") << std::endl;
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 program w języku C++, który pobierze ze standardowego wejścia napis, zapisze go w tablicy znaków, a następnie wyświetli.
Zadanie 2
Napisz program w języku C++, który napis w tablicy znaków wyświetli w taki sposób, że każde słowo (ciąg znaków oddzielony spacją) będzie wyświetlone w nowej linii.
Zadanie 3
Zmodyfikuj poprzednie zadanie tak, aby pierwszy znak w każdym słowie, jeżeli jest literą, został wyświetlony z użyciem wielkiej litery.
Zadanie 4
Napisz program w języku C++ sprawdzający, czy liczba wczytana od użytkownika jest potęgą dwójki. Program powinien wyświetlić 1, jeśli liczba jest potęgą dwójki lub 0 w przeciwnym wypadku. Wykorzystaj do tego operacje bitowe.
Zadanie 5
Napisz program w języku C++, który wczyta dwie całkowite wartości określające początek i koniec obustronnie domkniętego przedziału, a następnie wyświetli wszystkie liczby pierwsze w tym przedziale.
