PP – Laboratorium 6

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>
using namespace std;

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] -= 32;

    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ści 0.
  • 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=%d B=%d", &a, &b);
    printf("%d\n%d\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 powielenie najstarszego bitu na skrajnej lewej pozycji.

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] - 48);
    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;
}

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *