Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Порівняння складності арифметичних операцій в римській та десятковій системах числення
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи оптимізації
Група:
КI
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
ЛАБОРАТОРНА РОБОТА №1
з дисципліни: “Алгоритми”
Виконав: ст.гр. КІ-3
Львів 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. Висновки.
На лабораторній роботі засвоїв основні визначення, порівняв часову та програмну складність алгоритмів.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора