Довга арифметика 1
Довга арифметика - розділ олімпіадного програмування, в якому розглядається реалізація дій з великими числами, що не вміщається в стандартних типах даних. На сьогоднішній день одним з мов, що використовуються для вирішення олімпіадних завдань і підтримує довгу арифметику, є Java, де всі необхідні функції для роботи з довгими числами вбудовані і можна обійтися без трудомістких реалізацій.
В основному ми будемо розглядати роботу з цілими числами. Для зберігання довгого числа можна використовувати цілочисельний масив, де в якості елемента масиву буде одна цифра числа. В 1м елементі масиву будемо зберігати останню цифру числа, у 2м - передостанню і т.д. до останньої цифри. У 0м елементі можна зберігати загальна кількість цифр в числі. У найпростішому випадку, для зберігання числа 154 достатньо буде використовувати такий запис:
Елементом масиву може бути не одна цифра, можливо використовувати один елемент для зберігання 4х цифр, тому що ми розуміємо, що на сучасних ЕОМ всі операції як мінімум 32-розрядні, тому час на складання двох чисел таке ж як і на складання чисел, що складаються з 4-х цифр. Тому часто використовують порядок системи числення base = 10000 і фактично довгі числа зберігаються як би в 10000-й системі числення, це дозволяє збільшити швидкість виконання операцій над ними в 3-4 рази.
Ідея реалізації всіх необхідних операцій (додавання, віднімання, множення, ділення і т.д.) заснована на тих принципах, якими ми користуємося при розрахунках на папері. Навіть коли ми реалізуємо розподіл "в стовпчик", фактично ми працюємо з невеликими числами, зводячи більш складну задачу до набору з більш простих підзадач.
Завдання, які розглядаються в даному розділі є базовий набір, достатній для формування первинних навичок оволодіння принципами довгої арифметики. Практично всі завдання на довгу арифметику вимагають читання з файлу і запис в файл довгих чисел, тому наведемо реалізацію цих функцій в даному розділі, а в розборі задач будемо їх використовувати:
Так само часто виникає необхідність порівнювати довгі числа. Наведемо наступну функцію, яка буде повертати 0 в разі рівності чисел, -1 коли перше число менше другого і 1 коли перше більше: