Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 з дисципліни: “Алгоритмізація та методи обчислення” на тему: "Порівняння складності арифметичних операцій в римській та десятковій системах числення". Варіант № 20. Львів 2008 Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів. Мухамед ібн Муса з Хорезму, за арабським ім’ям – аль-Хорезмі (походженням з середньоазіатського міста Хорезм), видатний багдадський вчений, що працював у ІХ столітті н.е. У своїй книжці – трактаті “Про індійський рахунок” аль-Хорезмі описав десяткову систему числення і арифметичні операції “ множення і ділення, сумування, віднімання та інші”. Сьогодні збереглися лише переклади трактату. Перші з них відносяться до початку XII століття. Наприкінці XVII ст. в роботах Лейбніца цей термін набув змістовності, яка не заперечує сучасному тлумаченню: “Алгоритм - це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу”. Зауважимо, що за довгу еволюцію слова “алгоритм“ було втрачено джерело його виникнення. І тільки у 1849 році сходознавець Ж. Рейно повернув нам ім’я аль-Хорезмі [2]. Арабською “відновлення” – аль-джебр. Звідси походить слово “алгебра”[3]. Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації обсягу досліджень – часовій складності розв’язання задач. Але зміст складності алгоритму не обмежується однією характеристикою. В ряді випадків не менше значення має складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім часової та програмної складності, досліджуються також інші характеристики складності, наприклад, ємкістна, але найчастіше розглядають дві з них - часову і програмну. Якщо у кінцевому результаті часова складність визначає час розв’язання задачі, то програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму. Вона впливає на витрати часу проектування алгоритму. аль-Хорезмі, мабуть, першим звернув увагу на складність римської системи числення у порівнянні з позиційною десятковою з точки зору простоти операцій, їх послідовного виконання та засвоєння. Слова – легкість, стислість, полегшення свідчать перш за все про те, що мова йде про програмну складність алгоритмів арифметичних операцій з використанням двох систем числення. Алгоритми реалізації арифметичних операцій, описані аль-Хорезмі у словесній формі, були першими у позиційній десятковій системі числення. Цікаво спостерігати, як точно і послідовно описує він алгоритм сумування, користуючись арабською системою числення і кільцем (нулем). Наприклад, для операції сумування двох чисел CMLIX + XCIV потрібні таблиці більшого об’єму, ніж 10*10 кожна. Один з варіантів рахунку полягає в представленні чисел, по-перше, розділеними на окремі цифри, по-друге, проведенням операцій віднімання і сумування окремих цифр з використанням таблиць, по-третє, об’єднанням цифр, що залишилися, в єдине число. Як бачимо, для проведення розрахунків у римській системі необхідно виконувати більше типів операцій, ніж у десятковій арабській позиційній системі числення. Крім того, у римській системі потрібні додаткові логічні перетворення, що суттєво ускладнюють зв’язки між окремими операціями обчислювального процесу. Часова складність операцій сумування і віднімання в десятковій системі визначається кількістю розрядів у взаємодіючих числах. У римській системі часова складність залежить від порядку розташування цифр у числах. У тих випадках, коли не потрібно утворювати ланцюги логічних операцій, часова складність не перевищує часову складність операцій з десятковими числами. У протилежному випадку, як у розглянутому прикладі, зростання невелике. Таким чином, за логікою побудови і різноманітністю операцій – програмною складністю, арабська система суттєво простіша за римську, що й довів аль-Хорезмі. За часовою складністю вони майже однакові. · Правила запису і читання чисел в римській системі числення: Числа читаються зліва на право (від більшого до меншого): MXI = 1011; Всі цифри складаються окрім тих, які стоять перед тими, що їх перевершують: XIX = 19; Зліва від цифр, що більші їх самих можуть стояти тільки I, Х, С: I може стояти зліва тільки від V і Х; Х може стояти зліва тільки від L і С; С може стояти зліва тільки від D і M; · Підряд можуть йти тільки три однакові цифри. Підряд можуть йти I, Х, С, M; V, L, D можуть зустрічатися тільки один раз; I, Х, C зліва (від більшої цифри) можуть зустрічатися тільки один; Завдання № 20 LVII + XLIX 57 + 49 LVII + XLIX = L + V + I + I - X + L - I + X LVII + XLIX = L + L + V+ I = CVI;  EMBED Equation.3 
 Виконання однієї операції для римських чисел : ~0,00010486 сек Виконання однієї операції для Десяткових чисел : ~ 0,00008495сек Програмна складність для римських чисел ~587 дій Програмна складність для десяткових чисел ~58 дій  SHAPE \* MERGEFORMAT Початок Перевірка на правильність написання Правильно ? Ввід чисел Так Ні Розстановка знаків Додавання чисел Стирання пробілів між числами Сортування по спаданню цифр Кінець Розстановка цифр за їх знаками (по правилах) Вивід результату IX = -I +X IV= -I+V XL = -X +L XC= -X+C CD= -C+D CM= -C+M Якщо символи рівні, а знаки різні – обидва числа в парі стираємо Уникаємо пробілів, Що утворилися після додавання Наприклад L+V+L+I = L+L+V+I Наприклад D-C+L-X-I-I = CDIIXL X-I-I= IIX +L-X = XL D-C = CD
  SHAPE \* MERGEFORMAT Початок Ввід чисел Розбиваємо числа на розряди Додавання n розряду 1 числа до n розряду 2 числа Кінець Додавання до n+1 розряду переповнення Вивід результату while i<=n do begin L:=d[i]+e[i]; m:=l mod 10; L:=(L-m) div 10; d[i]:=m; if i<>4 then d[i+1]:=d[i+1]+L; end; Поки І<кількості розрядів Так Ні Сума>10 ? Так Ні