ARPZ-s1-pr3

Алгоритмы решения прикладных задач, 1-й семестр, 3-я прктика

Задание 1

Написать программу для сложения и вычитания двух больших чисел в столбик. Для представления чисел использовать массив, в котором будут храниться цифры числа. При реализации процедуры вычитания предпочтительно из большего вычитать меньшее. Для этого первоначально определять, какое из двух чисел больше

#include <iostream>

int compare(int *a, int *b, int size)
{
    // Сравнение чисел
    // a - первое число
    // b - второе число
    // size - длина числа

    for (int i = 0; i < size; i++)
    {
        if (a[i] > b[i])
        {
            return 1; // a > b
        } 
        else if (a[i] < b[i]) 
        {
            return -1; // a < b
        }
    }
    return 0; // a равно b
}

int* sum(int *A, int* B, int size) 
{
  // Сложение чисел
  // a - первое число
  // b - второе число
  // size - длина числа

  int *a = new int[size]();
  int *b = new int[size]();
    
  for (int i = 0; i < size; i++) {
      a[i] = A[i];
      b[i] = B[i];
  } 
  
  // Инициализируем массив для хранения результирующего числа с длиной size
  // ************************************************************************
  // *ВНИМАНИЕ! Скобки на конце инициализируют массив нулями! ЭТО ВАЖНО!
  // *Массив может изначально содержать биты, неочищенные из памяти
  // *после работы других программ, что приведет непредвиденным последствиям!
  // ************************************************************************
  int *result = new int[size]();

  // Выполняем поразрядное сложение
  for (int i = size - 1; i >= 0; i--)
  {
    int sum = a[i] + b[i];
    result[i] = sum % 10;  // Помещаем то, что оказалось меньше 10, в текущий разряд

    if(i - 1 >= 0 && sum >= 10)  // Избегаем вставку в следующий разряд при переполнении
    {
      b[i - 1] = b[i - 1] + sum / 10; // Помещаем то, что оказалось больше 10, в следующий разряд
    }
  }

  // Очищаем память от временных массивов
  delete[] a;
  delete[] b;

  // Возвращаем результирующий массив
  return result;
}

int* subtract(int *A, int *B, int size) 
{

    int *a = new int[size]();
    int *b = new int[size]();
      
    for (int i = 0; i < size; i++) 
    {
        a[i] = A[i];
        b[i] = B[i];
    } 

    int *result = new int[size]();

    // Проверяем, какое из двух чисел больше
    if (compare(a, b, size) == -1) 
    {
      int *temp = a;
      a = b;
      b = temp;
    }

    // Выполняем поразрядное вычитание
    for (int i = size - 1; i >= 0; i--) 
    {
        if (a[i] < b[i])
        {
            // Если текущий разряд a меньше b, нужно занять 1 из следующего разряда
            a[i - 1]--; // Уменьшаем следующий разряд
            result[i] = a[i] + 10 - b[i]; // Добавляем 10 к текущему разряду и вычитаем b
        } 
        else 
        {
            result[i] = a[i] - b[i]; // Обычное вычитание
        }
    }

    // Очищаем память от временных массивов
    delete[] a;
    delete[] b;

    return result;
}

int main() 
{

  std::setlocale(LC_ALL, "ru");
  
  int size;
  int *a;
  int *b;

  std::cout << "Максимально предусматриваемая длина числа: ";
  std::cin >> size;

  // Инициализируем массивы чисел. Все элементы аналогично инициализируем нулями
  a = new int[size]();
  b = new int[size]();

  std::cout << "Введите первое число: ";
  for (int i = 0; i < size; i++)
  {
    std::cin >> a[i];
  }

  std::cout << "Введите второе число: ";
  for (int i = 0; i < size; i++)
  {
    std::cin >> b[i];
  }

  int *resultSum = sum(a, b, size);
  int *resultSub = subtract(a, b, size);

  std::cout << "Результат сложения:   ";
  for (int i = 0; i < size; i++)
  {
    std::cout << resultSum[i] << " ";
  }
  std::cout << std::endl;

  std::cout << "Результат вычитания:  ";
  for (int i = 0; i < size; i++)
  {
    std::cout << resultSub[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

Задание 2

Написать программу для реализации ускоренного сложения чисел в двоичной системе

#include <iostream>

bool* addBinary(bool* A, bool* B, int size) {
    bool* result = new bool[size]();
    bool carry = false;  // Перенос

    for (int i = size - 1; i >= 0; i--) {
        // Сложение с учетом переноса
        bool sum = A[i] ^ B[i] ^ carry;  // XOR для сложения
        carry = (A[i] && B[i]) || (carry && (A[i] || B[i]));  // Логика переноса
        result[i + 1] = sum;  // Запись результата
    }
    result[0] = carry;  // Записываем перенос в старший бит

    return result;
}

int main() {
    std::setlocale(LC_ALL, "ru");

    int size;
    std::cout << "Введите длину двоичных чисел: ";
    std::cin >> size;

    bool* a = new bool[size]();
    bool* b = new bool[size]();

    std::cout << "Введите первое двоичное число (0 или 1): ";
    for (int i = 0; i < size; i++) {
        int bit;
        std::cin >> bit;
        a[i] = (bit != 0); // Преобразуем в bool
    }

    std::cout << "Введите второе двоичное число (0 или 1): ";
    for (int i = 0; i < size; i++) {
        int bit;
        std::cin >> bit;
        b[i] = (bit != 0); // Преобразуем в bool
    }

    bool* result = addBinary(a, b, size);

    std::cout << "Результат сложения: ";
    for (int i = 0; i < size + 1; i++) {
        std::cout << result[i] << " ";      
    }    
    std::cout << std::endl;

    // Освобождаем память
    delete[] a;
    delete[] b;
    delete[] result;

    return 0;
}

Задание 3

В задании 2 была реализована идея ускорения суммирования двоичных чисел. Реализуйте сложение десятичных чисел с использованием подобного механизма ускорения.

#include <iostream>

int* addDecimal(int* A, int* B, int size) {
    int* result = new int[size + 1](); // Результат может быть на 1 разряд больше
    int carry = 0; // Перенос

    for (int i = size - 1; i >= 0; i--) {
        // Сложение с учетом переноса
        int sum = A[i] + B[i] + carry; // Сложение
        result[i + 1] = sum % 10; // Текущий разряд
        carry = sum / 10; // Перенос
    }
    result[0] = carry; // Записываем перенос в старший разряд

    return result;
}

int main() {
    std::setlocale(LC_ALL, "ru");

    int size;
    std::cout << "Введите длину десятичных чисел: ";
    std::cin >> size;

    int* a = new int[size]();
    int* b = new int[size]();

    std::cout << "Введите первое десятичное число (цифры от 0 до 9): ";
    for (int i = 0; i < size; i++) {
        std::cin >> a[i];
    }

    std::cout << "Введите второе десятичное число (цифры от 0 до 9): ";
    for (int i = 0; i < size; i++) {
        std::cin >> b[i];
    }

    int* result = addDecimal(a, b, size);

    std::cout << "Результат сложения: ";

    for (int i = 0; i < size + 1; i++) {
        std::cout << result[i] << " ";
    }
    std::cout << std::endl;

    // Освобождаем память
    delete[] a;
    delete[] b;
    delete[] result;

    return 0;
}

Задание 4

Написать программу для умножения двух больших чисел столбиком. Обратите внимание на количество цифр в произведении: их скорее всего будет больше, чем в исходных числах

#include <iostream>

void printArray(int* arr, int size)
{
    // Печать массива, пропуская ведущие нули
    bool leadingZero = true;
    for (int i = 0; i < size; i++)
    {
        if (arr[i] != 0)
        {
            leadingZero = false;
        }
        if (!leadingZero)
        {
            std::cout << arr[i];
        }
    }
    if (leadingZero)
    {
        std::cout << "0"; // Если все нули
    }
    std::cout << std::endl;
}

int* multiplyDecimal(int* A, int sizeA, int* B, int sizeB, int& resultSize)
{
    resultSize = sizeA + sizeB;  // Максимально возможный размер результата
    int* result = new int[resultSize]();  // Инициализируем массив нулями

    // Умножаем каждую цифру первого числа на каждую цифру второго числа
    for (int i = sizeA - 1; i >= 0; i--) 
    {
        for (int j = sizeB - 1; j >= 0; j--)
        {
            int product = A[i] * B[j];
            int sum = product + result[i + j + 1];  // Добавляем к текущему разряду результата

            result[i + j + 1] = sum % 10;  // Текущий разряд
            result[i + j] += sum / 10;  // Перенос
        }
    }
    return result;
}

int main()
{
    std::setlocale(LC_ALL, "ru");

    int sizeA, sizeB;
    std::cout << "Введите длину первого числа: ";
    std::cin >> sizeA;
    int* A = new int[sizeA];

    std::cout << "Введите первое число (цифры от 0 до 9): ";
    for (int i = 0; i < sizeA; i++)
    {
        std::cin >> A[i];
    }

    std::cout << "Введите длину второго числа: ";
    std::cin >> sizeB;
    int* B = new int[sizeB];

    std::cout << "Введите второе число (цифры от 0 до 9): ";
    for (int i = 0; i < sizeB; i++)
    {
        std::cin >> B[i];
    }

    int resultSize;
    int* result = multiplyDecimal(A, sizeA, B, sizeB, resultSize);

    std::cout << "Результат умножения: ";
    printArray(result, resultSize);

    // Освобождаем память
    delete[] A;
    delete[] B;
    delete[] result;

    return 0;
}

Задание 6

Написать программу для нахождения частного и остатка от деления двух чисел методом половинного деления

#include <iostream>

// Функция для нахождения частного и остатка от деления
void divide(int dividend, int divisor, int &quotient, int &remainder) {
    quotient = 0;
    remainder = dividend;

    int currentDivisor = divisor;
    int currentQuotient = 1;

    while (remainder >= divisor) {
        currentDivisor = divisor;
        currentQuotient = 1;

        while (remainder >= currentDivisor + currentDivisor) {
            currentDivisor += currentDivisor;
            currentQuotient += currentQuotient;
        }

        remainder -= currentDivisor;
        quotient += currentQuotient;
    }
}

int main() {
    int dividend, divisor;
    
    std::cout << "Введите делимое: ";
    std::cin >> dividend;
    std::cout << "Введите делитель: ";
    std::cin >> divisor;

    if (divisor == 0) {
        std::cout << "Ошибка: деление на ноль!" << std::endl;
        return 1;
    }

    int quotient, remainder;
    divide(dividend, divisor, quotient, remainder);

    std::cout << "Частное: " << quotient << std::endl;
    std::cout << "Остаток: " << remainder << std::endl;

    return 0;
}