Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритму вибіркових переміщень
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Курсовий проект
Предмет:
Інші
Група:
ВП
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки, молоді та спорту України
Національний університет «Львівська політехніка»
Курсовий проект
на тему:
«Дослідження алгоритму вибіркових переміщень»
ЗМІСТ
1. ВСТУП
2. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ
2.1. Поняття комбінаторного розміщення елементів
2.2. Ідеальні кільцеві в’язанки як одновимірна нееквідистантні структура
2.3 Основні відомості про алгоритм вибіркових переміщень.
3. СИСТЕМНИЙ АНАЛІЗ
3.1. Аналіз проблеми
3.2. Основні пункти методу
3.3. Критерій заповнення двовимірних нееквідистантних структур
4. ПОБУДОВА ІКВ МЕТОДОМ ВИБІРКОВИХ ПЕРЕМІЩЕНЬ
5. ПРОГРАМНА РЕАЛІЗАЦІЯ
5.1. Постановка задачі
5.2. Середовище розробки програми
5.3. Опис програми
ВИСНОВКИ
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
ДОДАТОК
1.ВСТУП
Нехай задана множина ={}, елементів і задана операція «#», що здійснюється над елементами цієї множини. Тоді n- в’язанкою за операцією «#» називається впорядкована сукупність n – елементів, кожен з яких утворюється застосуванням заданої операції між наборами послідовно розміщених елементів даної сукупності.
Отже можна вважати, що n- в’язанка породжує множину , де , - новоутворена множина. Кожен з елементів має не менше 2-х полюсів, які є його умовними входами і виходами і вказують на порядок виконання операції.
Порядок n- в’язанки – це кількість n базових елементів, що входять до її складу. Кількість новоутворених n- елементів визначається її структурою та порядком.
Одновимірна n- в’язанка утворюється на упорядкованій сукупності елементів, які є одновимірними числовими об’єктами (числа, відрізки), дво та більше вимірна відповідно на сукупності елементів, які є відповідно дво або більше вимірними (наприклад вектори t- вимірного простору, де t).
Одновимірні в’язанки складаються з чисел, багатовимірні – з упорядкованих числових наборів:
1 2 10 19 4 7 9 5
Рис.1 Одновимірна числова в’язанка
Рис.2 Двовимірна числова в’язанка
Числова в’язанка, утворена з елементів, які у свою чергу також є в’язанками, називається комбайном в’язанок, а їх упорядкована сукупність – гіперкомбайном.
Числові в’язанки поділяються на ідеальні та неідеальні. Оскільки алгоритм вибіркових переміщень використовується тільки для побудови ідеальних кільцевих в’язанок(ІКВ), то саме їх ми надалі розглянемо детально.
2. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ
2.1. Поняття комбінаторного розміщення елементів
В комбінаториці, розміщенням із n елементів по m, або впорядкованою (n, m) вибіркою із множини M (потужність n, m≤n) називають довільний кортеж що складається із m попарно відмінних елементів. Розміщення можна розглядати як різнозначну функцію f: , для якої .
Кількість розміщень із n по m позначається як або P(n,m) і обчислюється за наступною формулою:
Розміщення з повтореннями
Розміщенням з повтореннями із n елементів по m або дворядкованою (n, m) вибіркою з поверненнями називається довільний кортеж елементів множини M, для якого |M| = n.
Кількість можливих розміщень з повтореннями із n елементів по m дорівнює n піднесене до степеня m:
Наприклад, із цифр 1, 2, 3, 4 можна скласти трьохзначних числа.
Поняття «ІКВ» та його визначення.
Ідеальна кільцева в’язанка – це упорядкована циклічна послідовність чисел
,
на якій всі можливі кільцеві суми, які утворюють значення чисел натурального ряду від 1 до Sn=n(n — 1). Кільцевою сумою називається сума будь-якої кількості (від 1 до n-1) послідовно розміщених елементів циклічної n-послідовності. Наприклад, якщо вибрати циклічну послідовність з чисел 1,4,2, то з них можна утворити натуральний ряд чисел від 1 до =7:
1=1;
2=2;
3=2+1;
4=4;
5=4+1;
6=2+4;
7=1+4+2;
Цей ряд можна продовжити, обираючи перший елемент для початку відліку та обходячи кільцеву схему більше одного разу, наприклад:
8=1+4+2+1;
Отже, наведена вище циклічна числова послідовність є ідеальною кільцевою в’язанкою.
Рис.3 Ідеальна кільцева в’язанка з елементів 1,4,2.
Класифікація ІКВ.
За кількістю повторень кожного з реалізованих на в'язанці числових значень ІКВ поділяють на прості та багатократні. Числові значення простих ІКВ не повторюються (R=1), а багатократних повторюються R>1 разів.
Залежно від структурних особливостей в’язанки поділяються на розімкнені та замкнені. До розімкнених в’язанок належать нерозгалужені лінійки і розгалужені без замкнених ланок. Замкнені містять замкнені ланки, які, у свою чергу, можуть утворювати в’язанки без розгалужень чи з розгалуженнями у вигляді лінійок або замкнутих ланок або, врешті, з розгалуженням що включають обидва види ланок. Двовимірні ідеальні в’язанки можуть утворювати впорядковані послідовності елементів, відносне розміщення кожного з яких задається двома вимірами на площині, а багатовимірні – відповідним числом вимірів простору.
Умови існування деяких ІКВ
Теорема 1. Простих ідеальних лінійок без розгалужень вище 3-го порядку не існує.
Теорема 2. Багатократних ідеальних лінійок без розгалужень вище другого порядку не існує.
Теорема 3. Простої ідеальної в’язанки 4-го порядку без замкнених ланок не існує.
2.3 Основні відомості про алгоритм вибіркових переміщень.
Описаний алгоритм реалізує загальний підхід до рішення задачі генераціі повних сімей простих та багатократних одновимірних числових лінійок-в'язанок.
Алгоритм складається з наступних кроків:
Крок 1. За значеннями і обчислюється оцінка найбільшого граничнього значення суми ЧЛВ при за формулою (2.22) і оцінка найбільшого значення суми ЧЛВ відносно суми ЧКВ за формулою (1.2);
Крок 2. Заготовлюється масив із комірок, пронумерованих у зростаючому порядку;
Крок 3. В перші комірок масиву записується число, з якого починається відлік в ЧЛВ, в -у - наступне, в решту заносяться нулі;
Крок 4. Перший раз число визначається як збільшене на одиницю найбільше число найкоротшого ряду послідовності чисел, утворенного на множині сум, які знайдені на всіх окремих послідовностях, що належать масиву. Наступний раз число з тим самим значенням визначається як збільшене на одиницю наступне за найбільшим числом найкоротшого ряду послідовності чисел, поки сума усіх чисел масиву менша за . При існуючих вільних комірках масиву число записується у вільну комірку з найменшим порядковим номером і обчислюється нове значення суми усіх чисел масиву; у випадку коли виконується крок 5, а при - виконується крок 7;
Крок 5. Обчислюється нове значення суми елементів масиву ЧЛВ . При існуючих у масиві вільних комірках знаходяться всі суми на всіх послідовностях, а при їх відсутності - всі лінійні сумі на єдиній послідовності:
a) якщо кожна зі знайденних сум зустрічається не більше разів і є вільні комірки, то здійснюється перехід до кроку 4. При відсутності вільних комірок і при виконанні умови, що нове значення суми не більше попереднього, отримується варіант ЧЛВ, після чого виконується крок 7. В іншому випадку виконується крок 6;
б) якщо хоча б одна зі знайденних сум з'являється більше разів, то виконується крок 6;
Крок 6. Знаходиться найбільше число , потім визначається чи є вільний номер комірки з номером більшим ніж той, де розташоване число ; якщо така комірка існує, то з комірки з меншим номером число переноситься у вільну комірку з більшим номером, після чого виконується крок 5; в протилежному випадку виконується крок 7.
Крок 7. Звільняється комірка з числом і виконується крок 6. Ознакою закінчення обчислень при побудові повної сім'ї ЧЛВ служить поява числа, з якого починається відлік в ЧЛВ в комірці при умові його відсутності в попередніх комірках для непарних значень і аналогічно в комірці для парних значень .
Ознаки закінчення обчислень сформульовані з врахуванням властивості алгоритму та отримані із умови виключення повторень ситуацій, при яких одна і та ж послідовність чисел з’являється як дзеркальне відображення раніше отриманої послідовності чисел ЧЛВ. Враховується, що в ЧЛВ повинно міститися точно не більше однакових сум, а також те, що елементи ЧЛВ, які знаходяться в комірках з меншими порядковими номерами, по черзі переміщаються в комірки з більшими порядковими номерами в міру поступового зменшення числових значень цих елементів. Це й забезпечує перебір всіх можливих без винятку варіантів ЧЛВ.
Наведемо приклад побудови ЧЛВ мінімальної довжини порядку кратності , починаючи з числа 1. Процес обчислень для зручності зобразимо у вигляді ланцюжка послідовних кроків перетворень над масивом чисел:
(1,1,2,3)-(1,1,2,0)-(1,1,0,2)-(1,1,3,2)-(1,1,0,2)-(1,1,0,0,)-(1,0,1,0)-(1,2,1,2)-(1,0,1,0)-(1,0,0,1)-(1,2,2,1)-(1,0,0,1)-(0,1,1,0)-(2,1,1,0)-(0,1,1,2)-(0,1,1,0)-(0,1,0,1)-(2,1,0,1)-(0,1,2,1)-(0,1,0,1)-(0,0,1,1).
Виділена послідовність (1,2,2,1) утворює єдину існуючу ЧЛВ мінімальної довжини .
Алгоритм покладено в основу розробки комплексу програм для синтезу повних сімей ЧЛВ із заданими параметрами [35, 56].
Для оцінки ефективності алгоритму число варіантів перебору підраховується як кількість нетотожніх перестановок на кожному розбитті множини [66], елементами якої є числа ЧЛВ:
, (4.1)
де - порядок ЧЛВ;
- верхня гранична оцінка мінімальної довжини ЧЛВ, коли відлік починається з числа 1 за формулою (2.22).
Для - кратних ЧЛВ порядка , де враховується поява додаткових тотожних перестановок як результат взаємозаміни однакових частин в'язанки, зокрема одиниць (одна з них є фіксованою).
, (4.2)
де - порядок ЧЛВ кратності ;
- верхня гранична оцінка мінімальної довжини ЧЛВ кратності , коли відлік починається з числа 1. Не може бути більше ніж значення суми ЧКВ за формулою (1.2).
Із залежностей (4.1) і (4.2) видно, що зі збільшенням порядка число варіантів перебору різко зростає, а збільшення кратності має зворотну дію, тому машинний синтез повних сімей ЧЛВ без упорядкованого перебору варіантів можливий лише для ЧЛВ малих порядків.
Аналогічно, як для одновимірних ЧЛВ, розроблено алгоритм вибіркових переміщень "з пропусками" і для багатовимірних ЧЛВ. Робота починається за наступним алгоритмом (на прикладі двовимірної ЧЛВ, див. блок-схему алгоритму вибіркових переміщень побудови двовимірних числових лінійок-в'язанок на рис. 3.2.):
Крок 1. Вибирається елемент двовимірної ЧЛВ (ДЧЛВ) з координатами ( - номер рядка, що змінюється в межах від 1 до , - номер стовпчика, що змінюється в межах від 1 до ).
Крок 2. Знаходяться всі можливі різниці між координатами і вибраного елемента ДЧЛВ з усіма раніше вибраними координатами елементів.
Крок 3. Порівнюються обчислені різниці координат і з раніше знайденими різницями координат елементів у відповідних масивах різниць координат. Якщо хоча б одна пара різниць координат збігається, біжучому значенню кількості різниць присвоюється значення .
Крок 4. Поточне значення збільшується на 1, і масивам координат рядків та координат стовпчиків відповідно присвоюються координати і . Значенню присвоюється значення .
Крок 5. Перевіряється умова , де - максимальна кількість елементів ДЧЛВ з раніше знайдених варіантів. Якщо ця умова задовольняється, то значенню присвоюється значення і отримується один із варіантів ДЧЛВ.
Крок 6. Вибираються координати і останнього елемента ДЧЛВ з відповідних масивів.
Крок 7. Якщо задовольняється умова , , ( - половина кількості стовпчиків ПЧВ), то закінчуються обчислення.
Крок 8. Порівнюється координата з числом стовпців ДЧЛВ. Якщо , то порівнюються координата з числом рядків ДЧЛВ. Якщо , то кількість елементів ДЧЛВ зменшується на 1, кількість різниць зменшується на , і здійснюється перехід на крок 6.
Крок 9. Значення зменшується на 1, - на і здійснюється перехід до вибору наступного елемента ДЧЛВ на крок 1.
Алгоритм вибіркових переміщень "з пропусками" покладено в основу створення програм синтезу одно- та багатовимірних ЧЛВ, які входять до складу комплексу програм (комплекс програм наведений в звіті по госпдоговірній темі №4904, державний регістраційний №01890077490). В додатках приведені приклади роботи алгоритму для двовимірних ЧЛВ з параметрами .
Описаний алгоритм успішно справляється з задачами, пов'язаними з побудовою одно- і багатовимірних ЧЛВ невисоких порядків. Основні переваги алгоритму - його простота і можливість широкого спектру удосконалень для синтезу ЧЛВ з різними характеристиками. Дослідження алгоритму вказує на те що основним фактором, який обмежує його ефективність, є перебір великого числа варіантів на послідовних перестановках елементів ЧЛВ. У зв'язку з цим виникає проблема скорочення числа варіантів перебору, яка в частково розв'язується за алгоритмом асиметричних розгалужень "з пропусками".
3. СИСТЕМНИЙ АНАЛІЗ
3.1. Аналіз проблеми
Найпростішою структурною організацією елементів, що утворює математичний об`єкт під назвою “в’язанка”, є одновимірна упорядкована послідовність Kn чисел k1, k2, …, ki, …, kn:
Kn=(k1, k2, …, ki, …, kn).
З погляду постановки задачі синтезу та дослідження оптимальних комбінаторних моделей особливий інтерес викликають в’язанки з кільцевою структурою, елементами яких є цілі додатні числа, а суми на кільцевій послідовності вичерпують значення чисел натурального ряду від 1 до суми Sn=k1+k2+…+ki+…+kn усіх чисел цієї послідовності. Така числова конструкція називається "ідеальною кільцевою в’язанкою", або скорочено ІКВ.
Наприклад, якщо обрати упорядкований ряд (1, 4, 2) як кільцеву послідовність чисел, то легко перевірити, що всі кільцеві суми цієї послідовності вичерпують натуральний ряд чисел від 1 до Sn=7:
1=1, 2=2, 3=2+1, 4=4, 5=1+4, 6=4+2, 7=1+4+2.
3.2 Основні пункти методу.
1. За значеннями і обчислюється оцінка найбільшого граничнього значення суми ЧЛВ при за формулою (2.22) і оцінка найбільшого значення суми ЧЛВ відносно суми ЧКВ за формулою (1.2);
2. Заготовлюється масив із комірок, пронумерованих у зростаючому порядку;
3. В перші комірок масиву записується число, з якого починається відлік в ЧЛВ, в -у - наступне, в решту заносяться нулі;
4. Перший раз число визначається як збільшене на одиницю найбільше число найкоротшого ряду послідовності чисел, утворенного на множині сум, які знайдені на всіх окремих послідовностях, що належать масиву. Наступний раз число з тим самим значенням визначається як збільшене на одиницю наступне за найбільшим числом найкоротшого ряду послідовності чисел, поки сума усіх чисел масиву менша за . При існуючих вільних комірках масиву число записується у вільну комірку з найменшим порядковим номером і обчислюється нове значення суми усіх чисел масиву; у випадку коли виконується крок 5, а при - виконується крок 7;
5. Обчислюється нове значення суми елементів масиву ЧЛВ . При існуючих у масиві вільних комірках знаходяться всі суми на всіх послідовностях, а при їх відсутності - всі лінійні сумі на єдиній послідовності:
a) якщо кожна зі знайденних сум зустрічається не більше разів і є вільні комірки, то здійснюється перехід до кроку 4. При відсутності вільних комірок і при виконанні умови, що нове значення суми не більше попереднього, отримується варіант ЧЛВ, після чого виконується крок 7. В іншому випадку виконується крок 6;
б) якщо хоча б одна зі знайденних сум з'являється більше разів, то виконується крок 6;
6. Знаходиться найбільше число , потім визначається чи є вільний номер комірки з номером більшим ніж той, де розташоване число ; якщо така комірка існує, то з комірки з меншим номером число переноситься у вільну комірку з більшим номером, після чого виконується крок 5; в протилежному випадку виконується крок 7.
7. Звільняється комірка з числом і виконується крок 6. Ознакою закінчення обчислень при побудові повної сім'ї ЧЛВ служить поява числа, з якого починається відлік в ЧЛВ в комірці при умові його відсутності в попередніх комірках для непарних значень і аналогічно в комірці для парних значень .
4. ПОБУДОВА ДВОВИМІРНИХ ІКВ
Рис. 4.1. Блок-схема алгоритму побудови двовимірної ЧЛВ з найбільшим заповненням
5. ПРОГРАМНА РЕАЛІЗАЦІЯ
5.1. Постановка задачі
Сьогодні є дуже багато готових систем та пакетів. Однак будь-який пакет чи програма з моменту своєї появи морально старіє, тобто з'являються нові пропозиції щодо поліпшення їхніх можливостей, а самі задачі трансформуються у нові, наперед не передбачені.
Виходом з цієї ситуації є самостійна розробка програм для розв'язування конкретних задач. Важливими у цьому випадку є навики та досвід програміста, його вміння складати ефективні та надійні програми.
Програма написана в середовищі С. Додаткові компоненти не використовувалися — лише стандартні. Програма працює під наступними операційними системами: Windows 95, Windows 98, Windows ME, Windows NT, Windows 2000, Windows XP, Windows Vista, Windows 7.
Програма призначена для створення одновимірних ІКВ за заданими значеннями n і R.
Підготовка і організація вхідних даних виконується користувачем.
5.2. Середовище розробки програми
Для написання заданої програмної реалізації було вирішено скористатися мовою програмування C.
Як середовище програмування було вибрано операційна система Microsoft Windows 7 Ultimate.
Переваги вибраного середовища:
Використання мови С дозволяє зробити відкомпільований модуль досить швидким.
Велика кількість існуючих програмних бібліотек на мові С для організації обчислень і проектування користувацького інтерфейсу.
Щоб переконатись в правильності виконання програми, її потрібно неодноразово протестувати. Для тестування даної програми я використовувала різні вхідні дані.
5.3. Опис програми
Написана на мові програмування С.
Може виконуватися під керуванням операційних систем Windows 95/98/NT/2000/XP/Vista/7.
Програмна реалізація має модульну структуру.
Вхідні дані: параметри n і R.
Вихідні дані: усі можливі одновимірні ІКВ за заданими параметрами.
Дана програма дозволяє:
Задати вручну параметри для побудови одновимірної ідеальної кільцевої в’язанки.
2. Отримати всі можливі ІКВ при заданих користувачем параметрах
Висновки
Під час роботи над курсовим проектом було розроблено програмний продукт, який дозволяє за заданими параметрами програмно будувати одновимірні ідеальні кільцеві в’язанки методом вибіркових переміщень. Цей алгоритм досить простий у застосуванні і не потребує довгого часу роботи програмного продукту для отримання результатів, у тому і є його найбільша перевага. У програмі передбачені всі можливі помилки користувача, на них відбуваються відповідні реакції.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
А.с. 1377942 СССР. Разреженная неэквидистантная фазированная антенная решетка / Копилович Л.Е., Содин Л.Г. (СССР). 1988. Бюл. №8.
Альберт А. А. Конечные поля // Кибернетический сб. 1966. Вып. 3. С. 7-49.
Архангельский А. Я. C++ Builder 6. Справочное пособие. Кн. 1. Язык С++. — М.: ООО «Бином-Пресс», 2002 г.
Шпак З.Я Програмування мовою С.Видання друге, доповнене – Львів: Видавництво Львівської політехніки, 2011.
Методичні вказівки до курсової роботи з дисципліни «Проблемно-орієнтовані мови програмування»/ Укл. З.Я.Шпак – Львів: Видавництво Національного університету «Львівська політехніка», 2004.
ДОДАТОК
ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ ВИБІРКОВИХ ПЕРЕМІЩЕНЬ
#include<stdio.h>
#include<conio.h>
#define N 50
void p3(void);
void p4(void);
void p5(void);
void p6(void);
int MyFunk(int *,int, int);
int ar[250],k=0;
int n,R,Sn,i,mas[N];
int Imax,Iv,B,lich;
void main(void){
puts("vvedit` n<50,R");
scanf("%d",&n);
scanf("%d",&R);
if(R>n)
puts("\n ERROR!!!");
//1
Sn=n*(n-1)/R+1;
printf("\n\n Sn=%d",Sn);
//2
i=0;
while(i<R){
mas[i]=1;
i++;}
mas[i]=2;
i++;
//int i=2;
while(i<n){
mas[i]=0;
i++;
}
mas[i]=42;
//mas[i]='*';
p3();
fflush(stdin);
getchar();
}
void p3(void){
int sum=0,A,C;
i=0;
int max;
//A=mas[findmax(mas,n)]+2;
for(i=0,lich=0;i<n;i++)
if(mas[i]==0)
lich++;
for(i=0;i<n;i++)
sum+=mas[i];
i=0;
if(mas[n-1]==0)
while(mas[i]>0)
i++;
A=mas[0]+mas[i]+1;
if(k%2!=0)
for(i=0;i<n-1;i++){
if(mas[i]>mas[i+1])
A=mas[i]+1;
else
A=mas[i+1]+1;
}
k++;
if(lich>=2){
for(i=0;mas[i]!=0;i++)
;
mas[i]=A;
}
sum=0;
for(i=0;i<n;i++)
sum+=mas[i];
if(lich==1){
// for(i=0;i<n;i++)
// if(mas[i]==0)
// mas[i]=A;
for(i=0,sum=0;i<n;i++)
sum+=mas[i];
C=A+sum;
if(C==Sn)
{ for(i=0;i<n;i++)
if(mas[i]==0)
mas[i]=A;
p4();
}
else
p5();
}
if(sum<=Sn)
p4();
if(sum>Sn)
p6();
}
void p4(void){
//puts("\n");
//for(i=0;i<n;i++)
// printf(" %d",mas[i]);
for(i=0,lich=0;i<n;i++)
if(mas[i]==0)
lich++;
if (lich>0)
p3();
if(lich==0){
puts("\n");
for(i=0;i<n;i++)
printf(" %d",mas[i]);
p6(); }//return;
}
void p5(void){
int B, Imax=-1,Iv;
for(i=0,Imax=-1,Iv=-1;i<n;i++){
if(mas[i]>mas[i+1]){
Imax=i;
B=mas[i];
}
// else{
// Imax=i+1;
// B=mas[i+1];
// }
if(mas[i]==0&&i>Imax)
Iv=i;
}
if(Iv!=-1){
mas[Imax]=0;
mas[Iv]=B;
p4();
}
else
p6();
}
void p6(void){
//mas[Imax]=0;
//p5();
for(i=1;i<=(n+2)/2;i++){
if(mas[i]!=1)
lich+=1;
}
if(R>2&&mas[(n+4)/2]==1&&(n%2)==0&&lich==(n+2)/2)
return;
for(i=1;i<=(n+1)/2;i++){
if(mas[i]!=1)
lich+=1;
}
if(R>2&&mas[(n+3)/2]==1&&(n%2)!=0&&lich==(n+1)/2)
return;
if((R==1&&mas[(n+4)/2]==3)||(R==1&&mas[(n+3)/2]))
return;
mas[Imax]=0;
p5();
}
23.05.2013 19:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора