К олимпиаде по программированию. Тема "Длинная арифметика" (Язык программирования C++)
олимпиадные задания на тему

Олимпиады по программированию

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

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

Олимпиады - это система отбора наиболее талантливых студентов, имеющих своеобразный способ мышления, позволяющий решать нестандартные задачи.

Данная разработка составлена в помощь студентам и содержит изложение материала по теме «Длинная арифметика», которая в литературе освещена не достаточно полно. Рассмотрены простейшие математические операции: сложение, вычитание, умножение, деление.

Длинная арифметика

Длинная арифметика - в вычислительной технике операции (сложение, вычитание, умножение, деление, возведение в степень, элементарные функции) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно.

Длинная арифметика - раздел олимпиадного программирования, в котором рассматривается реализация действий с большими числами, не умещающихся в стандартных типах данных.

Например: 123456789012345678901234567890. Это число не поместится ни в int, ни в long. Такие числа очень часто применяются в криптографии.

В настоящее время единственным языком, используемым для решения олимпиадных задач и поддерживающим длинную арифметику, является Java, где все необходимые функции для работы с длинными числами встроены и можно обойтись без трудоемких реализаций.

Рассмотрим работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В первом элементе массива будем хранить последнюю цифру числа, во втором - предпоследнюю и так далее до последней цифры. В нулевом элементе можно хранить общее количество цифр в числе.

Идея реализации всех необходимых операций (сложение, вычитание, умножение, деление и так далее) основана на тех принципах, которые используются при расчетах на бумаге. Даже когда выполняем деление "в столбик", фактически работаем с небольшими числами, сводя сложную задачу к набору из более простых подзадач.

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

// ввод значений, определение количества цифр в длинном числе,

// заполнение массива цифр числа в обратном (зеркальном) порядке

void read_long(int *z)

{

        int i, num = 0;

        char s[80];             // строка для хранения длинного целого числа

        cin >> s;

        cout << " => " << s << endl;

        z[0] = strlen(s);       // количество разрядов длинного числа

        // зеркальное формирование массива цифр числа

        for(i = z[0]; i > 0; i--)

        {

                num++;

                z[num] = s[i - 1] - '0';

                cout << "s[" << i - 1 << "] = " << s[i - 1] << '\t'

                        << "z[" << num << "] = " << z[num] << endl;

        }

}

// вывод результата - элементов массива с конца

void print(int *v, int kol)

{

        int i;

        cout << endl << "s = ";

        for(i = kol; i > 0; i--)

                cout << v[i];

}

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

Сложение длинных чисел 

Стандартные библиотеки должны поддерживать возможность ввода-вывода и работы со строками.

#include

#include

#include

Потребуются функции для ввода значений void read_long(int *z), для вывода результата void print(int *v, int kol).

Кроме этого надо создать функцию для выполнения операции сложения двух целых чисел.

В алгоритме делаем так, как при сложении в столбик:

• складываем отдельные разряды, начиная с конца;
• делим получившуюся сумму на 10 и получаем целую часть от деления на десять, которую сразу прибавляем к следующему разряду;
• отсекаем первый разряд полученного числа, если он есть.

// вычисление суммы двух длинных чисел

int summa(int z[], int v[], int r[])

{

        int i, kol;

        // длина массива суммы

        if(z[0] > v[0])

                kol = z[0] + 1;

        else

                kol = v[0] + 1;

        // вычисление суммы

        for(i = 1; i <= kol; i++)

        {

                // суммируем последние разряды чисел

                r[i] += (z[i] + v[i]);

                r[i + 1] += v[i] + z[i];        // если есть разряд для переноса,

                r[i + 1] /= 10;                  // переносим его в следующий разряд

                // если есть разряд для переноса, он отсекается

                r[i] %= 10;

        }

        if(r[kol] == 0)

                kol--;

        return(kol);

}

В теле функции main() остается вызвать функции для формирования массивов слагаемых и вычисления суммы.

void main()

{

        freopen("input.txt", "r", stdin);

        freopen("output.txt", "w", stdout);

        int a[80] = {0}, b[80] = {0}, c[80] = {0}, kol;

        // массивы слагаемых

        read_long(a);

        read_long(b);

        kol = summa(a, b, c);

        print(c, kol);

        fclose(stdin); fclose(stdout);

}

        Пример.         123125643298 + 9874578208 = 133000221506

Вычитание длинных чисел 

Стандартные библиотеки должны поддерживать возможность ввода-вывода и работы со строками.

#include

#include

#include

Потребуются функции для ввода значений void read_long(int *z), для вывода результата void print(int *v, int kol).

Поскольку не известно, какое из чисел больше, а вычитать будем из большего числа меньшее, сравним их значения. Если первое число больше второго, то k = 1, иначе k = 0.

// сравнение значений

int srawn(int z[], int v[])

{

        int k;

        if(z[0] > v[0])         // сравнение длин чисел

                k = 1;

        if(v[0] > z[0])

                k = 0;

        if(z[0] == v[0])        // если длина одинаковая, сравнить каждую цифру

        {

                for(int i = z[0]; i > 0; i--)

                {

                        if(z[i] > v[i])

                        {

                                k = 1;  break;

                        }

                        if(z[i] < v[i])

                        {

                                k = 0; break;

                        }

                }

        }

        return(k);

}

Кроме этого надо создать функцию для выполнения операции вычитания двух целых чисел. Ремарки в программном коде функции содержат подробные пояснения по вычислению разности.

// вычисление разности

int razn(int z[], int v[], int r[])

{

        int i;

        // проход по всем разрядам числа, начиная с последнего

        for(i = 1; i <= z[0]; i++)

        {

                if(i < z[0])    // если текущий разряд чисел не первый

                {

                        // в следующуем разряде большего числа занимаем 1

                        z[i + 1]--;

                        // в ответ записываем сумму значения текущего разряда

                        // большего числа и 10-ти

                        r[i] += (10 + z[i]);

                }

                // если текущий разряд чисел - первый

                // в ответ суммируем значение текущего разряда большего числа

                else

                        r[i] += z[i];

                // вычитаем значение текущего разряда меньшего числа

                r[i] -= v[i];

                // если значение в текущем разряде двухразрядное

                if((r[i] / 10) > 0)

                {

                        r[i + 1]++;     // переносим единицу в старший разряд

                        r[i] %= 10;     // в текущем разряде отсекаем ее

                }

        }

        while(r[z[0]] == 0)

                z[0]--;

        return( z[0]);

}

В теле функции main() переменные объявлены, значения их вычитаны из файла, и организовано вычитание из большего значения меньшего.

void main()

{

        freopen("input.txt", "r", stdin);

        freopen("output.txt", "w", stdout);

        int a[80] = {0}, b[80] = {0}, c[80] = {0}, kol, dl;

        read_long(a);

        read_long(b);

        // сравнить значения и вызвать функцию для вычисления разности

        kol = srawn(a, b);

        if(kol)

                dl = razn(a, b, c);

        else

                dl = razn(b, a, c);

        print(c, dl);

        fclose(stdin); fclose(stdout);

}

        Пример. 123125643298 - 9874578208 = 113251065090

Умножение длинных чисел 

Стандартные библиотеки должны поддерживать возможность ввода-вывода и работы со строками.

#include

#include

#include

Потребуются функции для ввода значений void read_long(int *z), для вывода результата void print(int *v, int kol).

При вычислении произведения необходимо определить длину результата, которая может быть равна сумме длин сомножителей, или на единицу больше суммы длин сомножителей. Возьмем большее значение. Затем вычисление организовано аналогично умножению в столбик.

// вычисление произведения

int proizv(int *z, int *v, int *r)

{

        int i, j, kol;

        // длина массива произведения

        kol = z[0] + v[0] + 1;

        // вычисление произведения

        for(i = 1; i <= z[0]; i++)

                for(j = 1; j <= v[0]; j++)

                        r[i + j - 1] += z[i] * v[j];

        for(i = 1; i <= kol; i++)

        {

                r[i + 1] += (r[i] / 10);

                r[i] %= 10;

        }

        while(r[kol] == 0)

                kol--;

        return(kol);

}

В теле функции main() надо ввести значения и вызвать функцию для вычисления произведения.

void main()

{

        freopen("input.txt", "r", stdin);

        freopen("output.txt", "w", stdout);

        int a[80] = {0}, b[80] = {0}, c[80] = {0}, kol;

        // массивы сомножителей

        read_long(a);

        read_long(b);

        // вычисление произведения

        kol = proizv(a, b, c);

        print(c, kol);

        fclose(stdin); fclose(stdout);

}

        Пример.         45782008 * 5643298 = 258361514182384

Деление длинных чисел 

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

Рассмотрим пример деления в столбик.

Делим a = 1234 (делимое) на b = 54 (делитель).

Получим неполное частное q = 22, и остаток r = 46.

Деля а на b, мы получаем при выводе числа q и г, которые связаны с а и b следующим образом: a = b q + r и 0 ≤ r < b.

Алгоритм деления 

Ввод: натуральные числа а и b.

Вывод: неотрицательные целые числа q и r, для которых выполнено равенство:

a = b q + r        и        0 ≤ r < b.

Шаг 1. Положить Q = О и R = а.

Шаг 2.        Если R < b, то сообщить: частное равно Q, а остаток равен R, и остановиться.

                Иначе перейти к шагу 3.

Шаг 3. Если R ? b, то вычесть b из R (R = R - b), увеличить Q на 1 (Q = Q + 1) и возвратиться к шагу 2.

Стандартные библиотеки должны поддерживать возможность ввода-вывода и работы со строками.

#include

#include

#include

В глобальной области надо объявить массив для хранения остатка от деления двух целых чисел:                int d[80] = {0};

Потребуются функции для ввода значений void read_long(int *z), для вывода результата void print(int *v, int kol), для сравнения значений int srawn(int z[], int v[]) и для вычисления разности int razn(int z[], int v[], int *r).

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

// вычисление частного

void delen(int z[], int v[], int r[])

{

        int n, i, q = 0, R[80] = {0}, B[80] = {0}, k, kol = 1;

        for(i = 0; i <= z[0]; i++)

        {

                R[i] = z[i];

        }

        n = 1; r[0] = n;

        while((k = srawn(R, v)))

        {

                // считаем остаток

                kol = razn(R, v, B);

                for(i = 1; i <= kol; i++)

                {

                        R[i] = B[i];

                        B[i] = 0;

                }

                // считаем неполное частное

                q++; r[n] = q;

                if(q % 10 == 0)

                {

                        n++;

                        r[n] /= 10;

                        r[n - 1] %= 10;

                }

        }

        for(i = 0; i <= R[0]; i++)

                d[i] = R[i];

        while(d[d[0]] == 0)

                d[0]--;

        if(n > 1)

        {

                // переставить массив в обратном порядке

                for(i = 1; i <= n / 2; i++)

                        r[i] ^= r[n - i + 1] ^= r[i] ^= r[n - i + 1];

                while(r[n] == 0)

                        n--;

                r[0] = n;

        }

}

В теле функции main() объявим массивы и вычитаем значения делимого и делителя. Объявим массив для хранения неполного частного и передадим его имя в функцию для нахождения частного. Организуем вывод результатов вычисления.

void main()

{

        freopen("input.txt", "r", stdin);

        freopen("output.txt", "w", stdout);

        int a[80] = {0}, b[80] = {0}, c[80] = {0};

        read_long(a);

        read_long(b);

        delen(a, b, c);

        cout << endl << "неполное частное";

        print(c, c[0]);

        cout << endl << "остаток";

        print(d, d[0]);

        fclose(stdin); fclose(stdout);

}

        Пример. 234572008 / 5643298 = 41        остаток = 3196790