Головна |
Аналіз трудомісткості алгоритмуМІНІСТЕРСТВО ОСВІТИ Сибірський федеральний університет Кафедра «ПРИКЛАДНОЇ МАТЕМАТИКИ І КОМП'ЮТЕРНОЇ БЕЗПЕКИ» Аналіз трудомісткості алгоритму Курсовий проект Виконав студент КІ11-02Б Чикин А. а. Науковий керівник: доцент Богульская Н. а. КАСНОЯРСК зміст: Завдання ... ... 3 Короткі теоретичні відомості ... ..3 Опис алгоритму ... ... 5 Лістинг розробленого додатка за алгоритмом ... 6 Скріншоти результатів роботи програми ... 9 Аналіз трудомісткості алгоритму ... .. завдання: 1. Розробити алгоритм порозрядного додавання цілих двійкових чисел бітовими операціями: й, диз'юнкція, додавання по модулю два, заперечення. 2. Використовувати розроблений алгоритм для написання програми на мові програмування високого рівня. 3. Проаналізувати трудомісткість розробленого алгоритму. Короткі теоретичні відомості: Кон'юнкція або логічне множення. Таблиця істинності: X Y Z 1 1 + 1 1 0 0 0 1 0 0 0 0 Диз'юнкція або логічне додавання. Таблиця істинності: X Y Z 1 1 + 1 1 0 1 0 1 + 1 0 0 0 Додавання за модулем два або заперечення еквівалентності. Таблиця істинності: X Y Z 1 1 0 1 0 1 0 1 + 1 0 0 0 заперечення: Таблиця істинності: X Z 1 0 0 1 алгоритм: 1. Оголосити три цілочисельних статичних масиву довільного розміру і дати їм позначення: m1, m2, m3. Оголосити три цілочисельні змінні n, p і r. 2. Осередки пам'яті масиву з ім'ям m2 заповнити нулями. 3. Визначити кількість елементів (т. Е. Нулів і одиниць), що входять в кожне з двох цілих двійкових чисел. Кількість елементів числа більшої довжини, позначити за n, а кількість елементів числа меншою довжини, позначити за p. 4. Від кількості елементів числа більшої довжини, відняти кількість елементів числа меншою довжини і різницю позначити за n-p = r. 5. Заповнюємо осередки пам'яті масиву m1 елементами числа, що має велику довжину. Заповнення ведемо з 0-го осередки до осередку з номером n-1. 6. Заповнюємо осередки пам'яті масиву m2 елементами числа, що має меншу довжину. Заповнення ведемо з r-го осередки до осередку з номером n-1. 7. Осередки результуючого масиву m3 заповнюються за принципом порівняння елементів: m1 [0] і m2 [0], m1 [1] і m2 [1], ..., m1 [n-1] і m2 [n-1], враховуючи правила обчислення бітовими операціями. (Кон'юнкція, диз'юнкція, додавання по модулю два, заперечення), т. Е. Працюючи з таблицями істинності, які відповідають кожній бітової операції (дивитися короткі теоретичні відомості). Лістинг розробленого додатка за алгоритмом: #include "stdafx.h" #include "math.h" #include #include "windows.h" #include "stdio.h" #include "stdlib.h" #include "conio.h" #include using namespace std; int m1 [256]; int m2 [256]; int m3 [256]; int n = 0; int p = 0; int printfmenu (); int _tmain (int argc, _TCHAR * argv []) { setlocale (LC_ALL, "Russian"); setlocale (LC_ALL, "rus"); int menu = 0; for (int i = 0; i { m2 [i] == 0; } do { menu = printfmenu (); switch (menu) { case 1: { system ("cls"); printf ("Введіть кількість елементів довшого числа:"); scanf ("% d", & n); for (int i = 0; i { scanf ("% d", & m1 [i]); } system ("cls"); printf ("\ nВведіте кількість елементів менш довгого числа:"); scanf ("% d", & p); for (int i = n-p; i { scanf ("% d", & m2 [i]); } for (int i = 0; i { if (m1 [i] == 0 && m2 [i] == 0) m3 [i] = 0; if ((m1 [i] == 1 && m2 [i] == 0) || (m1 [i] == 0 && m2 [i] == 1)) m3 [i] = 1; if (m1 [i] == 1 && m2 [i] == 1) m3 [i] = 1; } system ("cls"); printf ("перший доданок"); for (int i = 0; i { printf ("% d", m1 [i]); } printf ("\ nвторое доданок"); for (int i = 0; i { printf ("% d", m2 [i]); } printf ("\ nРезультат диз'юнкції:"); for (int i = 0; i { printf ("% d", m3 [i]); } getchar (); getchar (); break; } case 2: { system ("cls"); printf ("Введіть кількість елементів довшого числа:"); scanf ("% d", & n); for (int i = 0; i { scanf ("% d", & m1 [i]); } system ("cls"); printf ("\ nВведіте кількість елементів менш довгого числа:"); scanf ("% d", & p); for (int i = n-p; i { scanf ("% d", & m2 [i]); } for (int i = 0; i { if (m1 [i] == 1 && m2 [i] == 1) { m3 [i] = 1; } if ((m1 [i] == 1 && m2 [i] == 0) || (m1 [i] == 0 && m2 [i] == 1)) m3 [i] = 0; if (m1 [i] == 0 && m2 [i] == 0) m3 [i] = 0; } system ("cls"); printf ("перший доданок"); for (int i = 0; i { printf ("% d", m1 [i]); } printf ("\ nвторое доданок"); for (int i = 0; i { printf ("% d", m2 [i]); } printf ("\ nРезультат кон'юнкції:"); for (int i = 0; i { printf ("% d", m3 [i]); } getchar (); getchar (); break; } case 3: { system ("cls"); printf ("Введіть кількість елементів довшого числа:"); scanf ("% d", & n); for (int i = 0; i { scanf ("% d", & m1 [i]); } system ("cls"); printf ("\ nВведіте кількість елементів менш довгого числа:"); scanf ("% d", & p); for (int i = n-p; i { scanf ("% d", & m2 [i]); } for (int i = 0; i { if ((m1 [i] == 1 && m2 [i] == 1) || (m1 [i] == 0 && m2 [i] == 0)); { m3 [i] = 0; } if ((m1 [i] == 0 && m2 [i] == 1) || (m1 [i] == 1 && m2 [i] == 0)) { m3 [i] = 1; } } system ("cls"); printf ("перший доданок"); for (int i = 0; i { printf ("% d", m1 [i]); } printf ("\ nвторое доданок"); for (int i = 0; i { printf ("% d", m2 [i]); } printf ("\ nРезультат складання по модулю 2:"); for (int i = 0; i { printf ("% d", m3 [i]); } getchar (); getchar (); break; } case 4: { system ("cls"); printf ("Введіть кількість елементів:"); scanf ("% d", & n); for (int i = 0; i { scanf ("% d", & m1 [i]); } for (int i = 0; i { if (m1 [i] == 1) { m3 [i] = 0; } if (m1 [i] == 0) { m3 [i] = 1; } } system ("cls"); printf ("Початкове число:"); for (int i = 0; i { printf ("% d", m1 [i]); } printf ("\ nІнверсія числа:"); for (int i = 0; i { printf ("% d", m3 [i]); } getchar (); getchar (); break; } case 0: { break; } } } While (menu! = 0); return 0; } int printfmenu () { system ("cls"); printf ("--- \ n") ; printf ("|| Меню: || \ n"); printf ("|| 1) Диз'юнкція || \ n"); printf ("|| 2) Кон'юнкція || \ n"); printf ("|| 3) Додавання за модулем два || \ n"); printf ("|| 4) Заперечення || \ n"); printf ("|| 0) Вихід || \ n"); printf ("|| || \ n"); printf ("---"); int number = 0; printf ("\ nВведіте пункт меню:"); scanf ("% d", & number); if (number> 4) { printf ("Вкажіть вірний пункт меню! \ n"); scanf ("% d", & number); } return number; } Скріншоти результатів роботи програми: Аналіз трудомісткості алгоритму: розглянувши |