Week 18 Homework in IT STEP Academy (recursion in C++)

Week 18 Homework.cpp

#include <iostream>
#include <windows.h>
#include <string>


using namespace std;

// Завдання на рекурсію (12 задач)

// 1) Від 1 до n.
// Дано натуральне число n. Виведіть усі числа від 1 до n.
// Вхід: 5
// Вихід: 1 2 3 4 5

void naturalRange(unsigned int n, unsigned int k = 1)
{
    if (k <= n) {
        cout << k << " ";
        naturalRange(n, ++k);
    }
}


// 2) Від A до B.
// Дано два цілих числа A і B. Виведіть усі числа від A до B включно,
// у порядку зростання, якщо A < B, або в порядку зменшення
// в протилежному випадку.
// Вхід: 5 1
// Вихід: 5 4 3 2 1

void rangeBetween(int a, int b)
{
    if (a < b) {
        cout << a << " ";
        rangeBetween(++a, b);
    }
    else if (a > b) {
        cout << a << " ";
        rangeBetween(--a, b);
    }
    else cout << b;
}


// 3) Точна ступінь двійки.
// Дано натуральне число N. Виведіть слово YES, якщо число N
// є точною ступінню двійки, або слово NO в протилежному випадку.
// Операцією піднесення до степеня користуватися не можна!
// Вхід: 3 8
// Вихід: NO YES

bool isExactPowerOfTwo(double n)
{
    if (n != (int)n) return false;  // виявилися особливості С/С++
    if ((int)n < 1) return false;
    if ((int)n == 1) return true;  // 2 ** 0 = 1
    if ((int)n % 2 != 0) return false;  // ця умова має бути саме тут
    return isExactPowerOfTwo((int)n / 2);
}


// 4) Сума цифр числа.
// Дано натуральне число N. Обчисліть суму його цифр.
// Вхід: 179
// Вихід: 17

unsigned int naturalDigitSum(unsigned int n)
{
    if (n == 0) return 0;  // хоча 0 – не натуральне число, проте
    // без цієї умови виникає помилка для десятків, сотень і так далі!
    return naturalDigitSum(n / 10) + n % 10;
}


// 5) Цифри числа справа наліво.
// Дано натуральне число N. Виведіть усі його цифри по одній,
// у зворотному порядку, розділяючи їх пробілами.
// Вхід: 179
// Вихід: 9 7 1

void reverseDigits(unsigned int n)
{
    cout << n % 10 << " ";
    if (n >= 10) reverseDigits(n / 10);
}


// 6) Цифри числа зліва направо.
// Дано натуральне число N. Виведіть усі його цифри по одній,
// у звичайному порядку, розділяючи їх пробілами або новими рядками.
// Вхід: 179
// Вихід: 1 7 9

void forwardDigits(unsigned int n)
{
    if (n >= 10) forwardDigits(n / 10);
    cout << n % 10 << " ";  // виводить на виході з рекурсії 
}


// 7) Реверс числа.
// Дано число n, десятеричний запис якого не містить нулів. Отримайте
// число, записане тими ж цифрами, але в протилежному порядку.
// Функція повинна повертати ціле число, яке є результатом роботи
// програми, виводити число по одній цифрі не можна.
// Вхід: 179
// Вихід: 971

unsigned int mirrorNumber(unsigned int n, unsigned int temp = 0)
{
    // 9 = 179 % 10;
    // 7 = 17 % 10 = (179 / 10) % 10;
    // 1 = 1 % 10 = (17 / 10) % 10;
    // 9 = 0 * 10 + 9;
    // 97 = 9 * 10 + 7;
    // 971 = 97 * 10 + 1;
    if (n == 0) return temp;
    // mirrorNumber(179, 0);
    return mirrorNumber(n / 10, temp * 10 + n % 10);
    // return mirrorNumber(17, 9);
    // return mirrorNumber(1, 97);
    // return mirrorNumber(0, 971);
    // return 971;
}


// 8) Паліндром.
// Дано слово, що складається тільки з малих латинських літер.
// Перевірте, чи є це слово паліндромом. Виведіть YES або NO.
// Вхід: radar yes
// Вихід: YES NO

bool isPalindrome(const string& word, short i, short j)
{
    if (i >= j) return true;
    if (word[i] != word[j]) return false;
    return isPalindrome(word, ++i, --j);
}


// 9) Числа Фібоначчі.
// Напишіть функцію для обчислення елементів ряду чисел Фібоначчі,
// спираючись на рекурентне рівняння F(n) = F(n - 1) + F(n - 2).
// Функція приймає індекс числа, повертає значення числа.

unsigned int fibonacci(unsigned int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n >= 2) return fibonacci(n - 1) + fibonacci(n - 2);
}

// Додаткова функція для виведення послідовності чисел Фібоначчі
// до числа із заданим індексом n:

void printFibonacci(unsigned int n, unsigned int m = 0)
{
    if (m > n) return;
    if (m > 0) cout << ", ";
    cout << fibonacci(m);
    printFibonacci(n, ++m);
}


// 10) Ступінь числа.
// Обчисліть ступінь числа, використовуючи рекурсію. 
// У функцію передається 2 параметри — число і ступінь.

double intPower(double base, int exp)
{
    if (exp == 0) return 1.0;
    if (exp < 0) return 1.0 / intPower(base, -exp);
    return base * intPower(base, --exp);
}


// 11) Сума чисел у діапазоні.
// Обчисліть суму чисел у певному діапазоні.
// Початок та кінець діапазону задаються параметрами функції.

int sumRange(int a, int b)
{
    if (a > b) return sumRange(b, a);
    if (a == b) return a;
    return a + sumRange(a + 1, b);  // тут інкремент недоречний!
}


// 12) НОД.
// Напишіть рекурсивну функцію для знаходження найбільшого спільного
// дільника двох цілих чисел.

// https://uk.wikipedia.org/wiki/Алгоритм_Евкліда
int gcd(int a, int b)  // greatest common divisor
{
    if (b == 0) return a;
    return gcd(b, a % b);
}


int main()
{
    SetConsoleOutputCP(1251);

    // unsigned int k = 1;  // початок натурального ряду
    int n;  // дано натуральне число N
    int a, b;  // дано два цілих числа А і B
    double p, q;  // special for завдання 3
    string word;  // завдання 8
    double base;  // завдання 10
    int exp;  // завдання 10


    cout << "\tЗАВДАННЯ 1\n\n"
        << "Вивести всі числа від 1 до натурального числа n.\n"
        << "Вхід: ";
    cin >> n;
    cout << "Вихід: ";
    naturalRange(n, 1);
    cout << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 2\n\n"
        << "Вивести всі цілі числа від A до B включно.\n"
        << "Вхід: ";
    cin >> a >> b;
    cout << "Вихід: ";
    rangeBetween(a, b);
    cout << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 3\n\n"
        << "Відповісти, чи є два числа точними ступенями двійки.\n"
        << "Вхід: ";
    cin >> p >> q;
    cout << "Вихід: "
        << (isExactPowerOfTwo(p) ? "YES" : "NO") << " "
        << (isExactPowerOfTwo(q) ? "YES" : "NO")
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 4\n\n"
        << "Обчислити суму цифр натурального числа.\n"
        << "Вхід: ";
    cin >> n;
    n = abs(n);  // обробка знака "мінус" для від'ємних цілих чисел
    cout << "Вихід: " << naturalDigitSum(n)
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 5\n\n"
        << "Записати цифри натурального числа справа наліво.\n"
        << "Вхід: ";
    cin >> n;
    n = abs(n);
    cout << "Вихід: ";
    reverseDigits(n);
    cout << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 6\n\n"
        << "Вивести цифри натурального числа у звичайному порядку.\n"
        << "Вхід: ";
    cin >> n;
    n = abs(n);
    cout << "Вихід: ";
    forwardDigits(n);
    cout << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 7\n\n"
        << "Віддзеркалити число.\n"
        << "Вхід: ";
    cin >> n;
    n = abs(n);
    cout << "Вихід: " << mirrorNumber(n)
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 8\n\n"
        << "Перевірити, слово – паліндром чи ні.\n"
        << "Вхід: ";
    cin >> word;
    cout << "Вихід: "
        << (isPalindrome(word, 0, word.length() - 1) ? "YES" : "NO")
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 9\n\n"
        << "Введіть індекс числа Фібоначчі.\n"
        << "Вхід: ";
    cin >> n;
    cout << "Вихід: "
        << fibonacci(n) << "\n" << "Послідовність чисел Фібоначчі: ";
    printFibonacci(n, 0);
    cout << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 10\n\n"
        << "Обчислити ступінь числа, використовуючи рекурсію.\n"
        << "Основа ступеня: ";
    cin >> base;
    cout << "Цілочисельний показник ступеня (додатний, від'ємний або нуль): ";
    cin >> exp;
    cout << "Відповідь: " << intPower(base, exp)
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 11\n\n"
        << "Обчислити суму цілих чисел у певному діапазоні.\n"
        << "Вхід: ";
    cin >> a >> b;
    cout << "Вихід: "
        << sumRange(a, b)
        << "\n" << string(80, '-') << "\n\n";


    cout << "\tЗАВДАННЯ 12\n\n"
        << "Знайти найбільший спільний дільник двох цілих чисел.\n"
        << "Вхід: ";
    cin >> a >> b;
    cout << "Вихід: " << gcd(a, b)
        << "\n" << string(80, '-') << "\n\n";
    // Вхід: 79750 88730
    // Вихід: 10
    // Вхід: 10744 10856
    // Вихід: 8
    // Вхід: 29 23
    // Вихід: 1

    return 0;
}