Порівняння складності арифметичних операцій в римській та десятковій системах числення. Лабораторна робота з Алгоритми та методи обчислень. Робота № 200104

Перехід до торгівельного партнера Binance

Порівняння складності арифметичних операцій в римській та десятковій системах числення

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

Інформація про роботу

Рік:

2008

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми та методи обчислень

Група:

КI

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 з дисципліни: “Алгоритмізація та методи обчислення” на тему: "Порівняння складності арифметичних операцій в римській та десятковій системах числення". Варіант № 20. Виконав ст. гр. КІ-3 Львів 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 ? Так Ні Висновок : на даній лабораторній роботі я порівнював складність арифметичних операцій в римській та десятковій системах числення, та склав програму для виконання додавання чисел в обох системах сислення. Час виконання дій над числами майже однаковий , проте складність програми для римських чисел набагато більша від такої ж програми але вже для десяткових чисел.

Лабораторна робота Алгоритми та методи обчислень

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись