Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Алгоритм Кастла-Пітвея

⇐ ПредыдущаяСтр 32 из 109Следующая ⇒



Цей алгоритм набагато менш ефективний з обчислювальної крапки зрені, чим алгоритм Брезенхема, однак має гарну математичну структуру. Він заснований на ідеї, схожої з відомим алгоритмом Евкліда знаходження Найбільшого Загального Дільника двох натуральних чисел [19].

Будемо працювати з рядками, що кодують послідовність зафарбування (тобто складаються із символів s і d, певних вище).

Визначимо дві операції над такими рядками:

- - конкатенація рядків, наприклад

- - "переворот" рядка, наприклад

// Координати кінців відрізка - (0,0) і (a,b)y = b;x = a - b; m1 = "s";m2 = "d"; while( x \ne y ){ if( x > y ) { x = x - y; m2 = m1 ~ m2; } else { y = y - x; m1 = m2 ~ m1; }}

Лістинг 6.3. Алгоритм Кастла-Пітвея

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

Поделиться:

Дата добавления: 2015-04-05; просмотров: 253; Мы поможем в написании вашей работы!; Нарушение авторских прав

⇐ Предыдущая27282930313233343536Следующая ⇒
lektsii.com - Лекции.Ком - 2014-2025 год. (0.412 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты