ОБЧИСЛЮВАЛЬНА СКЛАДНІСТЬ АЛГОРИТМІВ І ПРОГРАМ НА ПРИКЛАДІ ЗАДАЧІ ПРО ЩАСЛИВІ КВИТКИ

Мета та завдання Мета – дослідити особливості розвязання проблеми розрахунку алгоритмічної складності, знайти оптимальний варіант розрахунку алгоритмічної складності для даної задачі. Завдання: Сформувати уявлення про алгоритми та їх складність; Зясувати відмінності теоретичного та експериментального визначення складності алгоритму; На прикладах (задача про щасливі квитки) розглянути процедуру визначення алгоритмічної складності та вибору алгоритму відповідно складності.

Основні поняття Алгоритм – це обчислювальний процес, що починається з обробки деякої сукупності можливих даних і спрямований на отримання визначених цими даними результатів. Алгоритмічна складність - це поняття теорії складності обчислень, оцінка ресурсів (частіше часу), необхідних для виконання алгоритму. Класи складності - це множина задач розпізнавання, для розвязку яких існують алгоритми, схожі за обчислювальною складністю. Види алгоритмічної складності: логічна, статична,тимчасова, ємнісна,асимптотична, експериментальна;

Задача про щасливі квитки Дані трамвайні білети номерами від до Знайти всі щасливі квитки та вивести на екран їх кількість. Математична модель: Щасливим вважається квиток, сума трьох перших цифр якого дорівнює сумі останніх. Тобто нам потрібно розкласти шестизначне число на цифри. Приблизно такий вигляд буде мати число G: G=100000*a *b *c + 100*d +10e +f.

Три варіанти розв'язку 1) const Max=9; var q,w,e,r,t,y:integer; levo,pravo:integer; begin for q:=0 to Max do for w:=0 to Max do for e:=0 to Max do for r:=0 to Max do for t:=0 to Max do for y:=0 to Max do begin levo:=q+w+e; pravo:=r+t+y; if(levo = pravo) then begin inc(s); end; write (s); end. 2) var n,n1,n2,i,j,count:Longint; s:string; begin count:=0; for j:=0 to do begin n:=j; n1:=0;n2:=0; for i:=1 to 6 do begin if i<=3 then n1:=n1+n mod 10 else n2:=n2+ n mod 10; n:=n div 10; end; if (n1=n2) then begin Str(j,s); for i:=1 to 6-length(s) do s:='0'+s; count:=count+1; end; writeln('Всего ', count); end. 1)uses crt; var m,n,s,i,q,sum:integer; k: array[1..14] of integer; function c(m,n:integer):longint; begin if m>n then c:=0; if (m=0) or (m=n) then c:=1 else if n-m<m then c:=c(n- m,m) else c:=c(m-1,n-1)+c(m,n-1); end; begin clrscr; k[1]:=1; for i:=2 to 10 do begin s:=c(2,i+1)+1; k[i]:=s; end; k[11]:=(c(2,12)+1)- (3*c(2,2)); q:=3; for i:=12 to 14 do begin s:=(c(2,i+1)+1)- (3*(c(2,q)+1)); k[i]:=s; q:=q+1; end; sum:=0; for i:=1 to 14 do begin sum:=sum+sqr(k[i]); end; writeln('Biletu: ', 2*sum); end.

Результати трьох рішень та порівняння швидкодії програми за часом

Висновок: Існує безліч кількість способів розрахувати алгоритмічну складність. Їх треба вибирати відповідно складеної програми. Також на прикладі цієї задачі було зрозуміло, що правильних рішень може бути безліч. Важливо настільки граматично правильно скласти алгоритм, щоб сама програма була швидко - дієвою та приносила вірний результат. Наша задача була простим прикладом, тому для неї використовувалась експериментальна складність, але для більш складних задач використовуються інші великі формули. Алгоритмічна складність допомагає економити час та пам'ять компютера – це є найважливішим для програміста та його замовника, бо завжди потрібні чіткі швидкі результати, які не будуть займати багато простору памяті.