Паскаль: масиви, Детальна інформація

в) найбільшої довжини їхньої спільної підпослідовності символів (наприклад, для рядків "слова" та "справи" підпослідовності "св" і "са" мають довжину 2);

г) їхньої найдовшої спільної підпослідовності (якщо таких кілька, то повертається найбільш "притиснута" до початку першого рядка – для рядків "справи" та "слова" це "са", а не "св").

19. Нехай над рядками означено дії двох видів: вставити та вилучити символ. Мінімальна довжина послідовності дій, необхідних для перетворення одного рядка в інший, називається відстанню між ними. Наприклад, відстань між рядками "кава" та "чай" дорівнює 5 (вилучити букви "к", "в", "а" та вставити "ч" та "й"). Написати функцію обчислення відстані між двома рядками.

3. Нестандартне подання чисел

В умовах і розв'язаннях багатьох реальних задач виникають числа, що не подаються в стандартних типах, наприклад, великі цілі числа або дійсні з великою кількістю дробових розрядів. Розглянемо окремі питання реалізації "нестандартної арифметики" цілих та дійсних чисел.

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

Ціле число в будь-якій системі числення зображається послідовністю цифр. Зокрема, подання в стандартних типах – це послідовність двійкових цифр, відтворених бітами. Обробка чисел у їх стандартному поданні відтворює звичні алгоритми виконання арифметичних операцій (додавання "у стовпчик" тощо), але у двійковій системі числення.

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

1) Значення цифри десяткового числа подається елементом масиву типу integer. Пам'ять використовується дуже неекономно (розряд займає 2 або 4 байти), але арифметичні операції реалізуються через порозрядні операції над значеннями цифр, уже означені в Паскалі для типу integer.

2) Цифра числа (а не її значення-число) безпосередньо є значенням типу char і подається одним байтом. Покомпонентні операції над значеннями цифр треба відтворити у вигляді операцій над символами. Для зображення чисел зручно скористатися рядковим типом.

3) Значення цифри числа в P-ковій системі подається одним байтом як число від 0 до P-1, де P\xF0A3 256. За P=256 кожний біт відображає значення двійкової цифри 0 чи 1; таке подання найекономніше витрачає пам'ять, але вимагає певних зусиль для реалізації операцій.

4) Значення P-кової цифри, де P\xF0A3 16, подається чотирма бітами (півбайтом) так, що дві сусідні цифри займають байт.

Дійсні числа (точніше, раціональні з їх певної підмножини) можуть подаватися у вигляді з фіксованою чи з плаваючою крапкою. У першому випадку фіксуються розряди для зображення цифр цілої та дробової частини. У другому – розряди дробової частини та показника степеня (мантиси й порядку – див. підрозділ 11.2). Ще один розряд подає знак числа. Варіанти подання відрізняються основами систем числення та довжиною мантиси й порядку, а також одиницями пам'яті для розрядів.

Задачі

20.* Означити типи для зображення цілих згідно з варіантами 1-4 у поясненнях.

21. Означити типи для зображення дійсних чисел у вигляді з фіксованою та плаваючою крапкою.

22.* Написати підпрограми введення та виведення числа нестандартного цілого типу.

23. Написати підпрограму обчислення

а)* суми; б) різниці

двох цілих чисел у нестандартному цілому типі.

24. Написати підпрограму обчислення

а) добутку; б) частки від ділення; в) остачі від ділення

"нестандартного" цілого числа на число типу integer.

25.* Написати підпрограму обчислення

а) добутку; б) частки від ділення; в) остачі від ділення

двох "нестандартних" цілих чисел.

26. Вхідними даними програми є послідовність цілих сталих та знаків операцій, що задається метавиразом

<стала> { <знак> <стала> }

Знаки операцій +, -, *, d, m позначають відповідно додавання, віднімання, множення, частку та остачу від ділення. Сталі мають до 20 десяткових цифр. Кожна стала та знак операції набирається на клавіатурі з нового рядка. Ознака кінця задається натисканням на "Ctrl-Z".

Вихідними даними програми є послідовність вихідних цілих сталих. Перша з них є першою вхідною сталою. Кожна наступна подає результат застосування операції, заданої знаком, до чисел, що подаються попередньою вихідною сталою та наступною вхідною.