Wejściówka – rekurencja
Napisz funkcję rekurencyjną w języku C++, która dla otrzymanej w argumencie nieujemnej liczby całkowitej k
oraz liczby rzeczywistej x
zwraca wartość elementu o indeksie k
ciągu zdefiniowanego w następujący sposób:T0(x) = 1
T1(x) = x
Tk(x) = 2 * T(k-1)(x) - T(k-2)(x)
Rozwiązanie:
float f(unsigned int k, float x) { if(k == 0) return 1; else if(k == 1) return x; else return 2 * x * f(k - 1, x) - f(k - 2, x); }
Zadanie 1
Napisz funkcję w języku C++, która przyjmie jako argument dwuwymiarową tablicę liczb zmiennoprzecinkowych oraz jej wymiary.
Funkcja powinna tak zmodyfikować tą tablicę, aby w każdym polu znalazła się średnia arytmetyczna wartości w nim samym oraz polach sąsiednich: górnym, dolnym, lewym i prawym. Jeżeli pole znajduje się na krawędzi tablicy, należy policzyć średnią z mniejszej liczby sąsiadów. Napisz program, który przetestuje działanie tej funkcji, wypełniając tablicę losowymi wartościami.
Rozwiązanie:
#include <cstdio> #include <cstdlib> #include <ctime> const int N = 10; const int M = 10; void avg(float arr[][M], float tmp[][M], int n, int m) { int count; float sum; for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) { sum = arr[i][j]; count = 1; if(i > 0) sum += arr[i - 1][j], count++; if(i < n - 1) sum += arr[i + 1][j], count++; if(j > 0) sum += arr[i][j - 1], count++; if(j < m - 1) sum += arr[i][j + 1], count++; tmp[i][j] = sum / count; } for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) arr[i][j] = tmp[i][j]; } void print_arr(float arr[][M], int n, int m) { for(int i = 0 ; i < N; ++i) { for(int j = 0; j < M; ++j) printf("%5.1f", arr[i][j]); printf("\n"); } printf("\n"); } void init_arr(float arr[][M], int n, int m) { for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) arr[i][j] = rand() % 100; } int main() { srand(time(0)); float arr[N][M]; float tmp[N][M]; init_arr(arr, N, M); print_arr(arr, N, M); avg(arr, tmp, N, M); print_arr(arr, N, M); return 0; }
Zadanie 2 – tablica znaków
Napisz program w języku C++, który zmieni wszystkie małe litery wczytanego napisu na wielkie. Załóż, że napis nie może mieć więcej niż 100
znaków.
Rozwiązanie:
#include <cstdio> int main(){ char str[101]; scanf("%100s", str); //Wczytywanie bez białych znaków. for(int i = 0; str[i]; ++i) if(str[i] >= 'a' && str[i] <= 'z') str[i] += 'A' - 'a'; printf("%s\n", str); return 0; }
Omówienie:
Na razie do obsługi napisów nie będziemy wykorzystywać specjalnej struktury, a zwykłą tablicę znaków (tablicę typu char
):
- Do tego celu stosowane są tablice typu
char
zakończone znakiem końca napisu'\0'
.char napis1[5] = {'a','d','a','m','\0'};
char napis2[] = "Ala ma kota"; /*Tablica 12-elementowa, bo ostatni znak to '\0'. */
- Znak
'\0'
jest niedrukowalnym znakiem ASCII o wartości0
. - Znak
'\0'
określa miejsce zakończenia napisu. - Tablica znakowa musi mieć rozmiar co najmniej o
1
większy niż ilość znaków.
Porównanie napisu i pojedynczego znaku:char x = 'a'; //apostrof
char x[] = "a"; //cudzysłów
Zadanie 3
Napisz program w języku C++, który wczyta od użytkownika dwie wartości całkowite a
i b
. Program powinien obliczyć wynik następującego równania: sqrt(a / b^5)
, jeśli użytkownik wprowadził wartości mniejsze od zera należy zwrócić odpowiedni komunikat, a dla b = 0
wartość NAN
.
Rozwiązanie:
#include <iostream> #include <cmath> int main() { int a, b; std::cin >> a >> b; if(a < 0 || b < 0) std::cout << "Niepoprawne dane wejsciowe.\n"; else std::cout << (b == 0 ? NAN : sqrt(a / pow(b, 5))) << std::endl; return 0; }
Zadanie 4 – operacje bitowe
Napisz program w języku C++, który sprawdzi parzystość liczby wczytanej od użytkownika. Program powinien wyświetlić 1
, jeśli liczba jest parzysta lub 0
w przeciwnym wypadku.
Rozwiązanie:
#include <iostream> using namespace std; int main() { int n; cin >> n; cout << !(n & 1); return 0; }
Omówienie:
Język C++ został wyposażony także w operatory bitowe, zdefiniowane dla liczb całkowitych. Są to:
~
negacja bitowa (NOT),&
koniunkcja bitowa (AND),|
alternatywa bitowa (OR),^
alternatywa rozłączna (XOR).
Działają one na poszczególnych bitach przez co mogą być szybsze od innych operacji. Działanie tych operatorów można zdefiniować za pomocą poniższych tabel:
"~" | a "&" | a | b "|" | a | b "^" | a | b ----+--- ----+---+--- ----+---+--- ----+---+--- 0 | 1 0 | 0 | 0 0 | 0 | 0 0 | 0 | 0 1 | 0 0 | 1 | 0 1 | 1 | 0 1 | 1 | 0 0 | 0 | 1 1 | 0 | 1 1 | 0 | 1 1 | 1 | 1 1 | 1 | 1 0 | 1 | 1
Przykład:
a | 0101 = 5 b | 0011 = 3 ------+------ ~a | 1010 = 10 ~b | 1100 = 12 a & b | 0001 = 1 a | b | 0111 = 7 a ^ b | 0110 = 6
Przy okazji warto zauważyć, że a ^ b ^ b
to po prostu a
. Właściwość ta została wykorzystana w różnych algorytmach szyfrowania oraz funkcjach haszujących. Alternatywę wyłączną stosuje się np. do szyfrowania kodu wirusów polimorficznych.
Zadanie 5
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.
Rozwiązanie:
#include <iostream> using namespace std; int main() { int n; cin >> n; cout << !(n & (n-1)); return 0; }
Zadanie 6 – przesunięcia bitowe
Napisz program w języku C++, który wczytuje od użytkownika dwie liczby całkowite bez znaku a
i b
w formacie A=a B=b
. Program powinien wypisać wartość liczby a
po przesunięciu bitowym w lewo i w prawo o b
w dwóch oddzielnych liniach. Użyj tylko jednego wywołania funkcji printf
.
Rozwiązanie:
#include <cstdio> int main() { unsigned int a, b; scanf("A=%u B=%u", &a, &b); printf("%u\n%u\n", a<<b, a>>b); return 0; }
Omówienie:
Dodatkowo, język C/C++ wyposażony jest w operatory przesunięcia bitowego w lewo <<
i prawo >>
. Przesuwają one w danym kierunku bity lewego argumentu o liczbę pozycji podaną jako prawy argument. Brzmi to może strasznie, ale wcale takie nie jest. Rozważmy operacje przesunięcia na liczbach 4-bitowych (bez znaku):
a | a<<1 | a>>2 | a>>1 | a>>2 -----+------+------+------+------ 0001 | 0010 | 0100 | 0000 | 0000 0011 | 0110 | 1100 | 0001 | 0000 0101 | 1010 | 0100 | 0010 | 0001 1000 | 0000 | 0000 | 0100 | 0010 1111 | 1110 | 1100 | 0111 | 0011 1001 | 0010 | 0100 | 0100 | 0010
Operacje przesunięcia bitowego w języku C/C++ są zdefiniowane dla liczb całkowitych (bez znaku) i są odpowiednikiem mnożenia i dzielenia całkowitego przez wartość 2n. Przesunięcie w lewą stronę oznacza przemieszczenie wszystkich bitów argumentu w lewo o określoną liczbę miejsc oraz wprowadzenie z prawej strony takiej samej ilości zer. Przesunięcie w prawo oznacza przemieszczenie wszystkich bitów argumentu w prawo o określoną liczbę miejsc oraz wprowadzenie z lewej strony takiej samej ilości zer.
Operacje przesunięcia bitowego dla liczb całkowitych ze znakiem są zdefiniowane w następujący sposób: (1) dla liczby dodatniej przesunięcie w prawo działa na wszystkich bitach poza najstarszym bitem znaku, (2) dla liczby dodatniej przesunięcie w lewo jest częściowo zależne od bitów tej liczby a częściowo niezdefiniowane, (3) dla liczby ujemnej przesunięcie w prawo jest zależne od implementacji, (4) dla liczby ujemnej standard C++ nie definiuje przesunięcia w lewo.
Zadanie 7
Napisz funkcję w języku C++, która przyjmuje jako argumenty napis będący liczbą binarną, liczbę całkowitą bez znaku. W rezultacie funkcja powinna zwrócić sumę liczb całkowitych podanych w pierwszym i drugim argumencie. Zaimplementuj odpowiednie funkcję oraz program, który przetestuje ich działanie.
Rozwiązanie:
#include <iostream> using namespace std; unsigned int bin_to_int_it(char str[]) { unsigned int num = 0; for(int i = 0; str[i]; ++i) num = (num << 1) | (str[i] - '0'); return num; } int f(char value1[], unsigned int value2) { return bin_to_int_it(value1) + value2; } int main() { char str[] = "1111011"; //char str[8] = {'1', '1', '1', '1', '0', '1', '1', '\0'}; cout << f(str, 123) << endl; return 0; }
Zadanie 8
Napisz program w języku C++, który zamienia wartościami dwie zmienne całkowite i nie używa do tego dodatkowej zmiennej. Wykorzystaj do tego operacje bitowe.
Rozwiązanie:
#include <iostream> using namespace std; int main () { int a, b; cin >> a >> b; cout << "a = " << a << "\tb = " << b << endl; a ^= b; b ^= a; a ^= b; cout << "a = " << a << "\tb = " << b << endl; return 0; }
Zadanie 9
Napisz program w języku C++, który poda wartość bezwzględną liczby całkowitej wczytanej od użytkownika nie używając instrukcji sterujących oraz zewnętrznych bibliotek.
Rozwiązanie:
#include <cstdio> int main () { int a, mask; scanf("%d", &a); mask = a >> sizeof(int) * 8 - 1; printf("%u\n", (a + mask) ^ mask); return 0; }
Zadanie 10
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.
Rozwiązanie:
#include <iostream> using namespace std; int main() { int a, b; bool isPrime; cin >> a >> b; for(int v = a; v <= b; ++v) { isPrime = true; for(int i = 2; i < v; ++i) if(!(v % i)) { isPrime = false; break; } if(isPrime) cout << v << endl; } return 0; }
Zadanie 11
Napisz funkcję w języku C++, która przyjmuje jako argumenty 10
-elementową automatyczną tablicę liczb rzeczywistych oraz jej rozmiar. Funkcja powinna zwrócić true
, jeśli tablica czytana od końca wygląda tak samo, ta tablica czytana od początku, bądź false
w przeciwnym wypadku. Napisz program w języku C++, który przetestuje działanie tej funkcji, wczytując od użytkownika 10
wartości wprowadzonych do tablicy.
Rozwiązanie:
#include <iostream> #include <cmath> using namespace std; bool f(float arr[], int n) { for(int i = 0; i < ceil(n / 2); ++i) if(arr[i] != arr[n - i - 1]) return false; return true; } int main() { const int n = 10; float arr[n]; for(int i = 0; i < n; ++i) cin >> arr[i]; cout << f(arr, n); return 0; }
Zadanie 12
Napisz funkcję w języku C++, która dla otrzymanej w argumencie nieujemnej liczby całkowitej n zwróci kolejne wyrazy ciągu zdefiniowanego w następujący sposób:
a0 = a1 = 1
an = a(n−1) + 2 * a(n−2) + 3 dla n > 1.
Dodatkowo zaimplementuj rozwiązania rekurencyjne i optymalne rozwiązanie rekurencyjne, które obliczy n
-ty wyraz tego ciągu.
Rozwiązanie:
typedef unsigned int uint; int f_rec(uint n) { return (n == 0 || n == 1) ? 1 : f_rec(n - 1) + 2 * f_rec(n - 2) + 3; } int f_tail_rec(uint a, uint b, uint n) { //1, 1, 5 return n == 1 ? b : f_tail_rec(b, b + 2 * a + 3, n - 1); } int f_it(uint n) { int a, b, c; a = b = 1; while(n-- >= 1) { c = b + 2 * a + 3; a = b; b = c; } return a; }
Zadanie 13
Napisz program w języku C++, który stworzy 15
elementową tablicę dowolnych wartości rzeczywistych. Następnie program, który wczyta od użytkownika 5
liczb całkowitych, będących indeksami wcześniej stworzonej tablicy. Program powinien wyświetlić elementy tablicy o wskazanych przez użytkownika indeksach i zapewnić odpowiedni komunikat, jeśli indeks wykracza poza rozmiar tablicy. Zastanów się nad bardziej uniwersalnym rozwiązaniem takiego zadania.
Rozwiązanie:
//Version 1.0 #include <iostream> using namespace std; int main() { float arr[15] = {1.f, 2.f, 3.f, 4.f, 5.f, 6.f, 7.f, 8.f, 9.f, 10.f, 11.f, 12.f, 13.f, 14.f, 15.f}; int k = 5; int temp; while(k--) { cin >> temp; if(temp >= 0 && temp < 15) cout << arr[temp] << endl; //printf("%f\n", temp >= 0 && temp < n ? arr[temp] : 0.f); else cout << "Poza zakresem." << endl; } return 0; }
//Version 2.0 #include <iostream> using namespace std; void f(float values[], int n_v, int ids[], int n_i) { for(int i = 0; i < n_i; ++i) cout << (ids[i] >= 0 && ids[i] < n_v ? values[ids[i]] : 0.f) << endl; } int main() { const int k = 5, n = 15; float arr[15] = {1.f, 2.f, 3.f, 4.f, 5.f, 6.f, 7.f, 8.f, 9.f, 10.f, 11.f, 12.f, 13.f, 14.f, 15.f}; int ids[k]; for(int i = 0; i < k; ++i) cin >> ids[i]; f(arr, n, ids, k); return 0; }
Zadanie 14
Zadeklaruj funkcję w języku C++, która przyjmuje w argumencie automatyczną tablicę liczb całkowitych, jej rozmiar jako wartość całkowita bez znaku oraz zmienną typu bool
. Funkcja powinna zwrócić wartość pierwszego powtarzający się element w tablicy, tylko wtedy gdy wartość zmiennej typu bool
ma wartość logiczną true
. Jeśli tablica składa się tylko z unikalnych wartości to funkcja powinna zwrócić 0
.
Rozwiązanie:
int f(int arr[], unsigned int n, bool unique);
Zadanie 15
Napisz funkcję rekurencyjną w języku C++, która dla otrzymanej w argumencie nieujemnej liczby całkowitej n
zwraca wartość elementu o indeksie n
ciągu zdefiniowanego w następujący sposób:a0 = a1 = 1
an = a(n-1) + n
dla n
parzystych,an = a(n-1) * n
dla n
nieparzystych.
Rozwiązanie:
int a(int n) { if(n == 0 || n == 1) return 1; if(n % 2 == 0) return a(n-1)+n; else return a(n-1)*n; }
Zadanie 16
Pewna obojnacza populacja rozwija się w taki sposób, że na wiosnę wszystkie osobniki łączą się w pary, a każda para ma jedno młode. W lecie liczebność nie zmienia się. Przez jesień populacja pozbywa się dziesięciu najsłabszych osobników. Zimę przeżywa 60%
populacji. Napisz funkcję rekurencyjną w języku C++, która przyjmie początkową liczebność populacji oraz rok i porę roku (wiosna – 0
, …, zima – 3
) sprawdzenia jej wielkości. Funkcja powinna zwrócić liczebność populacji w podanym roku, po zakończeniu podanej pory roku. Zakładamy, że początkowa liczebność jest odczytana w roku 0
, na początku wiosny. Jeżeli pośrednim lub ostatecznym wynikiem będzie liczba niecałkowita, zaokrąglamy wynik na niekorzyść populacji. Dodatkowo napisz program w języku C++, który sprawdzi działanie funkcji.
Rozwiązanie:
#include <cstdio> int pop(int initCount, int year, int season){ int n; if(year == 0 && season == 0) return initCount; if(season == 0) n = pop(initCount, year - 1, 3); else n = pop(initCount, year, season-1); if(n == 0) return 0; switch (season){ case 0: return n * 1.5; case 1: return n; case 2: return n > 10 ? n - 10 : 0; case 3: return n * 0.6; default: return 0; } } int main(){ int initCount = 1000, year = 5, season = 2; printf("%d",pop(initCount, year, season)); return 0; }
Zadanie 17
Napisz program w języku C++, rysujący trójkąt ze znaków.
Rozwiązanie:
#include <cstdio> int main() { int n; scanf("%d", &n); for(int i = 0; i < n; ++i) { for(int j = 1; j <= n - i; ++j) printf(" "); for(int j = 1; j <= 2 * i - 1; ++j) printf("*"); printf("\n"); } return 0; }
Zadanie 18
Napisz funkcję w języku C++, która generuje szum Gaussowski. Funkcja powinna przyjmować dwie liczby rzeczywiste mean
(średnią) i sigma
(wariancję). Użyj metody polarnej Marsaglia.
Rozwiązanie:
#include <cstdlib> #include <cmath> using namespace std; static const double two_pi = 2.0 * M_PI; double generate_gaussian_noise(double mean, double sigma) { double z, u1, u2; do { u1 = rand() * (1.0 / RAND_MAX); u2 = rand() * (1.0 / RAND_MAX); z = u1 * u1 + u2 * u2; } while (z >= 1 || z == 0); z = sqrt(-2.0 * log(z)) / z; return u1 * z * sigma + mean; }
Zadanie 19
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.
Rozwiązanie:
#include <cstdio> int main(){ char str[] = "Ala ma kota."; for(int i = 0; str[i]; ++i) if(str[i] == ' ') printf("\n"); else printf("%c", str[i]); return 0; }
Zadanie 20
Zmodyfikuj poprzednie zadanie tak, aby pierwszy znak w każdym słowie, jeżeli jest literą, został wyświetlony z użyciem wielkiej litery.
Rzowiązanie:
#include <cstdio> int main(){ char str[] = "Ala ma kota."; for(int i = 0; str[i]; ++i) if(str[i] == ' ') { printf("\n"); if(str[i + 1] >= 'a' && str[i + 1] <= 'z') str[i + 1] -= 32; } else printf("%c", str[i]); return 0; }