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
Jeżeli chcielibyśmy wczytać napis wraz z białymi znakami możemy użyć innej metody np. fgets():
fgets(str, 101, stdin); // Wczytuje do 100 znaków, w tym białe znaki
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. Operacje bitowe są stosowane na poziomie bitów, co oznacza, że operują bezpośrednio na binarnych reprezentacjach liczb. Są szybkie i efektywne, zwłaszcza w sytuacjach, gdzie konieczne jest manipulowanie poszczególnymi bitami liczb całkowitych. W języku C++ mamy kilka operatorów bitowych, które mogą być bardzo przydatne w różnych algorytmach:
~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.
Wskazówka: Czasami chcemy ustawić więcej niż jeden bit, lub zrobić operację na większej grupie bitów. W takich sytuacjach może przydać się nam wprowadzony na pierwszych zajęciach zapis szesnastkowy liczb całkowitych.
unsigned int a = 0x0f; //00001111b, 15
unsigned int b = 0xf0f0; //1111000011110000b, 61680
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;
}
Zadanie 21
Napisz program w języku C++, który wczyta ze standardowego wejścia zmiennoprzecinkowe parametry a, b równania liniowego. Funkcja powinna wyświetlić na standardowym wyjściu fragment kodu SVG, który na obrazie o rozmiarach 1000 x 1000 pikseli narysuje w postaci linii osie rzędnych i odciętych krzyżujące się w pikselu (500, 500) oraz linię zadaną równaniem.
Rozwiązanie:
#include <iostream>
int main() {
double a, b, x1, x2, y1, y2;
std::cin >> a >> b;
x1 = 0;
y1 = -a * (x1 - 500) - b + 500;
x2 = 1000;
y2 = -a * (x2 - 500) - b + 500;
std::cout <<
"<svg height=\"1000\" width=\"1000\">"
"\n\t<line x1=\"" << std::to_string(x1) << "\" y1=\"" << std::to_string(y1) << "\" x2=\"" << std::to_string(x2) << "\" y2=\"" << std::to_string(y2) << "\" style=\"stroke:rgb(255,0,0);stroke-width:2\"/>"
"\n\t<line x1=\"0\" y1=\"500\" x2=\"1000\" y2=\"500\" style=\"stroke:rgb(0,255,0);stroke-width:2\"/>"
"\n\t<line x1=\"500\" y1=\"0\" x2=\"500\" y2=\"1000\" style=\"stroke:rgb(0,0,255);stroke-width:2\"/>"
"\n</svg>" << std::endl;
return 0;
}
Zadanie 22
Napisz funkcję w języku C++, która przyjmuje w argumencie dodatnią liczbę całkowitą i wyświetla jej binarną reprezentację.
Rozwiązanie:
#include <iostream>
void display_binary(unsigned int number) {
if (number) display_binary(number / 2);
std::cout << (number % 2);
}
void display_binary_bitwise_op(unsigned int number) {
if(number) display_binary_bitwise_op(number >> 1);
std::cout << (number & 1);
}
int main() {
unsigned int num = 10;
display_binary(num), std::cout << std::endl;
num = 21;
display_binary(num), std::cout << std::endl;
num = 10;
display_binary_bitwise_op(num), std::cout << std::endl;
num = 21;
display_binary_bitwise_op(num), std::cout << std::endl;
return 0;
}
Zadanie 23
Napisz funkcję w języku C++, która przyjmuje w argumencie liczbę całkowitą dodatnią x i liczbę naturalną n, a następnie zwraca wartość bitu na n-tej pozycji liczby x.
Rozwiązanie:
#include <iostream>
bool check_bit(unsigned int x, unsigned int n) {
return (x >> n) & 1;
}
int main() {
unsigned int num = 10; //1010
std::cout << check_bit(num, 0) << std::endl;
std::cout << check_bit(num, 1) << std::endl;
std::cout << check_bit(num, 3) << std::endl;
return 0;
}
Zadanie 24
Napisz funkcję w języku C++, która przyjmuje w argumencie liczbę całkowitą dodatnią x oraz liczbę naturalną n, a następnie ustawia n-ty bit liczby x na 1. Napisz drugą podobną funkcję, która wyłącza wybrany bit w liczbie x. Napisz trzecią funkcję, która ustawia wskazany bit na przeciwny.
Rozwiązanie:
#include <iostream>
void set_bit(unsigned int &x, unsigned int n) {
x |= (1 << n);
}
void unset_bit(unsigned int &x, unsigned int n) {
x &= ~(1 << n);
}
void negate_bit(unsigned int &x, unsigned int n) {
x ^= (1 << n);
}
int main() {
unsigned int num = 10; //1010b
set_bit(num, 0);
std::cout << num << std::endl; //11(d)
negate_bit(num, 1);
std::cout << num << std::endl; //9(d)
unset_bit(num, 3);
std::cout << num << std::endl; //1(d)
return 0;
}
Zadanie 25
Napisz funkcję w języku C++, która przyjmuje napis. Niech funkcja zwróci liczbę słów w tym napisie.
Rozwiązanie:
#include <iostream>
unsigned int num_of_words(const char str[]) {
unsigned int count = 0;
bool is_word = false;
for (unsigned int i = 0; str[i]; ++i) {
if (str[i] != ' ' && !is_word) {
is_word = true;
count++;
} else if (str[i] == ' ') {
is_word = false;
}
}
return count;
}
int main() {
char str[100] = "Ala ma kota i rybke.";
std::cout << "Liczba slow w napisie: " << num_of_words(str) << std::endl;
return 0;
}
Zadanie 26
Napisz program w języku C++, który dla tablicy znaków wypisuje liczbę całkowitą oznaczającą długość napisu (ilość znaków w tym napisie) – ekwiwalent funkcji bibliotecznej strlen().
Rozwiązanie:
#include <iostream>
unsigned int str_len(const char str[]) {
unsigned int result = 0;
for(;str[result];++result);
return result;
}
int main() {
const char str[100] = "Dlugosc napisu.";
std::cout << "Dlugosc napisu to: " << str_len(str) << std::endl;
return 0;
}
Zadanie 27
Napisz program w języku C++, który wykona kopię napisu (tablicy znakowej) do innej tablicy znakowej – ekwiwalent funkcji bibliotecznej strcpy().
Rozwiązanie:
#include <iostream>
void str_cpy(char dst[], char src[]) {
for(unsigned int i=0; src[i]; dst[i]=src[i], ++i);
}
int main() {
char str_0[100] = "Dlugosc napisu.", str_1[100] = {};
str_cpy(str_1, str_0);
std::cout << str_1 << std::endl;
return 0;
}
Zadanie 28
Napisz program w języku C++, który porówna dwa napisy i wypisze liczbę całkowitą: (1) równą zero, jeżeli oba napisy są identyczne lub (2) mniejszą od zera, jeżeli napis pierwszy jest wcześniej alfabetycznie niż napis drugi lub (3) większą od zera, jeżeli napis pierwszy jest później alfabetycznie niż napis drugi. Jest to ekwiwalent funkcji bibliotecznej strcmp().
Rozwiązanie:
#include <iostream>
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 main() {
char str_0[100] = "Dlugosc napisu.", str_1[100] = {};
std::cout << str_cmp(str_0, str_1) << std::endl;
return 0;
}
Zadanie 29
Napisz program w języku C++, który wyszuka pierwsze wystąpienie pojedynczego znaku w napisie i wypisze liczbę całkowitą równą pozycji tego znaku w napisie lub wartość (-1) jeżeli takiego podciągu nie ma. Jest to ekwiwalent funkcji bibliotecznej strchr().
Rozwiązanie:
#include <iostream>
unsigned int str_chr(char str_0[], char c) {
for(unsigned int i=0; str_0[i]; ++i)
if(str_0[i] == c)
return i;
return -1;
}
int main() {
char str[100] = "Dlugosc napisu.";
std::cout << str_chr(str, 's') << std::endl;
return 0;
}
Zadanie 30
Napisz program w języku C++, który wyszuka pierwsze wystąpienie podciągu w napisie, tzn. wyszukuje jeden napis wewnątrz innego napisu i wypisze liczbę całkowitą równą pozycji pierwszego znaku w napisie, w którym zaczyna się podciąg lub wartość (-1) jeżeli takiego podciągu nie ma. Jest to ekwiwalent funkcji bibliotecznej strstr().
Przykład:
napis = "alamakota"
podciąg = "mak"
wynik = 3
Rozwiązanie:
#include <iostream>
unsigned int str_len(const char str[]) {
unsigned int result = 0;
for(;str[result];++result);
return result;
}
int str_str(char text[], char pat[]) {
unsigned int m = str_len(pat);
for(unsigned int i=0; text[i]; ++i)
for(unsigned int j=0; pat[j]; ++j) {
if(text[i + j] != pat[j])
break;
if(m - 1== j)
return i;
}
return -1;
}
int main() {
char pattern[] = "maka", text[] = "alamakota";
std::cout << str_str(text, pattern) << std::endl;
return 0;
}
Zadanie 31
Napisz program w języku C++, który liczbę całkowitą (bez znaku) na jej reprezentację znakową (string) – ekwiwalent funkcji bibliotecznej sprintf().
Przykład:
int k = 267 => char str[] = {'2', '6', '7', '\0'};
Rozwiązanie:
#include <iostream>
#include <cmath>
unsigned int num_digits(int value) {
unsigned int result = 0;
do ++result; while(value /= 10);
return result;
}
void my_sprintf(int value, char result[]) {
for(unsigned int i = 0, tmp = pow(10, num_digits(value) - 1); tmp; ++i, value %= tmp, tmp /= 10)
result[i] = '0' + (value / tmp);
}
int main() {
int k = 267;
char str[100] = {};
my_sprintf(k, str);
std::cout << str << std::endl;
return 0;
}
Zadanie 32
Napisz program w języku C++, który zamieni reprezentację znakową liczby całkowitej bez znaku (string) na zmienną typu liczby całkowitej – ekwiwalent funkcji bibliotecznej atoi().
Przykład:
char str[] = {'2', '6', '7', '\0'} => int k = 267
Rozwiązanie:
#include <iostream>
#include <cmath>
unsigned int number_len(const char str[]) {
unsigned int result = 0;
for(;str[result] >= '0' && str[result] <= '9';++result);
return result;
}
int my_atoi(char str[]) {
unsigned int tmp = pow(10, number_len(str) - 1), i = 0;
int result = 0;
do result += (str[i++] - '0') * tmp; while(tmp /= 10);
return result;
}
int main() {
char str[100] = "267ab";
std::cout << number_len(str) << std::endl;
int result = my_atoi(str);
std::cout << result << std::endl;
return 0;
}
Zadanie 33
Napisz program w języku C++, który odwróci kolejność znaków w napisie.
Przykład:
WE: "Ala ma kota"
WY: "atok am alA"
Rozwiązanie:
#include <iostream>
unsigned int str_len(const char str[]) {
unsigned int result = 0;
for(;str[result];++result);
return result;
}
void reverse_str(char str[]) {
unsigned int s = 0, e = str_len(str) - 1;
while(s < e) std::swap(str[s++], str[e--]);
}
int main() {
char str[100] = "267ab";
reverse_str(str);
std::cout << str << std::endl;
return 0;
}
Zadanie 34
Napisz program w języku C++, który zamieni w tablicy znakowej małe litery na duże, duże na małe a pozostałe znaki nie zostaną zmienione.
Rozwiązanie:
#include <iostream>
void change_str(char str[]) {
for(unsigned int i = 0;str[i]; ++i)
if(str[i] >= 'a' && str[i] <= 'z')
str[i] -= 32;
else if(str[i] >= 'A' && str[i] <= 'Z')
str[i] += 32;
}
int main() {
char str[100] = "AcK267ab";
change_str(str);
std::cout << str << std::endl;
return 0;
}
Zadanie 35
Napisz program w języku C++, wyszuka w napisie wszystkie liczby a następnie na ekranie poda ich sumę. Zakładamy, że w napisie może się znajdować dowolna ilość liczb całkowitych i są zawsze odseparowane od reszty znaków symbolem spacji.
Przykład:
WEJŚCIE: "Ala ma 5 kotow, 3 psy i 19 myszek"
WYJŚCIE: 27
Rozwiązanie:
#include <iostream>
int sum_all_string_values(const char str[]) {
bool is_negative = false;
int result = 0, number = 0;
for (unsigned int i = 0; str[i]; ++i) {
if(str[i] == '-' && str[i + 1] && str[i + 1] >= '0' && str[i + 1] <= '9') {
is_negative = true;
} else if (str[i] >= '0' && str[i] <= '9') {
number = number * 10 + (str[i] - '0');
} else if (number != 0) {
if(is_negative) number *= -1;
result += number;
number = 0;
is_negative = false;
}
}
if (number != 0) {
if(is_negative) number *= -1;
result += number;
}
return result;
}
int main() {
char str[100] = "AcK 26 7ab 8 fsakf -1";
int result = sum_all_string_values(str);
std::cout << result << std::endl;
return 0;
}
