Финални задачи към част I

Днес ще трябва да решите задачи затвърждаващи знанията ви по уроците в тази тема: Въведение в езика C++.

Задачи и решения:

Задача 1*: Имате два int[] масива от по 1000 елемента. Генерирайте съдържанието им с rand(). Като всяко число в масивите трябва да е в интервала от 1 до 100. В трети масив запишете само общите им елементи без повторения и го отпечатайте.

Решение 
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAX_SIZE {1'000};
int arrayA[MAX_SIZE] {};
int arrayB[MAX_SIZE] {};

int arrayC_Size {0};
int arrayC[MAX_SIZE] {};

void Randomize() {
    srand((unsigned) time(0));
}

int RandomInt(int min, int max) {
    return min + rand() % (max - min + 1);
}

void FillArray(int arr[], int size) {
    for(int i = 0; i < size; i++)
        arr[i] = RandomInt(1, 100);
}

void PrintArray(const int arr[], int size) {
    cout << endl;
    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

bool ArrayHasValue(const int arr[], int arraySize, int value) {
    for(int i = 0; i < arraySize; i++)
        if(arr[i] == value) return true;
    return false;
}

int main() {
    Randomize();
    FillArray(arrayA, MAX_SIZE);
    FillArray(arrayB, MAX_SIZE);

    /* търсим общите елементи между arrayA и arrayB
       и ги записваме в arrayC без повторения */
    
    for(int i = 0; i < MAX_SIZE; i++) {
        int value = arrayA[i];
        if(ArrayHasValue(arrayB, MAX_SIZE, value)) {
            if(not ArrayHasValue(arrayC, arrayC_Size, value)) {
                arrayC[arrayC_Size] = value;
                arrayC_Size++;
            }
        }
    }
    
    PrintArray(arrayC, arrayC_Size);
}

Задача 2: Имате два float[] масива от по 20 елемента. Генерирайте съдържанието им с rand(). Като всяко число в масивите трябва да е в интервала от 1.0 до 100.0. Отпечатайте ги. В трети масив запишете произвседението. Например c[0] = a[0] * b[0]. Изведете масива с резултатите.

Решения 
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAX_SIZE {20};
float arrayA[MAX_SIZE] {};
float arrayB[MAX_SIZE] {};
float arrayC[MAX_SIZE] {};

void Randomize() {
    srand((unsigned) time(0));
}

float RandomFloat(int min, int max) {
    return min + (double) rand() / RAND_MAX * (max - min);
}

void FillArray(float arr[], int size) {
    for(int i = 0; i < size; i++)
        arr[i] = RandomFloat(1, 100);
}

void PrintArray(const float arr[], int size) {
    cout << endl;
    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    Randomize();
    FillArray(arrayA, MAX_SIZE);
    FillArray(arrayB, MAX_SIZE);

    // решение
    for(int i = 0; i < MAX_SIZE; i++)
        arrayC[i] = arrayA[i] * arrayB[i];
    
    cout << "Array A: ";
    PrintArray(arrayA, MAX_SIZE);
    cout << "Array B: ";
    PrintArray(arrayB, MAX_SIZE);
    cout << "Array C: ";
    PrintArray(arrayC, MAX_SIZE);
}

Задача 3: Напишете ваша функция StringCompare, която сравнява два char[] масива и го прави лексикографски. 

int StringCompare(const char a[], const char b[]);

// връща отрицателно число при a < b
// връща 0 при a == b
// връща положително число при a > b

Как трябва да работи:

  • Сравняваме символ по символ;
  • ако a[i] < b[i] → първият низ е по – малък;
  • ако a[i] > b[i] → първият низ е по – голям;
  • ако са равни → продължаваме;
  • ако стигнем края → по-късият е по – малък;
Решение 
int StringCompare(const char a[], const char b[]) {
    int i = 0;

    while (a[i] != '\0' && b[i] != '\0') {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
        i++;
    }

    // ако единия е по-къс
    if (a[i] == '\0' && b[i] == '\0') return 0;
    if (a[i] == '\0') return -1;
    return 1;
}

Тест на StringCompare():

#include <iostream>
using namespace std;

int StringCompare(const char a[], const char b[]) {
    int i = 0;

    while (a[i] != '\0' && b[i] != '\0') {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
        i++;
    }

    // ако единия е по-къс
    if (a[i] == '\0' && b[i] == '\0') return 0;
    if (a[i] == '\0') return -1;
    return 1;
}

int main() {
    char a[] = "apple";
    char b[] = "airport";

    int result = StringCompare(a, b);

    if (result == 0)
        cout << "Equal";
    else if (result < 0)
        cout << "a < b";
    else
        cout << "a > b";
}

Задача 4*: Имате масив от думи записани в char[]. Сортирайте го по метода на мехурчето и изведете сортирания масив. Използвайте функцията, която написахте в горната задача. Ето и декларацията на масива:

    char* words[] = {
        "apple", "parrot", "banana", "orange", "grape",
        "tiger", "elephant", "computer", "keyboard", "monitor",
        "school", "teacher", "student", "window", "bottle", 
        "phone", "camera", "river", "mountain", "cloud"
    };

По същество това представлява масив от указатели към char* масиви завършващи на ‘\0’. Реално при сортирането просто разменяме местата на указателите.

Решение 
#include <iostream>
using namespace std;

int StringCompare(const char a[], const char b[]) {
    int i = 0;

    while (a[i] != '\0' && b[i] != '\0') {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
        i++;
    }

    // ако единия е по-къс
    if (a[i] == '\0' && b[i] == '\0') return 0;
    if (a[i] == '\0') return -1;
    return 1;
}

void BubbleSort(char* arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {

            // ако arr[j] > arr[j + 1]
            if (StringCompare(arr[j], arr[j + 1]) > 0) {

                // размяна
                char* temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void PrintWords(char* arr[], int size) {
    cout << endl;
    for (int i = 0; i < size; i++) {
        cout << arr[i] << endl;
    }
    cout << endl;
}

int main() {
    char* words[] = {
        "apple", "parrot", "banana", "orange", "grape",
        "tiger", "elephant", "computer", "keyboard", "monitor",
        "school", "teacher", "student", "window", "bottle",
        "phone", "camera", "river", "mountain", "cloud"
    };
    int size = sizeof(words) / sizeof(words[0]);
    
    BubbleSort(words, size);
    PrintWords(words, size);
}

Задача 5: Имате зададен масив от string[]. Сортирайте го с библиотечната функция sort. И го изведете в терминала.

string words[20] = {
    "apple", "river", "mountain", "cloud", "forest",
    "ocean", "sun", "moon", "star", "wind",
    "fire", "stone", "tree", "flower", "grass",
    "bird", "sky", "rain", "snow", "shadow"
};
Решение 
#include <iostream>
#include <algorithm> // за sort
#include <string>
using namespace std;

int main() {
    // масива
    string words[20] = {
        "apple", "river", "mountain", "cloud", "forest",
        "ocean", "sun", "moon", "star", "wind",
        "fire", "stone", "tree", "flower", "grass",
        "bird", "sky", "rain", "snow", "shadow"
    };

    // сортиране
    sort(words, words + 20);

    // извеждане
    cout << endl;
    for(int i = 0; i < 20; i++)
        cout << words[i] << endl;
    cout << endl;
}

Задача 6: Имате затворен интервал от години [1981; 2026]. Това означава, че 1981 и 2026 влизат в изброяването. Изведете високосните години разделени с интервал на един ред.

Решение 
#include <iostream>
using namespace std;

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main() {
    for(int i = 1981; i <= 2026; i++)
        if(isLeap(i))
            cout << i << " ";
    cout << endl;
}

Задача 7**: Напишете програма с името calendar. Тя приема един параметър при извикване от командния ред. Това трябва да е число. По точно година. Програмата отпечатва календара за съответната година в терминала по месеци. И седмиците започват от Понеделник.

Напишете решение без да ползвате STL.
Това е генерална задача прилагаща всичко научено до тук.

Решение 
#include <iostream>
#include <string>
using namespace std;

const string months[] = {
    "Януари", "Февруари", "Март", "Април",
    "Май", "Юни", "Юли", "Август",
    "Септември", "Октомври", "Ноември", "Декември"
};

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int daysInMonth(int month, int year) {
    switch (month) {
        case 1: return 31;
        case 2:
            // Проверка за високосна година
            if (isLeap(year)) return 29;
                else return 28;
        case 3: return 31;
        case 4: return 30;
        case 5: return 31;
        case 6: return 30;
        case 7: return 31;
        case 8: return 31;
        case 9: return 30;
        case 10: return 31;
        case 11: return 30;
        case 12: return 31;
        default:
            return 0;
    }
}

// Връща ден от седмицата:
// 0 = Понеделник, 1 = Вторник, ..., 6 = Неделя
int dayOfWeek(int day, int month, int year) {
    if (month < 3) {
        month += 12;
        year--;
    }

    int k = year % 100;
    int j = year / 100;

    int h = (day + (13 * (month + 1)) / 5 + k +
             k / 4 + j / 4 + 5 * j) % 7;

    // Алгоритъма връща h = 0 като Неделя
    // Нормализиранр: h = 0 за Понеделник
    return (h + 5) % 7;
}

void printMonth(int month, int year) {
    cout << "\n";
    cout << "======== " << months[month - 1]
         << " " << year << " ========\n";

    cout << " Пон  Вт  Ср Чет Пет Съб Нед\n";

    int firstDay = dayOfWeek(1, month, year);
    int days = daysInMonth(month, year);

    // Празни места преди първия ден
    for (int i = 0; i < firstDay; i++) {
        cout << "    ";
    }

    for (int day = 1; day <= days; day++) {
        if (day < 10)
            cout << "  " << day << " ";
        else
            cout << " " << day << " ";

        if ((firstDay + day) % 7 == 0)
            cout << "\n";
    }

    cout << "\n";
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        cout << "Usage: ./calendar <year>\n";
        return 1;
    }

    int year = 0;

    // Преобразуване от char* към int
    for (int i = 0; argv[1][i] != '\0'; i++) {
        if (argv[1][i] < '0' || argv[1][i] > '9') {
            cout << "Invalid year!\n";
            return 1;
        }

        year = year * 10 + (argv[1][i] - '0');
    }

    for (int month = 1; month <= 12; month++)
        printMonth(month, year);
}

Задача 8: Напишете програма която намира първите 1000 прости числа. И ги извежда в терминала. Тук ще използваме функцията:

bool isPrime(int n) {
    if (n < 2) return false;
    // търсим до корен втори (оптимизация)
    for (int i = 2; (i * i) <= n; i++)
        if (n % i == 0) return false;
    return true;
}

Обърнете внимание на (i * i)!

Решение 
#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    // търсим до корен втори (оптимизация)
    for (int i = 2; (i * i) <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int count = 1;
    int num = 2;

    while (count <= 1000) {
        if (isPrime(num)) {
            cout << "Prime [" << count << "] = " << num << endl;
            count++;
        }
        num++;
    }
}

Задача 9: Напишете програма намираща решение на квадратни уравнения от вида Ax^2 + Bx + C = 0

Решение 
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double A, B, C;

    cout << "Въведете A, B и C: " << endl;
    cout << "A = ";  cin >> A;
    cout << "B = ";  cin >> B;
    cout << "C = ";  cin >> C;

    // проверка дали е квадратно уравнение
    if (A == 0) {
        cout << "Това не е квадратно уравнение." << endl;
        return 0;
    }

    double D = B * B - 4 * A * C;

    cout << "Дискриминанта D = " << D << endl;

    // два реални корена
    if (D > 0) {
        double x1 = (-B + sqrt(D)) / (2 * A);
        double x2 = (-B - sqrt(D)) / (2 * A);

        cout << "x1 = " << x1 << endl;
        cout << "x2 = " << x2 << endl;
    }

    // един реален корен
    else if (D == 0) {
        double x = -B / (2 * A);

        cout << "x = " << x << endl;
    }

    // няма реални корени
    else {
        cout << "Уравнението няма реални корени." << endl;
    }
}

Задача 10*: Използвайте реда на Leibniz, за да изчислите числото Pi. Трябва да завъртите циклъл и да спрете когато точността на получения резултат стане по – малка от 10-9. После направете необходимите преобразувания, за да получите реалната стойност на Pi.

Решение 
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
    double pi = 0.0;
    double term;

    int sign = 1;
    int n = 1;

    const double EPS = 10e-9;
    int iterCount = 0;
    
    do {
        term = sign * (1.0 / n);
        pi += term;

        sign *= -1;
        n += 2;
        iterCount++;

    } while (fabs(term) > EPS);

    pi *= 4;
    cout << "pi = "
    
    // това фиксира формата до 10-9
    << fixed << setprecision(9)
    << pi << endl;
    
    cout << "-- Диагностика --" << endl;
    cout << "Необходим брой итерации: " << iterCount << endl;
}

Това са 50 000 000 итерации? От този малък код… Програмата замръзна за ~ 1/2 секунда преди да изплюе отговора. И не съм задал флагове за оптимизация. Не ми се мисли колко време ще отнеме подобен код написан на някой интерпретатор 🙂

Поздравления!
Завършихте част първа от уроците!

На този етап не се очаква от вас да решите всичко, като по учебник. Ако сте решили всички задачи без звездичка минавате. Една решена задачка с * е отличен. А ако успеете да напишете кода на calendar сте на ниво PRO!

Отне ми време да обмисля сложни условия на задачите. Всяка задача иска обмисляне. В някои задачи въвеждаме нови знания без да сме ги обяснили. Това е най – добрия начин за интуитивно учене (проба – грешка). Първо покажи, че го има и работи. После обясни.