Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Теорія алгоритмів і математичні основи представлення знань
Група:
КН-411
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 1
з курсу
"Теорія алгоритмів і математичні основи представлення знань"
на тему
" Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності "
Виконав:
Студент групи КН-411
Прийняв:
Львів – 2009
Тема: Складність алгоритмів. Реалізація на ПЕОМ цілочислових арифметичних операцій багатократної точності.
Мета: 1) експериментально дати оцінку складності елементарних арифметичних функцій мов програмування типу Паскаль; 2)забезпечити засобами мови Паскаль або Си емуляцію арифметичних операцій додавання, віднімання, множення i ділення натуральних чисел багатократної точності й оцінити їх складність.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Практично важливим напрямком, що вивчає теорія алгоритмів є дослідження й аналіз їх, складності [2,4].
1. Однією із задач аналізу алгоритмів є необхідність отримання оцінок для об'єму часу, що необхідно алгоритму для обробки конкретних даних. Досить часто, тільки на практиці програміст переконується, що його програма в змозі обробити вхідні дані тільки через декілька діб безперервної роботи ЕОМ. Крім того, необхідно порівнювати ефективність, складність (час роботи, пам'ять) алгоритмів, що ров"язують одну й ту ж задачу.
Нехай А - алгоритм для розв"язування задач деякого класу К, а число n - розмірність окремої задачі з К (кількість змінних, слів у тексті і т.п.) Визначимо fа(n) як функцію складності, що визначає верхню межу для максимальної кількості основних операцій (додавання, порівняння і т.п.), які повинен виконати алгоритм А для розв"язку будь якої задачі розмірності n.
Будемо користуватися наступним критерієм оцінки складності А. Алгоритм А має поліноміальну складність, коли fa(n) зростає не швидше, ніж поліном від n, у протилежному випадку алгоритм А експоненційний. Цей критерії базується на часі роботи у найгіршому випадку. Основою для цього критерію складнсті є машинні експерименти, що продемонстрували, що реальні послідовні або паралельні ЕОМ більш меньш здатні сприймати і ефективно реалізовувати поліноміальні алгоритми для великих задач, а експоненційні алгоритми вони не в змозі "реалізувати" за практично сприйнятний час.
Більш формально, функцію складності fa(n) визначають як O(g(x)) і кажуть, що вона має порядок g(n) для великих n, якщо
f(n)
lim ------- = constanta = a, a>0.
n->g(n)
Це позначується, як f(n) = O(g(n)). Функція h(n) є o(z(n)) для великих n, якщо
h(n)
lim ------- = 0.
n-> z(n)
Змістовно, якщо 1) fa(n) є O(g(x)), то ці дві функції , по суті, зростають з однаковою швидкістю; 2) якщо fa(n) є o(g(x)), то g(n) зростає набагато швидше, ніж fa(n).
Іншими словами, функція f(x) має порядок O(g(x)), якщо знайдеться константа С і f(x) <= C*g(x) для всіх x, крім скінченної (можливо, пустої) множини значень, або, що те саме, завжди знайдеться таке n 40 0, що f(x) <= C*g(x) для всіх x, де x >= n 40 і x > 0.
Розвиток теорії складності обчислень йшов по чотирьом напрямкам :
1) абстрактна (машино-незалежна) складність: 2) машинно-залежна складність;3) складність конкретних задач і алгоритмів; 4)експерементальна (ЕОМ-залежна) складність.
У першому із них обчислювальні моделі і міри складності визначаються аксиоматично і вивчаються найбільш загальні властивості складності алгоритмічних функцій. Доведені теореми про "стискування" і "прискорення". Перша із них стверджує про існування функцій будь якої складності, що оптимально реалізуються. Друга стверджує про існування функцій, кожне обчислення яких можна "прискорити", тобто функцій, для яких не існють оптимальні обчислення.
Другий напрям пов"язаний з дослідженням складності обчислень на конкретних моделях обчислювальних пристроїв и реальних ЕОМ. В цій галузі однією із дуже відомих невирішених проблем є проблема " Р – і NP - складності": чи співпадає клас P функцій, що обчислюються за поліноміальний час на машинах Тюрінга (послідовних ЕОМ), з класом NP функцій, що обчислюються за поліноміальний час на недетермінованих машинах Тюрінга (по суті, паралельних ЕОМ).
Із теорії алгоритмів відомо, що якщо задача Z належить класу NP, то вона завжди реалізується детермінованою машиною Тюрінга з часовою складністю O(k 5Pz(n) 0), де k - константа, а P(n) - поліном, що залежить від Z.
Відмітемо, що до класу P входять класичні комбінатрні проблеми :
а) проблема входження ("ідентифікації") слів, яка полягає у визначенні для двох слів x і y, чи входить x як підслво в y, функція складності якої має порядок O(n), де n - сумарна довжина слів x і y;
б) задача сортування має порядок O(n*log(n));
в) задача множення матриць має порядок складнсті O(n 52.49..0).
По проблематиці третього напрямку наведемо декілька понять і результатів про складність конкретних алгоритмів. Задача Z називається А-повню для класу задач КА, якщо Z належить КА і по будь якому алгоритму, що рзв"язує Z за час T(n), і довільної задачі Z1 із КА можна ефективно побудувати алгоритм В, який розв"язує Z1 за час T(pb(n)), де pb(n) деякій поліном, що залежить від В.
Задача Z називається NP-повною, якщо вона NP-повна для класу NP. На даний час відомо декілька тисяч NP-повних задач, серед яких можна назвати задачі булівського програмування, комівояжера і т.п. для яких відомо, що вони обчислюються за поліноміальний час на недетермінованих машинах Тюрінга. Але не відомо, чи ці NP-повні задачи належать класу P.
Цікаво, що задача ізоморфізму графів належить класу NP,але досі невідомо : 1) чи належить вона класу Р; 2) чи є вона NP-повною ?
Четвертий, експериментальний напрямок пов"язаний з "прокруткою" програми П на скінченній множині вхідних даних, заміром часу її роботи і прямою побудовою по цих замірах функції складності fп(n).
Такий підхід найбільш поширений при оцінці ефективності роботи паралельних, багатопроцесорних ЕОМ і мереж із розподіленою обробкою інформації, але широко і для звичайних послідовних програм, а саме, для виміру реальної швидкодії ЕОМ при реалізації задач практики відносно великої розмірності, так як оцінка ЕОМ по тактовій швидкодії є дуже "грубою".
Тому необхідно, щоб мати уявлення про те, які задачі можуть бути практично реалізовані на конкретному класі ПЕОМ, провести обчислювальні експерименти по оцінці швидкодії ПЕОМ, що і відображено в завданні на дану лабораторну роботу.
2. Завершуючи даний розділ зауважимо, що в теорії алгоритмів широко використовуються дуже великі цілі числа. Так геделiвська нумерація послідовності (x1,x2,..xk) кодусться числом p0 5x1 * p1 5x2 0 * ...pk 5xk 0,де pi - це i-е просте число, а ^ - операцiя пiднесення у степiнь.
В той же час, цілочислові типи даних , що вбудовані в мови програмування, можуть працювати не більше ніж з 10-розрядними числами. Тому для потреб теорії алгоритмів необхідно реалізувати алгоритми емуляції на ЕОМ арифметичних операцій над багаторозрядними числами, одночасно проаналізувавши практичну цінність теоретичних побудов.
Зрозуміло, що актуальними є проблеми експериментальної оцінки складності алгоритмі в багатократної точності.
II. ПОРЯДОК РОБОТИ
1. Вивчити поняття складності алгоритмів.
2. Використовуючи функцію типу get time , скласти програми на одній із мов програмування, що дадуть можливість наближено оцінити складність основних цілочислових арифметичних операцій.
3. На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
4.1 Вибрати i створити необхідні типи даних для реалізації арифметичних операцій багатократної точності над натуральними числами.
4.2 На основі відомих із шкільного курсу алгоритмів додавання, віднімання, множення та ділення DIV ( "у стовпчик") натуральних чисел із N в десятковій системі числення, а також функцій піднесення у степінь і залишку від ділення MOD над N, розробити машинно-орiентований алгоритм для цих операцій та функцій над багаторозрядними натуральними числами.
4.3 Засобами мови Паскаль або Си реалізувати i вiдлагодити відповідні процедури для багаторозрядних чисел.
5.1 Використовуючи функцію типу time із ДОС, скласти програми , що дадуть можливість наближено оцінити складність основних цілочислових операцій арифметики багатократної точності.
5.2 На основі машинних експериментів спробувати апроксимувати функції складності для цих операцій.
6. Здати викладачеві розроблені процедури, продемонструвавши їх працездатність на конкретних багаторозрядних числах.
7. Проаналізувати результати лабораторної роботи .
8. Оформити звіт з лабораторної роботи.
Тексти програм
Types.cpp
#include <stdio.h>
#include <dos.h>
#include <conio.h>
int main(void)
{
struct time tb,te;
long int i;
char abyte=1;
int ainteger=1;
long along=1;
float af =1.0;
double ad=1.0;
long double ald =1.0;
int dt=0;
long N =200000000;
long NF =200000000;
clrscr();
printf("N=%ld\n",N);
printf("Typ \"byte\" \n");
gettime(&tb);
for(i=0;i<N;i++){
abyte=abyte+abyte;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
abyte=-1;
gettime(&tb);
for(i=0;i<N;i++){
abyte=abyte-abyte;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
abyte=2;
gettime(&tb);
for(i=0;i<N;i++){
abyte=abyte*abyte;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
abyte=253;
gettime(&tb);
for(i=0;i<N;i++){
abyte=abyte/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tdiv:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
abyte=253;
gettime(&tb);
for(i=0;i<N;i++){
abyte=abyte%3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tmod:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
printf("Typ \"integer\" \n");
gettime(&tb);
for(i=0;i<N;i++){
ainteger=ainteger+ainteger;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
ainteger=-1;
gettime(&tb);
for(i=0;i<N;i++){
ainteger=ainteger-ainteger;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
ainteger=2;
gettime(&tb);
for(i=0;i<N;i++){
ainteger=ainteger*3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
ainteger=288898;
gettime(&tb);
for(i=0;i<N;i++){
ainteger=ainteger/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tdiv:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
ainteger=288839;
gettime(&tb);
for(i=0;i<N;i++){
ainteger=ainteger%3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tmod:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
printf("Typ \"long\" \n");
gettime(&tb);
for(i=0;i<N;i++){
along=along+along;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
along=-1;
gettime(&tb);
for(i=0;i<N;i++){
along=along-along;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
along=2;
gettime(&tb);
for(i=0;i<N;i++){
along=along*along;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
along=2888937038;
gettime(&tb);
for(i=0;i<N;i++){
along=along/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tdiv:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
along=2888937038;
gettime(&tb);
for(i=0;i<N;i++){
along=along%3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\tmod:\t%4d miliseconds, v= %1.3e \n",dt, double(N)/dt);
printf("N=%ld\n",NF);
printf("Typ \"float\" \n");
gettime(&tb);
for(i=0;i<NF;i++){
af=af+12;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
af=-1.2;
gettime(&tb);
for(i=0;i<NF;i++){
af=af-152;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
af=2.1;
gettime(&tb);
for(i=0;i<NF;i++){
af=af*1.0;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
af=2534758347;
gettime(&tb);
for(i=0;i<NF;i++){
af=af/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t/:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
printf("Typ \"double\" \n");
gettime(&tb);
for(i=0;i<NF;i++){
ad=ad+12;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ad=-1.2;
gettime(&tb);
for(i=0;i<NF;i++){
ad=ad-152;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ad=2.1;
gettime(&tb);
for(i=0;i<NF;i++){
ad=ad*1.0;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ad=2534758347;
gettime(&tb);
for(i=0;i<NF;i++){
ad=ad/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t/:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
printf("Typ \"long double\" \n");
gettime(&tb);
for(i=0;i<NF;i++){
ald=ald+12;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t+:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ald=-1.2;
gettime(&tb);
for(i=0;i<NF;i++){
ald=ald-152;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t-:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ald=2.1;
gettime(&tb);
for(i=0;i<NF;i++){
ald=ald*1.0;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t*:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
ald=2534758347;
gettime(&tb);
for(i=0;i<NF;i++){
ald=ald/3;
}
gettime(&te);
dt=((te.ti_min-tb.ti_min)*60+te.ti_sec-tb.ti_sec)*100+(te.ti_hund-tb.ti_hund);
printf("\t/:\t%3d miliseconds, v= %1.3e \n",dt, double(NF)/dt);
printf("Obrahunok zaversheno");
getch();
return 0;
}
Types.cpp
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
void vidnimannja(int zmenshyvane[],int lzmen, int vidjemnuk[], int lvid,
int riznucia [], int* iriz){
int z = 0,d = 0, i=0;
int izmen,ivid;
*iriz = 0;
for(izmen=lzmen-1, ivid=lvid-1; izmen>=0; izmen--,ivid--){
if(ivid>=0){
z = zmenshyvane[izmen] - vidjemnuk[ivid] + d;
if (z < 0){
d = -1;
z+=10;
}else{
d = 0;//z / 10;
}
riznucia[izmen] = z;//z % 10;
(*iriz) ++;
}else{
z = zmenshyvane[izmen]+d;
if(z<0){
z+=10;
d=-1;
}else {
d=0;
}
riznucia[izmen] = z;
(*iriz)++;
}
}
d = 0;
while((riznucia[d]==0)&&(d<(*iriz)))
d++;
for(i = d; i < *iriz; i++)
riznucia[i-d] = riznucia[i];
(*iriz)-=d;
};
int convertation(char s[], int m []){
int i, l = strlen(s);
for(i = 0; i < l; i++)
m[i] = s[i] - 48;
return l;
};
int compare(int m1[], int l1, int m2[], int l2){
if(l1 > l2)
return 1;
else
if(l1 < l2)
return -1;
else{
for(int i = 0; i < l1; i++){
if(m1[i] > m2[i])
return 1;
else
if(m1[i] < m2[i])
return -1;
else
if(i == l1-1)
return 0;
}
}
}
void main (void){
char s1[255],s2[255],sout[255],s[25];
int m1[255],m2[255],rez[255],r[255];
int i,j,k,d,z,l1,l2,lmax,flag=0;
long div=0;
clrscr();
printf("\nPershe chuslo: ");
gets(s1);
l1=strlen(s1);
printf("Druge chuslo: ");
gets(s2);
l2=strlen(s2);
j=0;
printf("\n+:\t");
for(i=0;i<255;i++){
rez[i]=0;
m1[i]=0;
m2[i]=0;
sout[i]=0;
}
for(i=l1-1;i>=0;i--){
m1[j]=s1[i]-48;
j++;
}
j=0;
for(i=l2-1;i>=0;i--){
m2[j]=s2[i]-48;
j++;
}
z=0;
d=0;
if(l1>l2)
lmax=l1;
else
lmax=l2;
strcat(sout,"%");
sprintf(s,"%d",lmax+1);
strcat(sout,s);
strcat(sout,"s\n");
for(i=0;i<=lmax;i++){
z=m1[i]+m2[i]+d;
d=z/10;
rez[i]=z%10;
}
if(rez[lmax]!=0)
printf("%d",rez[lmax]);
else
printf("");
for(i=lmax-1;i>=0;i--){
printf("%d",rez[i]);
}
printf("\n\n-:\t");
for(i=0;i<255;i++){
rez[i]=0;
}
z=0;
d=0;
if(l1>=l2){
lmax=l1;
for(i=0;i<lmax;i++){
z=m1[i]-m2[i]+d;
if(z<0)
if(i==lmax-1)
z=z;
else{
d=-1;
z=10+z;
}
else
d=0;
rez[i]=z%10;
}
for(i=0;i<=lmax;i++)
if(rez[lmax]!=0)
printf("%d",rez[lmax]);
for(i=lmax-1;i>=0;i--){
printf("%d",rez[i]);
}
}
else{
lmax=l2;
for(i=0;i<=lmax;i++){
z=m2[i]-m1[i]+d;
if(z<0)
if(i==lmax)
z=z;
else{
d=-1;
z=10+z;
}
else
d=0;
rez[i]=z%10;
}
printf("\n");
if(rez[lmax]!=0)
printf("%d",rez[lmax]);
else
printf("-");
for(i=lmax-1;i>=0;i--){
printf("%d",rez[i]);
}
};
printf("\n\n*:\t");
for(i=0;i<255;i++){
rez[i]=0;
sout[i]=0;
r[i]=0;
}
k=0;
strcat(sout,"%");
sprintf(s,"%d",l1+l2+1);
strcat(sout,s);
strcat(sout,"s\n");
for(j=0;j<l2;j++){
z=0;
d=0;
for(i=0;i<l1;i++){
z=m1[i]*m2[j]+d;
d=z/10;
r[i]=z%10;
if(i==l1-1)
r[i+1]=d;
}
z=0;
d=0;
for(k=0;k<=l1;k++){
z=rez[k+j]+r[k]+d;
d=z/10;
rez[k+j]=z%10;
}
}
if(rez[lmax]!=0)
printf("%d",rez[l1+l2]);
else
printf(" ");
for(i=l1+l2-1;i>=0;i--){
printf("%d",rez[i]);
}
printf("\n\nDiv:\t");
char sdilene[255], sdiljnuk[255];
int dilene[255], diljnuk[255], chastka[255], temp[255];
int ldilene, ldiljnuk, cur_chastka, ltemp,cur_pos = 0;
int lrez, cur_chastk_pos = 0;
for (i = 0; i < 255; i++){
sdilene[i] = 0;
sdiljnuk[i] = 0;
dilene[i] = 0;
diljnuk[i] = 0;
chastka[i] = 0;
temp[i] = 0;
}
ldilene = convertation(s1,dilene);
ldiljnuk = convertation(s2,diljnuk);
ltemp = ldiljnuk;
cur_pos = 0;
for(i = 0; i < ltemp; i++)
temp[i] = dilene[i];
cur_pos = i;
while(cur_pos < ldilene){
cur_chastka = 0;
if(compare(temp,ltemp,diljnuk,ldiljnuk)==-1){
temp[ltemp++]=dilene[cur_pos];
cur_pos++;
}
while(compare(temp,ltemp,diljnuk,ldiljnuk)!=-1){
vidnimannja(temp,ltemp,diljnuk,ldiljnuk,rez,&lrez);
cur_chastka++;
for(i = 0; i <= lrez; i++){
temp[i] = rez[i];
rez[i] = 0;
}
ltemp = lrez;
}
chastka[cur_chastk_pos] = cur_chastka;
cur_chastka = 0;
cur_chastk_pos++;
}
for(i = 0; i < cur_chastk_pos; i++)
printf("%d",chastka[i]);
printf("\n\nMod:\t");
if(ltemp==0)
printf("0");
else
for(i = 0; i < ltemp; i++)
printf("%d",temp[i]);
printf("\n");
getch();
}
Висновок: Виконуючи цю лабораторну роботу я експериментально дав оцінку складності елементарних арифметичних функцій мов програмування типу Паскаль, забезпечив засобами мови Паскаль або Си емуляцію арифметичних операцій додавання, віднімання, множення i ділення натуральних чисел багатократної точності й оцінив їх складність.
.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора