Задача про рюкзак. Математична модель задачі про рюкзак
У загальному вигляді задача про рюкзак (в літературі часто зустрічається і інша її назва, а саме задача про ранець) формулюється в такий спосіб: є рюкзак певного об'єму і необмежена кількість предметів. Для кожного предмета відомий його об'єм (вага) і цінність (вартість, ефективність). У рюкзак можна покласти ціле число предметів різного типу. Мета полягає в тому, щоб сумарна цінність всіх, що знаходяться в рюкзаку, предметів була максимальна, а їх об'єм (вага) не перевищував заданої величини. До подібного формулювання може бути зведена задача максимального використання вантажопідйомності рухомого складу, вантажомісткості судна, автомобіля і тому подібне. Таке завдання часто виникає при виборі оптимального управління в економіко-фінансових областях (наприклад розподіл бюджету відділу по проектам).
Ілюстрація задачі про ранець
Запишемо математичну модель задачі такого типу. Для цього, припустимо, що розглядається скінченна множина предметів 
, для кожного з яких відома вартість 
і визначений об'єм 
. Також є рюкзак об'ємом 
. Необхідно упакувати рюкзак таким чином, щоб загальна вартість запакованих предметів була якнайбільшою, а їх загальний об'єм не перевищував величини . Традиційно вважають, що , , — цілі невід'ємні числа.
Побудов кривої Безьє в середовищі програмування delphi
У представленій delphi-програмі, за допомогою досить простого інтерфейсу, користувачеві надається можливість задавати, переміщати та видаляти (з використанням миші) контрольні точки, за якими здійснюється прорисовка кривої Безьє (для цього необхідно щоб користувач задав хоча б три точки).
Головне вікно проекту "Побудова кривої Безьє"
На рисунку що міститься вище, показаний зовнішній вигляд запущеної програми. Як видно з рисунка, у верхній частині вікна містяться елементи управління, за допомогою яких, власне, і здійснюється побудова кривої. Розглянемо призначення кожного з них більш детально.
Криві Безьє. Основні поняття та властивості кривих Безьє
Векторні зображення складаються з контурів. Контури складаються із сегментів, обмежених вузлами. З декількох таких сегментів можна скласти, практично, будь-яку фігуру. Для опису контурів у програмах векторної графіки застосовують розроблені французьким математиком П'єром Безьє параметричні поліноміальні криві. Відмітимо, що криві та поверхні Безьє були використані у шістдесятих роках компанією «Рено» для комп'ютерного проектування форми кузовів автомобілів. На сьогодні вони широко використовуються в комп'ютерній графіці, автоматизованих системах управління виробництвом тощо. Квадратичні криві Безьє використовуються в шрифтах TrueType.
За заданим масивом вершин 
крива Безьє степеня 
визначається за формулою:
де 
— базисні функції кривої Безьє, також відомі як поліноми Берштейна, 
.
На рисунку що міститься нижче, зображено графіки вагових коефіцієнтів 
кривої Безьє при 
.
Вагові функції Безьє-Берштейна при m = 3
Зауваження: деякі з властивостей поліномів Берштейна суттєво впливають на поведінку кривих Безьє. Наведемо основні з них: многочлени Бернштейна набувають невід'ємних значень; в сумі многочлени Берштейна дають одиницю, тобто для них виконується умова (2); поліноми Берштейна не залежать від вершин масиву 
, а залежать лише від кількості точок у ньому.
Побудова кривої Гільберта в середовищі програмування delphi
У даній статті розглядається процес створення об'єктів фрактальної графіки засобами Delphi, на прикладі побудови кривої Гільберта, від першого по сьомий порядок включно. Одним з основних плюсів при використанні розглядуваного delphi-проекту є простота інтерфейсу та можливість наочно спостерігати зображення фрактальної кривої.
Головне вікно проекту "Побудова кривої Гільберта"
Побудова кривої здійснюється за допомогою кнопки «Побудувати криву Гільберта» (компонент типу TButton) та поля вибору кількості ітерацій необхідних для її побудови (компонент типу TSpinEdit). Відмітимо, що на рисунку, що міститься вище, зображено діалогове вікно програми, в якому виводиться крива Гільберта п'ятого порядку.
Крива Гільберта. Побудова кривої Гільберта за допомогою рекурсії
У 1890 році італійський математик Джузеппе Пеано відкрив плоску криву з дивовижною властивістю заповнення простору: крива заповнювала одиничний квадрат і проходила через кожну його точку 
щонайменше один раз.
Крива Пеано заснована на поділі кожної сторони одиничного квадрата на три рівні частини, які ділять його на дев'ять менших квадратів. Крива проходить ці дев'ять квадратів в певному порядку. Потім кожен з дев'яти менших квадратів аналогічно ділиться на дев'ять частин, і крива модифікується таким чином, щоб обійти всі частини в певному порядку.
У 1891 році німецький математик Давид Гільберт відкрив варіант кривої Пеано, який базується на розподілі кожної з сторін одиничного квадрата на дві рівні частини, що ділить квадрат на чотири менші частини. Після цього, кожен з чотирьох одержаних квадратів, в свою чергу, ділиться на чотири менших квадрата і так далі. Зазначимо, що на кожній стадії такого поділу Гільберт будував криву, яка обходила всі наявні квадрати. Крива Гільберта (яку іноді називають кривою Пеано-Гільберта) являє собою граничну криву, отриману в результаті такої побудови.
Побудова кривої Коха в середовищі програмування delphi
В даному параграфі міститься delphi-програма з вихідним кодом, яка демонструє приклад побудови однієї з найвідоміших фрактальних кривих, а саме криву Коха. Для того, щоб побудувати дану криву, достатньо скористатись кнопкою «Побудувати криву Коха» (компонент типу TButton), попередньо, в компоненті типу TSpinEdit, задавши кількість ітерацій необхідних для її побудови (порядок кривої Коха).
Головне вікно проекту "Побудова кривої Коха"
Зауваження: delphi-проект реалізує процес побудови кривої Коха від нульового до десятого порядку включно. Проте, даний процес можна продовжити і для більш високих ітерацій. Для цього достатньо задати необхідне значення для властивості MaxValue компонента TSpinEdit.
Поняття фрактала. Крива Коха та алгоритм її побудови
Поняття фрактала з'явилося в кінці сімдесятих років минулого століття і стало широко застосовуватися математиками і комп'ютерними художниками. Фрактали знайшли широке застосування в комп'ютерній графіці завдяки компактності математичного апарату, необхідного для їх відтворення на екрані комп'ютера.
Слово фрактал походить від латинського fractus і в перекладі означає «cкладений із фрагментів». Цей термін запропонований французько-американським математиком Бенуа Мандельбротом у 1975 році для позначення самоподібних структур.
У комп'ютерній графіці використовують таке означення фрактала: фракталом називається геометрична фігура, яка складається з частин, які в певному розумінні подібні за формою на всю фігуру, тобто це геометрична фігура, в якій один і той самий фрагмент повторюється при кожному зменшенні масштабу (частина об'єкта схожа на сам об'єкт). Тобто, характерною рисою фрактала є самоподібність відносно масштабу (наприклад, гірський камінь має такі ж обриси, як і гірський хребет).
Загрузка ...