Міністерство освіти і науки України Національний університет ″Львівська політехніка″ Кафедра захисту інформації
g Звіт про виконання лабораторної роботи №1 з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ” на тему: “ Алгоритми для виконання операцій з довгими числами ” Перевірив: Лагун А.Е. Львів 2009 Мета роботи: вивчити способи представлення та алгоритми для виконання операцій введення-виведення, порівняння, підсумовування, віднімання довгих чисел та навчитися розробляти програмне забезпечення для реалізації перерахованих алгоритмів на комп’ютері. Завдання : Домашня підготовка до роботи 1) Вивчити основні способи представлення довгих чисел та алгоритми для реалізації операцій введення, виведення, порівняння, а також арифметичних операцій додавання-віднімання довгих чисел. 2) Скласти блок-схеми алгоритмів та підпрограми для реалізації операцій введення та виведення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться за вказівкою викладача з таблиці 5. 3) Скласти блок-схеми алгоритмів, підпрограми та програму для реалізації адитивних операцій та операцій порівняння для роботи з довгими числами. Дані для роботи беруться з таблиці 1 за вказівкою викладача. Таблиця 1. Робота в лабораторії 1) Ввести в комп'ютер програми згідно з отриманим завданням. 2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи. Блок -схема головної програми  SHAPE \* MERGEFORMAT початок vvedit 1 chuslo: masivCh1 a = Input(masivCh1) vvedit 2 chuslo: masivCh2 b = Input(masivCh2) a+b= C=SumLong(a,b) Output(c) a>b: g=More(a,b) g=0 true false ні так кінець
 Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах , та їх пояснення MaxDigit – константа що вказує на максимальну довжину масиву; Osn – константа що вказує на основу; Input() ввід довгого числа з клавіатури; Output() вивід довгого числа на екран; SumLong() додавання двох довгих чисел; More() порівняння двох довгих - чи перше число більше за друге; ch – елемент типу CHAR; masCh – массив елементів типу CHAR; a[] – массив, що представляє довге число; b[]– массив, що представляє довге число; c[]– массив, що представляє довге число; i, j, k – цілі змінні, що використовуються в циклі. Остаточна версія програми #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MaxDig 100 #define Osn 10000 Int *Input( char masivCh[]) { int *a,result,a22; char ch; a = (int*)malloc(MaxDig*sizeof(int)); int i = 0; int j = 0; for(i = 0; i < MaxDig; i++) { a[i] = 0; } for(j = 0; masivCh[j] != NULL; j++) { if ( isdigit(masivCh[j]) ) { for (i = a[0]; i >= 1; i--) { a[i + 1] = a[i + 1] + (a[i] * 10) / Osn; a[i] = a[i] * 10 % Osn; } ch = masivCh[j]; a22 = atoi(&ch); a[1] = a[i+1] + a22; if (a[a[0] + 1] > 0) a[0]++; } } return a; } void Output(int *b) { int N = 0; int NN = 1; int p; int b_Osn = b[0]; int i = 0; for(i = b[0]; i>=1 ; i--) { N = b[i]; if (N == 0) NN = 0; for (p = 1; N > 0; p = p*10) { N = N / 10; } while (Osn - p != 0) { if (b[0] == i) break; printf("%c",'0'); p = p*10; } if (NN == 1) { result = b[i]; printf("%d",result); } NN = 1; N = 0; } } Int *SumLong(int a[], int b[]) { int k; int *c; c= (int*)malloc(MaxDig*sizeof(int)); int i; for( i = 0; i < MaxDig; i++) { c[i] = 0; } if(a[0] > b[0]) { k = a[0]; } else { k = b[0]; } for(i = 1; i <= k; i++) { c[i + 1] = (c[i] + a[i] + b[i]) / Osn; c[i] = (c[i] + a[i] + b[i]) % Osn; } if (c[k + 1] == 1) { c[0] = k + 1; } else { c[0] = k; } return c; } int More(int a[], int b[]) { int e; if (a[0] > b[0]) { e = 1; } else { e = 0; } for (long i = a[0]; i >= 1; i--) { if (a[i] == b[i]) { continue; } else if (a[i] > b[i]) { e = 1; } else { e = 0; } } return e; } int main() { int *a = 0, *b =0, *c = 0, g; char masivCh1[100] , masivCh2[100]; puts("vvedit 1 chuslo:"); gets(masivCh1); a = Input(masivCh1); puts("vvedit 2 chuslo:"); gets(masivCh2); b = Input(masivCh2); c = SumLong(a,b); printf("\na+b="); Output(c); printf("\na>b:"); g=More(a,b); if(g) puts("false"); else puts("true"); system("PAUSE"); return 0; } Результат роботи програми