Сторінка
3
3. Нестандартне подання чисел В умовах і розв'язаннях багатьох реальних задач виникають числа, що не подаються в стандартних типах, наприклад, великі цілі числа або дійсні з великою кількістю дробових розрядів. Розглянемо окремі питання реалізації "нестандартної арифметики" цілих та дійсних чисел. Для подання та обробки чисел необхідно означити спеціальні типи та підпрограми реалізації операцій над числами. Необхідні також підпрограми перетворення чисел із цих типів до звичного вигляду й назад, аналогічні процедурам запису та читання даних стандартних типів. Ціле число в будь-якій системі числення зображається послідовністю цифр. Зокрема, подання в стандартних типах – це послідовність двійкових цифр, відтворених бітами. Обробка чисел у їх стандартному поданні відтворює звичні алгоритми виконання арифметичних операцій (додавання "у стовпчик" тощо), але у двійковій системі числення. Нестандартним поданням цілого числа також є послідовність цифр. Питання лише у виборі системи числення та кількості розрядів, а також одиниці пам'яті для відтворення розряду числа. Розглянемо деякі можливі варіанти нестандартного зображення цілих чисел у масивах. 1) Значення цифри десяткового числа подається елементом масиву типу integer. Пам'ять використовується дуже неекономно (розряд займає 2 або 4 байти), але арифметичні операції реалізуються через порозрядні операції над значеннями цифр, уже означені в Паскалі для типу integer. 2) Цифра числа (а не її значення-число) безпосередньо є значенням типу char і подається одним байтом. Покомпонентні операції над значеннями цифр треба відтворити у вигляді операцій над символами. Для зображення чисел зручно скористатися рядковим типом. 3) Значення цифри числа в P-ковій системі подається одним байтом як число від 0 до P-1, де P£ 256. За P=256 кожний біт відображає значення двійкової цифри 0 чи 1; таке подання найекономніше витрачає пам'ять, але вимагає певних зусиль для реалізації операцій. 4) Значення P-кової цифри, де P£ 16, подається чотирма бітами (півбайтом) так, що дві сусідні цифри займають байт. Дійсні числа (точніше, раціональні з їх певної підмножини) можуть подаватися у вигляді з фіксованою чи з плаваючою крапкою. У першому випадку фіксуються розряди для зображення цифр цілої та дробової частини. У другому – розряди дробової частини та показника степеня (мантиси й порядку – див. підрозділ 11.2). Ще один розряд подає знак числа. Варіанти подання відрізняються основами систем числення та довжиною мантиси й порядку, а також одиницями пам'яті для розрядів. Задачі 20.*Означити типи для зображення цілих згідно з варіантами 1-4 у поясненнях. 21. Означити типи для зображення дійсних чисел у вигляді з фіксованою та плаваючою крапкою. 22.*Написати підпрограми введення та виведення числа нестандартного цілого типу. 23. Написати підпрограму обчислення а)* суми; б) різниці двох цілих чисел у нестандартному цілому типі. 24. Написати підпрограму обчислення а) добутку; б) частки від ділення; в) остачі від ділення "нестандартного" цілого числа на число типу integer. 25.*Написати підпрограму обчислення а) добутку; б) частки від ділення; в) остачі від ділення двох "нестандартних" цілих чисел. 26. Вхідними даними програми є послідовність цілих сталих та знаків операцій, що задається метавиразом <стала> { <знак> <стала> } <EOF> Знаки операцій +, -, *, d, m позначають відповідно додавання, віднімання, множення, частку та остачу від ділення. Сталі мають до 20 десяткових цифр. Кожна стала та знак операції набирається на клавіатурі з нового рядка. Ознака кінця <EOF> задається натисканням на "Ctrl-Z". Вихідними даними програми є послідовність вихідних цілих сталих. Перша з них є першою вхідною сталою. Кожна наступна подає результат застосування операції, заданої знаком, до чисел, що подаються попередньою вихідною сталою та наступною вхідною. Створити та використати модуль, що задає обробку чисел у їхньому нестандартному поданні. Варіанти подання – це варіанти 1-4 з пояснень до параграфа 12.3. Варіанти наборів знаків операцій: а) +; б) +, -; в) +, -, *; г) d, m; д) +, -, *, d, m. Сталі задають числа а) невід'ємні; б) невід'ємні та від'ємні (зі знаком '-' попереду). 27. Вхідними даними програми є послідовність дійсних сталих та знаків операцій, що задається метавиразом <стала> { <знак> <стала> } <EOF> Знаки операцій +, -, *, / позначають відповідно додавання, віднімання, множення та ділення. Вхідна стала – це пара цифрових послідовностей, можливо, зі знаками '-' попереду, що задається метавиразом ['-'] Ц { Ц } ' ' ['+'|'-'] Ц [ Ц ] Метасимвол Ц позначає десяткові цифри. Перша послідовність цифр (довжиною до 20) задає дробову частину числа, друга – десятковий порядок (так, символи 123 -12 задають число 0.123× 10-12). Кожна стала та знак операції набирається на клавіатурі з нового рядка. Ознака кінця <EOF> задається натисканням на "Ctrl-Z". Вихідними даними програми є послідовність вихідних дійсних сталих. Перша з них є результатом нормалізації першої вхідної сталої. Кожна наступна подає нормалізований результат застосування операції, заданої знаком, до чисел, що подаються попередньою вихідною сталою та наступною вхідною. Нормалізоване подання числа – це стала вигляду [ '+' | '-' ] Ц1 '.' Ц { Ц } 'E' [ '+' | '-' ] Ц [ Ц ], де метасимвол Ц1 позначає цифри від 1 до 9. Створити та використати модуль, що задає обробку чисел у їхньому нестандартному поданні. Варіанти наборів знаків: а) +, -; б) *, /; в) +, -, *, /. 28. Написати програму створення за p-ковим поданням натурального числа (послідовність p-кових цифр) q-кового, де p, q – числа з множини {2, 3, . , 36}. Довжина вхідної послідовності не більше 50 цифр. Значення p та q відповідно 1) 2 та 8; 2) 8 та 2; 3) 2 та 16; 4) 16 та 2; 5) 8 та 16; 6) 16 та 8; 7) задається як вхідне та 10; 8) 10 та задається як вхідне; 9) задаються як вхідні. 29.*Натуральні k та m, де 1£ k<m£ 2000, задають правильний дріб k/m. Написати програму друкування цифр XX…X, що передують періоду, та періоду YY…Y десяткового розкладу дробу у вигляді 0.XX .X(YY…Y). Наприклад, за дробу 3/4 це буде 0.75(0), за 2/3 – 0.(6), за 1/6 – 0.1(6).
4. Матриці та багатовимірні масиви Розглянемо прямокутну таблицю з m´ n однотипиних елементів як послідовність із m рядків, у кожному з яких n елементів. Послідовності певної довжини подаються в мовах програмування масивами. Отже, виникає поняття "масив, елементами якого є масиви", або двовимірний масив. Якщо елементи прямокутної таблиці самі є послідовностями або таблиці утворюють послідовність певної довжини, то виникає поняття тривимірного масиву тощо. Означення багатовимірних масивів та зображення їх елементів у мові Паскаль опишемо за допомогою простого прикладу. Позиція в грі "хрестики-нулики на полі 3´ 3" подається квадратною таблицею з символів 'x', '0' або ' ' (пропуск). Пронумеруємо клітинки поля, як у шахах – літерами 'a', 'b', 'c' по горизонталі та числами 1, 2, 3 по вертикалі. Тоді рядки таблиці можна подати масивами типу type Row = array [ 'a' 'c' ] of char; Таблицю можна розглянути як послідовність трьох рядків і подати масивом типу type Table = array [ 1 3 ] of Row; Партія, тобто послідовність позицій, має довжину не більше 9, і може подаватися масивом таблиць: type Game = array [ 1 9 ] of Table; Масиви типу Table мають два виміри: номер рядка та номер символу в ньому; масиви типу Game – три: номери таблиці, рядка та символу. Вимір 1 9 у типі Game називається зовнішнім, вимір 'a' 'c', що нумерує символи в рядках, – внутрішнім. Тип Game можна задати еквівалентним виразом, не означаючи імен типів Row і Table, а саме: type Game = array [ 1 9 ] of array [ 1 3 ] of array [ 'a' 'c' ] of char; Нехай A – змінна типу Game. Вираз вигляду A[ i ], де 1£ i £ 9, задає змінну типу Table, або типу array [ 1 3 ] of array [ 'a' 'c' ] of char; вираз вигляду A[i][j], де 1£ j£ 3, – змінну типу Row, або типу array[ 'a' 'c' ] of char; вираз вигляду A[i][j][k], де 'a' £ k £ 'c', – змінну типу char. Мова Паскаль допускає іншу форму задання типів та елементів багатовимірних масивів: виміри та індекси записуються через кому в спільних дужках. Так, означення type Game1 = array [ 1 9, 1 3, 'a' 'c' ] of char еквівалентне означенню типу Game, а вираз A[i, j, k] – виразові A[i][j][k]. Елементи багатовимірних масивів розташовуються в пам'яті послідовно, найшвидше в них змінюється внутрішній індекс, найповільніше – зовнішній. Зокрема, двовимірні масиви (матриці) розташовуються за рядками. Так, послідовні числа масиву типу array [ 1 2, 'a' 'b' ] of real мають набори індексів [1, 'a'], [1, 'b'], [2, 'a'], [2, 'b'], а послідовні символи в масиві типу Game – [1, 1, 'a'], [1, 1, 'b'], [1, 1, 'c'], [1, 2, 'a'], … , [1, 3, 'c'], [2, 1, 'a'], … , [9, 3, 'c']. Задачі 30. Написати процедуру побудови за дійсними числами a1, … , an квадратної матриці а) 1 1 … 1 б) a1 a2 … an-1 an a1 a2 … an a2 a3 … an a1 … … a1n-1 a2n-1 … ann-1 an a1 … an-2 an-1 31.*У матриці розмірами M ´ N обміняти місцями а) два рядки, б) два стовпці, задані номерами. 32.*Транспонувати квадратну матрицю без використання додаткової матриці. 33.*Квадратну матрицю повернути за годинниковою стрілкою на а) 90° ; б) 180° . Додаткову матрицю не використовувати. 34. Елемент матриці називається сідловим, якщо його значення є мінімальним у рядку й максимальним у стовпці, на перетині яких він знаходиться (або навпаки, максимальним у рядку й мінімальним у стовпці). Написати процедуру повернення номерів рядка та стовпця якого-небудь із сідлових елементів (якщо таких немає, то повертається пара номерів зовні індексної множини матриці). 35. За матрицею з дійсними елементами побудувати нову "згладжену" матрицю, значенням кожного елемента якої є середнє арифметичне значень відповідного елемента та його сусідів у початковій матриці. 36.*Написати процедуру обчислення добутку двох матриць. 37. Написати процедуру обчислення степеня квадратної матриці на основі "індійського алгоритму" (див. підр. 9.4). 38. За квадратною матрицею розміру N одержати послідовність чисел b1, b2, … , bN*N обходом матриці а) "змійкою": б) за спіраллю: 39. Елементи N-вимірного масиву розмірів M1 ´ … ´ MN розміщаються в пам'яті комп'ютера послідовно так, що найшвидше змінюється їх останній індекс, найповільніше – перший. Написати функцію обчислення лінійного індексу елемента (його номера в порядку розташування в пам'яті) за заданими розмірами M1, … , MN та індексами елемента в N-вимірному масиві. Написати процедуру обчислення індексів елемента в багатовимірному масиві за його лінійним індексом та розмірами M1, … , MN. Значенням N є: а) 2; б) 3; в) 4. 40. Зображення містить замкнений контур і подається матрицею з 50 рядків по 80 символів. Елементи контура зображаються символом chr(219), порожні клітини всередині та зовні контура – пропуском ' '. Якщо всередині контура є хоча б один елемент із значенням '1' (відмічений), то зображення "заливається", тобто всі елементи всередині контура відмічаються за правилом: елемент відмічається, якщо з чотирьох його сусідніх по вертикалі чи горизонталі елементів хоча б один відмічений. Написати процедуру заливання зображення.
Завантажити реферат