Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ ЛАБОРАТОРНА РОБОТА №1 з дисципліни: “Алгоритми” Львів 2008 Тема: Порівняння складності арифметичних операцій в римській та десятковій системах числення Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів. I. Теоретична частина. Алгоритм – точний припис, який задає обчислювальний процес, що починається з довільних початкових даних і спрямований на отримання результату, який повністю визначається цим початковим даним. Властивості алгоритму: Дискретність – алгоритм проводиться за послідовністю кроків. Детермінованість – результат обчислення на кожному кроці точно відповідає вхідним умовам, даним і функції перетворення на цьому кроці Елементарність – простота і локальність кроків алгоритму. Масовість – один і той же алгоритм дозволяє розв’язувати множину задач які відрізняються набором вхідних даних. Параметри алгоритму: Правило початку. Правило виводу даних. Система вхідних даних. Правило безпосереднього перероблення. Система проміжних результатів. Правило виводу результатів. Система результатів. Правило закінчення. II. Практична частина Виконати арифметичну операцію в римській та десятковій системах числення. Завдання №4 LVII – IX 56 – 9 Блок-схема адгоритму для десаткової системи числення (56 – 9) Початок Ввід даних: a = 56 b = 9; a1 = 6, b1 = 9, a2 = 5, b2 = 0 і=1 Значення с1 вибирається з таблиці віднімання для чисел від 0 до 9 c1= Tij; i= 4; j=5; cі = mas[ai,bi], і=і+1 Визначення займу в старшому розряді ai-1 < bi-1 Так ai = ai - 1 Ні i <=2 Так Ні c = “47” “c” = “c2”+ “c1” Кінець Часова складність L = 10 Програмна складність Р =7 Блок-схема адгоритму для римської системи числення(LVII – IX). Початок Кінець Ввід даних a = "LVII" b = "IX" a = "L + V + II " b =" II + V + II" c = "V + II" b = " II " + c a = a - c b =b - c a = "L+V+II-V-II" ="L" b ="II+V+II-V-II" = "II" s = a s=" VLIII" Еквівалентне перетворення Виділення цифри Еквівалентні перетворення здійснюються за допомогою скінченої таблиці еквівалентних перетворювань . II=I+I; III=II+I; IV=III+I; V=IV+I; VI=V+I; VII=V+II; VIII=V+III; IX=VIII+I; X=IX+I;......L=XL+X; ... M=CM+C; Еквівалентне перетворення a = "-V+III+L+II" Виділення цифри b = c c = "II" a = a - c a = "-V+III+L+II-II” = ”VLIII" b =b - c b = "II - II” = ”” Часова складність L =8 Програмна складність Р =5 Отже для даного прикладу часова і програмна складність менша в алгоритмі віднімання римської системи числення. III. Висновки. На лабораторній роботі засвоїв основні визначення, порівняв часову та програмну складність алгоритмів.