Материал: 252_337

Завдання

1.Розробити та реалізувати у вигляді програми алгоритм Брезенхема для побудови відрізка.

2.Виконати завдання 1 для відрізка, паралельного осі абсцис. Результат виконання програми вивести на екран монітора.

3.Виконати завдання 1 для відрізка, паралельного осі орди­ нат. Результат виконання програми вивести на екран моні­ тора.

4.Виконати завдання 1 для довільного відрізка. Результат ви­ конання програми вивести на екран монітора.

5.Розробити та реалізувати у вигляді програми алгоритм Брезенхема для побудови кола.

6.Виконати завдання 5 для кола з радіусом, меншим за 1. Ре­ зультат виконання програми вивести на екран монітора.

7.Виконати завдання 5 для кола з довільним радіусом. Резуль­ тат виконання програми вивести на екран монітора.

8.Розробити та реалізувати у вигляді програми метод плаваю­ чого горизонту для реалістичної побудови поверхні.

9.Виконати завдання 8 для поверхні, що не має невидимих то­ чок. Результат виконання програми вивести на екран моні­ тора.

10.Виконати завдання 8 для поверхні, що має невидимі точки. Результат виконання програми вивести на екран монітора.

11.Виконати завдання 8 для поверхні, що має невидимі точки. Результат виконання програми вивести на екран монітора.

/Запитання для самоконтролю

1.У чому полягає проблема виведення зображення відрізка на ек­ ран монітора?

2.Як можна вирішити проблему виведення зображення відрізка на екран монітора?

3.Опишіть алгоритм побудови чотиризв'язної розгортки відрізка. Наведіть фрагмент програми, що реалізує цей алгоритм.

4.Опишіть алгоритм побудови восьмизв'язної розгортки відрізка. Наведіть фрагмент програми, що реалізує цей алгоритм.

5.Який алгоритм носить назву цілочислового алгоритму Брезенхема для восьмизв'язної розгортки відрізка у першому квад­ ранті?

6.Опишіть особливості цілочислового алгоритму Брезенхема. На­ ведіть фрагмент програми, що реалізує цей алгоритм.

7.У чому полягає ідея алгоритму Брезенхема для екранної побу­ дови кола?

8.Які рекурентні формули використовуються для екранної побудо­ ви кола за допомогою алгоритму Брезенхема?

9.Як визначається вибір точок, що належать колу, яке будується? 10. У чому полягає проблема виведення на екран монітора реаліс­

тичного зображення поверхні?

317

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

12.Яка площина називається картинною?

13.Як виконується проектування поверхні на картинну площину? Запишіть необхідні для цього перетворення.

14.Запишіть формули для переведення точки поверхні (х; у; z) у точ­ ку (х'; у').

15.Які співвідношення описують зворотне перетворення точки (х'; у') у точку (х; у; z)?

16.Як відбувається побудова видимих ліній поверхні? Сформулюй­ те алгоритм побудови графіка функції у = f(x, z).

17.На якій математичній платформі базується алгоритм, що ре­ алізує метод плаваючого горизонту?

18.Запишіть фрагмент реалізації метода плаваючого горизонту мо­ вою програмування. Обґрунтуйте окремі його моменти.

19.Які недоліки має метод плаваючого горизонту?

•

-

•

•

318

Ознайомлення з оптимізаційними методами розв'язування задач із різних розділів математики та алгоритмізації буде не­ повним, якщо ми не розглянемо ще один тип задач. На перший погляд для знаходження найкращого оптимального розв'язку необхідно застосувати повний перебір. Однак виявляється, що існує дещо штучний метод пошуку отпимального розв'язку, на який наштовхує знання одного з методів визначення коренів системи п лінійних рівнянь з п невідомими. Тому почнемо роз­ гляд алгоритмічного методу з попереднього ознайомлення з відомим в алгебрі методом виключення.

Розв 'язування системи лінійних рівнянь методом виключення

Для розв'язування системи п лінійних рівнянь з п невідоми­ ми розроблений метод Гауса, який базується на покроковому перетворенні рівнянь заданої системи з поступовим виключен­ ням невідомих.

Розглянемо систему п лінійних рівнянь з п невідомими:

" 2 1 ^ 1 + ^22*^2 , * • + а2пХп=Ь2>

Л А + а * 2 * 2 + - - + annXn=K-

Будемо розглядати лише такі перетворення системи, які не змінюють значень її розв'язків:

-якщо будь-яке рівняння системи помножити на деяке чис­ ло А, то це ніяк не вплине на значення розв'язків системи;

-якщо додати ліві та праві частини двох рівнянь і звести подібні члени, то це так само не змінить значень розв'язків сис­ теми.

Саме на цих міркуваннях і будуть ґрунтуватися наступні пе­

Помножимо перше рівняння на — і отримаємо такий його перетворений вигляд: а п

319

Якщо отримане рівняння помножити на - а 2 1 і додати його до другого рівняння системи, то друге рівняння буде мати та­ кий вигляд:

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

••+аІА=ьі;

х2+.

*»**£•

Процес перетворення заданої системи лінійних рівнянь до «трикутного» вигляду називають прямим ходом. Після такого перетворення зовсім нескладно знайти розв'язки системи. Для цього із останнього рівняння визначається хп, це значення підставляється у передостаннє рівняння, звідси знаходиться значення хп_х і т. д. Процес знаходження розв'язків системи називають зворотним ходом.

Застосування методу виключення для розв 'язування алгоритмічних задач

Після короткого екскурсу в розділ алгебри перейдемо до пи­ тань алгоритмізації. Розглянемо наступну задачу.

Нехай є деякий пристрій, що складається з послідовності п елементів, кожний з яких може знаходитися лише у стані 0 або 1. Є також п пристроїв керування, що мають можливість одночасно змінювати стан будь-яких k (1% k < п) елементів послідовності на протилежний. Вхідною інформацією є така: п - кількість еле­ ментів пристрою, для якого відомий початковий та кінцевий стан його елементів, та п пристроїв керування з вказівкою, на які еле­ менти вони можуть впливати. Визначити, якою мінімальною кількістю пристроїв керування можна перевести всі елементи за­ даного пристрою із початкового стану у кінцевий.

Наприклад, нехай задано пристрій, елементи якого у почат­ ковому стані мають такі значення: 0,1,1,0,1. Існують пристрої керування з такими значеннями: 0,1,1,0,1; 0,1,1,1,0; 1,0,0,1,1; 0,1,1,1,1; 1,0,1,1,0. Застосувавши існуючі пристрої

320

керування, необхідно заданий пристрій перевести у стан 0,0ДЛ,0.

Якщо застосувати п'ятий пристрій керування до стартового стану заданого пристрою, то отримаємо такий результат:

\0 1 1 0 1 - ^ 1 ^ 1 1 0 1 1 .

Основна ідея застосування методу виключення для розв'я­ зання поставленої задачі полягає у тому, що:

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

-парна кількість застосування пристрою керування, що впливає на і-й елемент, до і-го елемента заданого пристрою по­ вертає його у початковий стан;

-непарна кількість застосування пристрою керування, що впливає на і-й елемент, до і-го елемента заданого пристрою пе­ реводить його у протилежний стан.

Виходячи з вищезазначеного, можна зробити висновок, що для оптимізації алгоритму необхідно:

-виключити всі зайві застосування пристроїв керування щодо елементів заданого пристрою;

-працювати лише з тими елементами, що змінюють свої значення.

Перш ніж сформулювати алгоритм розв'язку задачі, розгляне­ мо і-й та у'-й пристрої керування. Позначимо відповідно а\ - fe-й елемент і-го пристрою, a a'k - k-й елемент j-то пристрою. Про­ аналізуємо, що відбуватиметься з fe-м елементом заданого пристрою, якщо застосувати до нього обидва зазначені при­ строї керування. Якщо а\ = a'k=l або а\ = а{ = 0, то стан k-то еле­ мента заданого пристрою залишиться незмінним. Якщо а\ = 0, a'k = 1 або а\ = 1, а{ = 0, стан /г-го елемента заданого пристрою зміниться на протилежний. Але можна поставити запитання: навіщо виконувати дві операції, застосовуючи до заданого пристрою обидва пристрої керування, якщо лише у другому ви­ падку стануться зміни? А чи не можна замінити два пристрої керування одним, у якому на fe-й позиції знаходитиметься 0, якщо значення а\ і а{ збігаються, і 1, якщо вони різні? При цьому таку саму заміну необхідно зробити і щодо інших відповідних елементів обох пристроїв керування. Після таких перетворень отриманий пристрій керування впливатиме на елементи заданого пристрою так само, як і два попередніх.

Наступний крок міркувань наводить на думку, що, застосо­ вуючи один із пристроїв керування до інших, можна змінювати стан їх елементів і при цьому результат їх впливу на послідов­ ність елементів заданого пристрою дасть правильний результат.

321