Wejściówka
Napisz program w języku C++, który stworzy dwuwymiarową tablicę (NxM) w postaci tablicy wskaźników do tablicy wartości liczb całkowitych. Napisz funkcję f1, która wypełni tą tablicę dowolnymi wartościami.
Rozwiązanie:
#include <iostream>
void f1(int **arr, int n, int m) {
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
arr[i][j] = i * j;
}
int main() {
int n, m;
std::cin >> n >> m;
int **arr = new int*[n];
for(int i = 0; i < n; ++i)
arr[i] = new int[m];
f1(arr, n, m);
for(int i = 0; i < n; ++i)
delete[] arr[i];
delete[] arr;
return 0;
}
Zadanie 1
Napisz program w języku C++, który za pomocą wskaźnika do funkcji wywoła dwie funkcje: add i sub. Funkcja add powinna dodawać dwie liczby, zaś funkcja sub odejmować dwie liczby. Zaimplementowany program powinien sprawdzić poprawność działania tych funkcji.
Rozwiązanie:
#include <iostream>
int add(int a, int b) {
return a + b;
}
int sub(int a, int b) {
return a - b;
}
int main() {
int (*fun)(int, int);
fun = add;
std::cout << fun(10, 2) << std::endl;
fun = sub;
std::cout << fun(10, 2) << std::endl;
return 0;
}
Omówienie:
Dotychczas zajmowaliśmy się sytuacją, gdy wskaźnik wskazywał na jakąś zmienną. Jednak nie tylko zmienna ma swój adres w pamięci. Oprócz zmiennej także i funkcja musi mieć swoje określone miejsce w pamięci. Z tego względu nie ma przeszkód, aby i na nią wskazywał jakiś wskaźnik.
Kod maszynowy utworzony po skompilowaniu programu odnosi się właśnie do adresu funkcji. Wskaźnik na funkcję różni się od innych rodzajów wskaźników.
Jedną z głównych różnic jest jego deklaracja. Zwykle wygląda ona następująco:typ_zwracanej_wartości (*nazwa_wskaźnika)(typ1 argument1, typ2 argument2);
Należy zwrócić uwagę na dwie rzeczy:
– przypisując nazwę funkcji bez nawiasów do wskaźnika, automatycznie informujemy kompilator, że chodzi nam o adres funkcji,
– wskaźnika używamy tak, jak normalnej funkcji, na którą on wskazuje.
Zadanie 2
Napisz program w języku C++, który wczyta od użytkownika dwie liczby zmiennoprzecinkowe a i b, a następnie nieujemną liczbę całkowitą o. Program, w zależności od podanej nieujemnej liczby całkowitej, powinien wyświetlić wynik odpowiedniego działania:0 – dodawanie,1 – odejmowanie,2 – mnożenie,3 – dzielenie.
Do rozwiązania zadania wykorzystaj wskaźniki na funkcje.
Rozwiązanie:
#include <iostream>
float add(float a, float b) {
return a + b;
}
float sub(float a, float b) {
return a - b;
}
float mul(float a, float b) {
return a * b;
}
float div(float a, float b) {
return a / b;
}
int main() {
unsigned int o;
float a, b;
float (*f_ptr[4])(float, float) = {add, sub, mul, div}; // tablica wskaźników na funkcje
std::cin >> a >> b >> o;
std::cout << f_ptr[o](a, b) << std::endl;
return 0;
}
Zadanie 3
Wykorzystując wskaźniki na funkcje napisz program w języku C++, który w zależności od wywołania funkcji f znajdzie w tablicy liczb całkowitych wartość minimalną lub maksymalną.
Rozwiązanie:
#include <iostream>
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
int f(int arr[], int n, int (*fun)(int,int)) {
int ex = arr[0];
for(int i = 1; i < n; ++i)
ex = fun(ex, arr[i]);
return ex;
}
int main() {
int arr[] = {1, 2, 3, 5, 15, 0, 12, 13, 5, 7};
std::cout << f(arr, 10, min) << std::endl;
std::cout << f(arr, 10, max) << std::endl;
return 0;
}
Omówienie:
int f(int arr[], int n, int (*fun)(int,int)) //można zamienić na: typedef int (*p_fun)(int, int); int f(int arr[], int n, p_fun fun)
Zadanie 4
Napisz program w języku C++, który posortuje tablicę dowolnych liczb rzeczywistych arr1 malejąco oraz tablicę dowolnych liczb całkowitych arr2 rosnąco. Do sortowania wykorzystaj algorytm Quick Sort z pliku nagłówkowego cstdlib.
Rozwiązanie:
#include <cstdlib>
#include <iostream>
int min(const void *a, const void *b) {
float av = *(float *)a;
float bv = *(float *)b;
if(av > bv) return -1;
else if(av == bv) return 0;
else return 1;
//lub
//return *(float*)b - *(float*)a < 0 ? -1 : 1;
//powyższy zapis wynika z konwersji liczb zmiennoprzecinkowych na liczbę całkowitą np. float 0.2 -> int 0 itd.
}
int max(const void *a, const void *b) {
int av = *(int *)a;
int bv = *(int *)b;
if(av < bv) return -1;
else if(av == bv) return 0;
else return 1;
//lub
//return *(int*)a - *(int*)b;
}
int main() {
float arr1[] = {1.f, 2.f, 3.f, 5.f, 15.f, 0.f, 12.f, 13.f, 5.f, 7.f};
int arr2[] = {1, 2, 3, 5, 15, 0, 12, 13, 5, 7};
qsort(arr1, 10, sizeof(float), min);
for(int i = 0; i < 10; ++i)
std::cout << arr1[i] << " ";
std::cout << "\n";
qsort(arr2, 10, sizeof(int), max);
for(int i = 0; i < 10; ++i)
std::cout << arr2[i] << " ";
std::cout << "\n";
return 0;
}
Zadanie 5
Napisz program w języku C++, który posortuje malejąco tablicę napisów za pomocą funkcji qsort.
Rozwiązanie:
#include <cstdlib>
#include <iostream>
#include <cstring>
int str_cmp(char str_0[], char str_1[]) {
unsigned int i = 0;
while(str_0[i] && (str_0[i] == str_1[i])) ++i;
return str_0[i] - str_1[i];
}
int compar(const void *p1, const void *p2) {
return -str_cmp((char *)p1, (char *)p2);
//return -strcmp((const char *)p1, (const char *)p2); - jeżeli korzystamy z pliku nagłówkowego cstring
}
int main() {
char arr[5][100] = {
"tygrys syberyjski",
"krokodyl nilowy",
"panda wielka",
"tygrys azjatycki",
"chomik europejski"
};
qsort(arr, 5, 100, compar);
for(int i = 0; i < 5; ++i)
std::cout << arr[i] << std::endl;
return 0;
}
Zadanie 6
Napisz program w języku C++, który wczyta od użytkownika liczbę, jako napis. Liczba powinna mieć co najwyżej 10 cyfr. Następnie program powinien zwiększyć tą liczbę o 10 i ją wyświetlić.
Rozwiązanie:
#include <cstdio>
#include <cstdlib>
#include <iostream>
int main() {
char str[11] = {0}, *ptr = nullptr;
scanf("%10s", str);
int value = strtol(str, &ptr, 10) + 10;
std::cout << std::to_string(value) << std::endl;
return 0;
}
Zadanie 7
Zaprojektuj funkcję w języku C++, która zwróci indeks szukanej wartości w posortowanej tablicy liczb całkowitych. Funkcja powinna zwrócić -1, jeśli nie uda się znaleźć takiej wartości w tablicy. Rozwiązanie powinno wykorzystywać algorytm Binary Search. Napisz program w języku C++, który przetestuje działanie tej funkcji.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
int binarySearch(int *arr, int l, int r, int x) {
int mid = (l + r) / 2;
if(mid <= r && mid >= l) {
if(arr[mid] == x) return mid;
else if(arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
else return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int compare(const void *ap, const void *bp) {
return *(int*)ap - *(int*)bp;
}
int main() {
int arr[] = {1, 2, 3, 4, 10, 22, 23, 42};
int x = 4;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
int *p = (int *) bsearch(&x, arr, n, sizeof(arr[0]), compare);
std::cout << (result == -1 ? "Brak" : std::to_string(result)) << std::endl;
std::cout << (p ? std::to_string(p - arr) : "Brak") << std::endl;
return 0;
}
Zadanie 8
Napisz funkcję w języku C++, która przyjmuje w argumencie tablicę liczb całkowitych (wskaźnik na kwadratową macierz) oraz jej rozmiar N. Funkcja powinna wypełnić przekazaną w argumencie macierz tabliczką mnożenia. Macierz jest spójnym obszarem pamięci.
Rozwiązanie:
#include <iostream>
void fill_matrix(int *matrix, int n) {
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
matrix[i * n + j] = (i + 1) * (j + 1);
}
void print_matrix(int *matrix, int n) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
std::cout << matrix[i * n + j] << " ";
std::cout << "\n";
}
}
int main() {
int n = 10;
int *arr = new int[n * n];
fill_matrix(arr, n);
print_matrix(arr, n);
delete[] arr;
return 0;
}
Zadanie 9
Napisz funkcję w języku C++, która otrzymuje w argumencie jednowymiarową tablicę liczb zmiennoprzecinkowych, dwie liczby całkowite będące wymiarami obszaru reprezentowanego przez tablicę podaną w pierwszym argumencie. Funkcja powinna wypełnić krawędzie obszaru zerami, a następnie zwrócić dwuwymiarową tablicę z tak zmodyfikowanymi danymi. Napisz program w języku C++, który sprawdzi działanie tej funkcji.
Rozwiązanie:
#include <iostream>
void f(float *arr, int n, int m, float **result) {
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(i == 0 || j == 0 || i == n - 1 || j == m - 1)
result[i][j] = 0.f;
else
result[i][j] = arr[i * m + j];
}
void print_arr(float **arr, int n, int m) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j)
std::cout << arr[i][j] << " ";
std::cout << "\n";
}
}
int main() {
const int n = 3, m = 5;
float arr[n * m] = {1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f, 1.f};
float **result = new float*[n];
for(int i = 0; i < n; ++i)
result[i] = new float[m];
f(arr, n, m, result);
print_arr(result, n, m);
for(int i = 0; i < n; ++i)
delete[] result[i];
delete[] result;
return 0;
}
Zadanie 10
Napisz program w języku C++, który wczyta od użytkownika dwie liczby całkowite n i x, a następnie stworzy dwie n-elementowe tablice liczb całkowitych. Następnie program powinien uzupełnić tablicę kolejnymi wartościami zaczynając od x i ustawić te wartości w losowej kolejności (wymieszać). Na koniec program powinien wyświetlić obie tablicę, sumę wartości w tablicach oraz wynik iloczynu skalarnego dwóch tak zdefiniowanych wektorów. Spróbuj rozwiązać zadanie wykorzystując głównie algorytmy i funkcje biblioteczne np. iota z pliku nagłówkowego numeric.
Rozwiązanie:
#include <iostream>
#include <numeric>
#include <algorithm>
void print_arr(int *b, int *e) {
for(int *i = b; i < e; ++i)
std::cout << *i << " ";
std::cout << "\n";
}
int main() {
int n, x, init = 0, *t1 = nullptr, *t2 = nullptr;
std::cin >> n >> x;
t1 = new int[n];
t2 = new int[n];
std::iota(t1, t1 + n, x);
std::iota(t2, t2 + n, x);
std::random_shuffle(t1, t1 + n);
std::random_shuffle(t2, t2 + n);
print_arr(t1, t1 + n);
print_arr(t2, t2 + n);
std::cout << std::accumulate(t1, t1 + n, init) << std::endl;
std::cout << std::inner_product(t1, t1 + n, t2, init) << std::endl;
delete[] t1;
delete[] t2;
return 0;
}
Zadanie 11
Napisz program w języku C++, który wczyta od użytkownika maksymalnie 100 znakowe słowo. Następnie program powinien stworzyć odwrócony odpowiednik napisu wprowadzonego przez użytkownika za pomocą arytmetyki wskaźników.
Rozwiązanie:
#include <cstdio>
#define MAX_SIZE 100
int main() {
char str[MAX_SIZE + 1] = {0}, reverse[MAX_SIZE + 1] = {0};
char *s = str;
char *r = reverse;
scanf("%100s", str);
int len = 0;
while(*(s++)) len++;
s--;
while(len >= 0) {
*(r++) = *(--s);
len--;
}
*r = '\0';
printf("Original: %s\n", str);
printf("Reverse: %s\n", reverse);
return 0;
}
Omówienie:
Ciekawy przykład arytmetyki na wskaźnikach:
#include <iostream>
using namespace std;
int main()
{
int num[5];
int* p;
p = num;
*p = 10;
p++;
*p = 20;
p = &num[2];
*p = 30;
p = num + 3;
*p = 40;
p = num;
*(p + 4) = 50;
for (int i = 0; i < 5; i++)
cout << num[i] << ", ";
return 0;
}
Zadanie 12
Wykorzystaj funkcję qsort do posortowania tablicy liczb całkowitych rosnąco pod względem liczebności cyfry 0 w liczbach.
Rozwiązanie:
#include <iostream>
#include <cstdlib>
int num_zeros(int value) {
int result = 0;
do if(!(value % 10)) ++result; while(value /= 10);
return result;
}
int cmp_num_zeros(const void *a, const void *b) {
return num_zeros(*(int *)a) - num_zeros(*(int *)b);
}
void print_arr(int *arr, int n) {
for(int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\n";
}
int main() {
const int n = 6;
int arr[n] = {10, 1000, 1010, 100000, 101010, 100};
print_arr(arr, n);
qsort(arr, n, sizeof(arr[0]), cmp_num_zeros);
print_arr(arr, n);
return 0;
}
Zadanie 13
Zmodyfikuj poprzednie rozwiązanie tak, aby wykorzystało funkcję std::sort. Użyj jej zamiast qsort.
Rozwiązanie:
#include <iostream>
#include <algorithm>
int num_zeros(int value) {
int result = 0;
do if(!(value % 10)) ++result; while(value /= 10);
return result;
}
bool cmp_num_zeros(int &a, int &b) {
return num_zeros(a) < num_zeros(b);
}
void print_arr(int *arr, int n) {
for(int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << "\n";
}
int main() {
const int n = 6;
int arr[n] = {10, 1000, 1010, 100000, 101010, 100};
print_arr(arr, n);
std::sort(arr, arr + n, cmp_num_zeros);
print_arr(arr, n);
return 0;
}
Zadanie 14
Napisz funkcję w języku C++, która przyjmie dwa parametry liczbę całkowitą x oraz liczbę całkowitą d, w której zapisana będzie cyfra. Funkcja powinna zwrócić liczbę wystąpień cyfry d w liczbie x. W implementacji tej funkcji nie używaj pętli.
Rozwiązanie:
#include <iostream>
int count_occurrences_of_digit(int x, int d) {
if(!x) return 0;
int tmp = 0;
if(x % 10 == d) tmp = 1;
return count_occurrences_of_digit(x / 10, d) + tmp;
}
int main() {
int x = 156113, d = 1;
std::cout << count_occurrences_of_digit(x, d) << 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 stworzy n-elementową tablicę liczb całkowitych, a następnie wypełni tę tablicę dowolną wartością wykorzystując funkcję fill z biblioteki
Zadanie 2
Napisz funkcję w języku C++, która przyjmuje wskaźnik na void oraz liczbę całkowitą ptrsize. ptrsize jest liczbą bajtów, która reprezentuje zmienną. Funkcja powinna odpowiednio zrzutować zmienną i wyświetlić jej wartość (obsłuż typ char oraz int).
Zadanie 3
Zapoznaj się z innymi algorytmami znajdującymi się w bibliotece find, generate, transform, etc).
