Розробка алгоритмів та вибір оптимального алгоритму

2. Розробка алгоритмів та вибір оптимального алгоритму

При розробці алгоритму обчислення значення функції за допомогою інтерполяційної формули Бесселя будемо використовувати формулу яка описана в теоретичних відомостях.

Аналіз формули та прикладу, наведеного в першому розділі, показує що для обчислення значення функції необхідно обчислити  значеня кінцевих різниць а також значеннь q та р. Безпосереднє обчислення за формулою вимагає  операцій додавання (віднімання), n - операцій ділення та  - операцій множення. З врахуванням того, що час виконання операції множення та ділення відповідно в 1,14 та 2,33 рази більший за час виконання операції додавання (віднімання) при використанні математичного співпроцесора, загальна кількість операцій обчислення складає

Алгоритм можна побудувати таким чином, щоб спочатку обчислити всі всі знаменники поліному, а потім провести обчислення за основною формулою. В цьому випадку необхідно  комірок пам’яті.

Інший спосіб побудови алгоритму полягає в тому, щоб проводити обчислення знаменників поліному одночасно з обчисленнями за основною формулою виходячи з факторіалу. В цьому випадку для збереження значень необхідно лише n-1 комірок пам’яті.

Комплексний коефіцієнт ефективності Ке одного алгоритму в порівнянні з іншим можна обчислити за формулою

де Кч – коефіцієнт ефективності за часом виконання;

Кn – коефіцієнт ефективності за затратами пам’яті алгоритму.

Оскільки коефіцієнт ефективності за часом виконання алгоритму можна приблизно оцінити за кількістю арифметичних операцій алгоритму, то комплексний коефіцієнт ефективності описаних вище алгоритмів складає

Для випадку коли n=9

Блок-схеми описаних вище алгоритмів відповідно на рис 2.1 та рис 2.2. В даних алгоритмах вважається, що матриця A використовуються для збереження таблиці різниць, значення x, x0, n, q – однойменні змінні [6].

3. Приклад програми обчислення значення функції за допомогою інтерполяційної формули Бесселя

 

3.1 Інструкція користувача

Після виклику Pascal ABC із середовища Windows на екрані з'являється командне вікно середовища Pascal ABC.

Це вікно є основним у Pascal ABC. У ньому відображаються символи команд, що набираються користувачем на клавіатурі, результати виконання цих команд, текст програми, що виконується, а також інформація про помилки виконання програми, яка розпізнана системою.

Ознакою того, що програма Pascal ABC готова до сприйняття і виконання чергової команди, є наявність в останньому рядку текстового поля вікна миготливої вертикальної риски.

У верхній частині командного вікна (безпосередньо під заголовком Pascal ABC) розташований рядок меню, що складається з шести меню –Файл, Правка, Вид, Программа, Сервис, Помощь. Під головним меню розміщена панель інструментів з піктограмами, що дозволяють виконувати деякі найбільше часто використовувані операції.

1. Відкриття меню здійснюється натисненням миші. Щоб вибрати будь-яку команду меню, досить установити курсор на імені команди і натиснути ліву кнопку миші.

2. Текст програми міститься в одному файлі: файл основної програми з іменем kursach.pas. Для відкриття його необхідно вибрати у меню Файл команду Открыть (Відкрити), що відкриває діалогове вікно з переліком PAS- файлів поточної папки.

3. Вибір необхідного файлу з цього списку і наступне натискання кнопки OK приводить до появи вікна Редактора/Налагодження, який дає змогу не тільки коректувати програму, але і проводити її відладку. Запуск програми здійснюється вибором в меню Программа команди Выполнить, або натисненням клавіші F9.

4. В результаті запуску програми з’явиться командне вікно, в якому необхідно ввести коефіцієнти розширеної матриці. По завершенні введення значень в командному вікні буде виведенне значення функції в заданій точці.

3.2 Опис програми

Текст програми міститься у файлі kursach.pas, де описані всі змінні та присвоєні їм певні значення, необхідні для обчислення значення функції інтерполюванням за формулою Бесселя, а також власний процес обчислення методу. З метою ефективного використання пам’яті для збереження початкових значень системи, вони зберігаються в динамічній пам’яті, що дозволяє відводити під них місце динамічного розміру в залежності від кількості заданих даних.

Всі дані оператори утворюють саму основну програму, правила користування якої непотрібно перераховувати ─ вони звичайні (як і в будь-якій програмі), це дозволяє значно спростити користування даною програмою.

Файл містить описи структури методу та функцій, що використовуються основною програмою: опис змінних, введення початкових даних та обчислення таблиці різниць, визначення порядкового номеру х0 та обчислення q та р, обчислення за основною формулою, виведення результатів.

У програмі використовується оператор циклу for.

Сама програма є проста та зрозуміла у користуванні.

3.3 Лістинг програми

program kursach;

uses crt;

var

A:ARRAY [1..30,1..30] OF REAL;

i,i1,N,j,X0,f:longint;

H,x,P,pp,q,p1:REAL;

begin

clrscr;

write('Vvedit pochatkovui element ');

readln(p);

write('Vvedit k-t elementiv ');

readln(n);

write('Vvedit krock ');

readln(h);

for i:=1 to n do

begin

writeln('Vvedit Y[',i,'] v tochci ',p);

a[1,I]:=p; p:=p+h;

readln(A[2,I]);

end;

for i:=1 to n do

for j:=1 to n-i do a[i+2,j]:=a[i+1,j+1]-a[i+1,j];

writeln('Vvedit tochky v iakii bydemo chykatu znachennie fynkcii: ');

readln(X);

for i:=1 to n do if (a[1,i]-X<H) then x0:=i-1;

q:=(X-A[1,x0])/h;

pp:=q-(1/2);p1:=1;

p:=(a[2,x0]+a[2,x0+1])/2+pp*a[3,x0-1];

for i:=1 to n do begin

p1:=p1*(sqr(pp)-(sqr(2*i-1))/4);

f:=1;

for i1:=1 to 2*i do f:=f*i1;

p:=p+(p1/f*(a[2+2*i,n-i+1]+a[2+2*i,n-i+1])/2)+((p*p1)/(f*(2*i+1))*a[2+2*i,n-i+1]);

end;

writeln(p);

readln;

end.

3.4 Тестування програми

На рис. 3.1 подано екранні зображення в ході виконання програми для вихідних даних прикладу, наведеного в теоретичних відомостях.

Рисунок 3.1- Введення початкових значень та даних з таблиці та виведення кінцевого результату.

Висновки

1. Проведено теоретичний аналіз обчислення значення функції за допомогою інтерполяційної формули Бесселя та порівняння з іншими методами, який показав що цей метод є більш точним і простим.

2. Опираючись на теоретичну базу було створенно ефективний алгоритм обчислення значення таблично заданої функції за методом, коефіцієнт ефективності якого в 2,65 разу вищий за другий.

3. Реалізованно програму, написану на мові програмування Турбо Паскаль 7.0, що має зручний та наочний інтерфейс і максимально спрощує роботу.

4. Здійснено тестування програми, яке підтвердило її правильну та коректну роботу.

Перелік посилань

1.  Воробьева Г.Н., Данилова А.Н. Практикум по вычислительной математике. – М.: Высш. шк., 1990. - 187 с.

2.  Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. – М.: Наука, 1972. – 250 с.

3.  Волинець В.І. Конспект лекцій з курсів: Алгоритмічні мови і програмування. Обчислювальна техніка і програмування. - Вінниця, ВДТУ, 1996. – 42 с.

4.  Димидович Б.П., Марон И.А. Основы вычеслительной математики.– М.: 1970, – 240с.

5.  Волинець В.І., Ревенок В.І. Методичні вказівки до виконання лабораторних робіт з дисциплін: Алгоритмічні мови і програмування. Обчислювальна техніка і програмування. – Вінниця, ВДТУ, 1998. – 56 с.

6.  Волинець В.І., Ревенок В.І. Методичні вказівки до виконання практичних та контрольних робіт з дисциплін: Алгоритмічні мови і програмування та Обчислювальна техніка і програмування.– Вінниця, ВДТУ, 1998. – 40 с.

7.  Сердюченко В.Я. Розробка алгоритмів та програмування на мові Turbo Pascal. – Х.: Парітет, 1995. – 464 с.