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
charzakoń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
1wię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 = 1an = 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;
}
