6. Особливості вивчення «довгої арифметики».
Іноді в програмі необхідно використовувати числа, які виходять за межі діапазону, що представляється стандартними типами даних. У таких випадках програміст сам повинен потурбуватися про подання таких чисел і виконання операцій над ними.
Числа, для представлення яких в стандартних комп'ютерних типах даних не вистачає кількості двійкових розрядів, називаються «довгими». Реалізація арифметичних операцій над такими «довгими» числами отримала назва «довгої арифметики».
Одним із найпростіших способів подання довгих чисел є масив, значенням кожного елементу якого є відповідна цифра числа. Такий спосіб подання є нераціональним з точки зору використовуваної пам’яті, але найбільш легким для розуміння. Кількість цифр у числі можна зберігати в окремій змінній або як однин з елементів масиву (наприклад, елемент з індексом -1, якщо нумерація цифр починається з 0).
При виконанні арифметичних операцій над числами, поданими за допомогою масиву, використовують відомі з початкової школи алгоритми додавання, віднімання, множення в стовпчик. Розглянемо, наприклад, додавання довгих чисел.
Нехай
маємо два числа
і
,
необхідно знайти
При додаванні чисел в стовпчик процес
розпочинається з найменшого (нульового)
розряду. Спочатку додаються цифри
і
;
при цьому, у випадку, коли сума є
одноцифровим числом, це число є останньою
цифрою результату. Якщо сума є двоцифровим
числом, то остання цифра результату
дорівнює останній цифрі суми, а перша
цифра суми переноситься у наступний
розряд. При обчисленні передостанньої
цифри додаються
,
і цифра переносу з попереднього розряду
і т.д.
Таким чином, на кожній ітерації алгоритму слід:
Знайти
,
де
— цифра переносу з попереднього
розряду;Покласти
(остання цифра суми цифр — залишок від
ділення на 10);Покласти
(цифра переносу в наступний розряд є
першою цифрою суми цифр — неповна
частка від ділення на 10).
Вказані
дії повторюються для всіх значень
від 0 до
.
Після завершення циклу необхідно
записати значення цифри переносу в
найстарший розряд суми.
4. Ознайомлення зі структурами даних в поглибленому курсі інформатики.
Відомий спеціаліст з мови програмування Н. Вірт говорив, що «Алгоритм+Структури даних=Програми». Використання структури даних дозволяє будувати ефективніше алгоритм. Ознайомлення зі структурами даних дає учням можливість міркувати загальнішими категоріями, швидше реалізовувати алгоритм.
Основні структури даних, що вивчаються в поглибленому курсі:
1) Стек – структура даних, у якій всі додавання і знищення елементів відбуваються з одного кінця.
2) Черга – структура даних, у якій елементи додаються з одного кінця, а знищуються з іншого.
3) Зв’язний список – кожний елемент списку містить не лише значення, але й позицію наступного елемента.
4) Дерево – бінарне дерево – містить позицію не одного, а двох наступних елементів.