Курсова робота на тему: «ДОВГА АРИФМЕТИКА В PASCAL»

Зміст

Вступ    3

Числові алгоритми    4

I.    Додавання двох “довгих” чисел    11

II.    Віднімання двох “довгих” чисел    12

III.    Множення “довгого” числа на “коротке”    13

IV.    Множення “довгого” числа на “довге”    15

V.    Ділення “довгого” числа на “коротке”    16

VI.    Ділення “довгого” числа на “довге”    18

VII.    Обчислення найбільшого спільного дільника двох “довгих” чисел    21

VIII.    Обчислення найменшого спільного кратного двох “довгих” чисел    22

IX.    Піднесення “довгого” числа в “коротку” степінь    23

X.    Обчислення факторіала “короткого” числа    27

XI.    Обчислення кореня квадратного “довгого” числа    28

Розв’язання задач    30

Висновки    38

Список використаної літератури    39

 

Вступ

Інформатика – це наука про методи та засоби опрацювання інформації. Світ інформатики це світ персональних комп’ютерів та алгоритмів. Щоб зручно і впевнено почуватись у світі інформатики, треба знати будову, призначення та принципи функціонування комп’ютерів та алгоритмів. Комп’ютери навколо нас, вони супроводжують усі види нашої діяльності.

Це стосується також і інформації. Інформацію ми отримуємо, опрацьовуємо та пересилаємо щоденно. Вона надходить з різних джерел: книжок, газет, журналів, радіо, телебачення.

Сьогодні неможливо уявити кваліфікованого спеціаліста, який би не використовував комп’ютер повсякчасно.

Наше суспільство перетворюється з індустріального в інформаційне. А в ньому не лише професійний, а й культурний рівень людини визначатиметься розумінням процесів і вмінням спілкуватися з комп’ютером.

“Скільки?” Ми часто чуємо це питання і часто його ставимо. І в побуті і на виробництві, і в наукових дослідженнях. Отже без перебільшення історію математики можна вважати історією того, як люди вчилися відповідати на запитання “скільки?”. Уже давно відомо, як перерахувати предмети, записувати результати, вимовляти їх. Арифметика – наука дій над числами – одна із найдосконаліших.

У наш час люди рахують набагато краще, ніж у недалекому минулому: у них є добрі помічники — “розумні” комп’ютери. Сьогодні обчислення ведуться в сотні й тисячі разів швидше, ніж кілька десятиліть тому. Це досягається тим, що комп’ютери рахують інакше ніж люди.

Однією з мов програмування якою можна скористатися під час разв’язання математичних задач є мова програмування Pascal. За допомогою цієї мови програмування можна розв’язувати досить складні математичні задачі, не затрачуючи при цьому багато часу. До задач, які мають громісткі обчислення та займають великий проміжок часу розв’язання належать операції з “довгими числами”.

Числові алгоритми

Як організовується на комп’ютері робота з великими числами, які складаються з великої кількості цифр? Як отримати результат, якщо наперед відомо, що кількість цифр велика? Тобто чи можливо обчислити на комп’ютері знамените шахове число 2641, якщо відомо, що число 18446744073709551615 не поміститься в одну комірку пам’яті? Яким чином можна обчислити число p з більш ніж ста цифрами після коми?

На перший погляд нескладна задача містить в собі великий підводний камінь – “довгу арифметику”. В таких задачах обмеження на вхідні дані роблять вихідні дані такими, які не помістяться в обмежене число розрядів цілочисельної арифметики. А реалізація “довгої арифметики” часто викликає труднощі.

Я вирішила розглянути цей метод програмування ближче. Є основні математичні операції, якими найчастіше доводиться користуватись при розв’язуванні задач на “довгу арифметику”:

  • додавання двох “довгих” чисел;
  • віднімання двох “довгих” чисел;
  • множення “довгого” числа на “коротке”;
  • множення “довгого” числа на “довге”;
  • ділення “довгого” числа на “коротке”;
  • ділення “довгого” числа на “довге”;
  • обчислення найбільшого спільного дільника двох “довгих” чисел;
  • обчислення найменшого спільного кратного двох “довгих” чисел;
  • обчислення факторіала “короткого” числа;
  • піднесення “довгого” числа в “коротку” степінь;
  • обчислення кореня квадратного “довгого” числа.

Кожна з математичних операцій оформлена як окрема процедура, для якої, як вхідні дані, дають один або два масиви для опрацювання, а вона повертає результат. Деякі процедури можуть звертатись до інших процедур для опрацювання даних в ході своєї роботи. Наприклад, процедура ділення “довгого” числа на “довге” може, в ході своєї роботи, звернутись до процедури множення “довгого” числа на “коротке”.

Число, яке може поміститись в змінну типу Integer або LongInt, прийнято називати “коротким”, а число яке не поміщається в обмежену кількість розрядів називають “довгим”. Перший з можливих способів представлення “довгого” числа – це запис його з допомогою масива десяткових цифр. Кількість елементів такого масива рівна кількості значущих цифр в числі. А для роботи з таким масивом він повинен бути досить великим, щоб помістити в ньому результат. Так, при виконанні множення, довжина масива-результата може бути в два рази більша, ніж довжина масива для множників. Для роботи з таким масивом потрібно також зберігати його довжину.

Цей метод досить наочний, але неефективний. Одним з методів підвищення ефективності “довгої арифметики” – це зберігання в кожному елементі масива не по одній, а по дві і більше цифр. Я використала запис числа в масиві з основою 10000, тобто один елемент масива зберігає чотири цифри. В усіх процедурах використовується загальний тип Long, який оголошений на початку програми рядком:

Type Long=Array [0..Max_A] Of LongInt;

Max_A – константа, яка вказує на максимальну довжину масива. В масиві число записується від останнього елемента і до початку масиву, тобто наймолодший розряд, розряд одиниць, знаходиться в останньому елементі масива. В нульовому елементі міститься початок запису числа. Наприклад, число 10234560078 буде поділене на грані по чотири цифри в кожній і записане в такому вигляді:

Mas1: (8,0,0,0,0,0,0,0,10,3456,78);

Кожний елемент масива має тип LongInt, тому що при виконанні операції множення нове значення завжди буде належати типу LognInt, тобто навіть при множенні 9999 самого на себе (максимальне значення елемента масива), значення 99980001 поміщається в тип LongInt, а якщо взяти за основу для запису числа не 10000, а 100000 (в одному елементі 5 цифр), то 99999 при множенні саме на себе дає результат 9999800001 виходить за межі типу LongInt.

Далі при демонструванні роботи процедур, використовуються приклади в системі числення з основою 100. Це виправдано тим, що приклади в системі числення з основою 10000 є досить громіздкими і складними в розрахунках. Оскільки і перша, і друга система є змішаною з системою числення з основою 10, то всі операції в усіх трьох системах виконуються абсолютно однаково.

Розглянемо додавання двох чисел в системі з основою 10, 100 і 10000. Наприклад, додамо 123456789 і 147258:

Числа записані в системі з основою:

10

100

10000

1

2

3

4

5

6

7

8

9

1

23

45

67

89

1

2345

6789

1

4

7

2

5

8

14

72

58

14

7258

Розглянемо додавання двох чисел в системі з основою 10:

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Dovga Aryfm V Pascal (1.0 MiB, Завантажень: 12)

Сторінка: 1 2 3 4 5 6 7 8 9 10
завантаження...
WordPress: 23.5MB | MySQL:26 | 0,393sec