Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2015
Тип роботи:
Розрахункова робота
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
/
Розрахункова робота
з дисципліни
«Теорія алгоритмів»
Варіант - 5
ЛЬВІВ 2015
Зміст
Індивідуальне завдання.
Покроковий опис алгоритму.
Програмна реалізація.
Приклад роботи програми
Висновок.
Індивідуальне завдання
Дванадцять чисел, оточуючи фортецю, вирішили розташуватись так, щоб їхня сума вздовж кожної сторони шестикутника дорівнювала 17. Чотири числа вже знаходяться на своїх місцях. Як треба розташувати решту вісім чисел?
Покроковий опис алгоритму
Створюємо масив для збереження числової послідовності та масив для визначення, чи число використовувалося, чи ні.
Вводимо у масив числової послідовності дані, які задані умовою, тобто числа 9, 6, 2 і 12 уже знаходяться на своїх місцях.
Масив, який містить логічні true і false повністю заповнюємо значеннями true(число вільне), а окремі елементи, які відповідають числам, котрі уже на своїх місцях, заповнимо значеннями false(число зайняте).
Пошук наступного потрібного числа розпочинаємо з 5 елемента, оскільки перші 4 уже задані. Пошук здійсюємо за допомогою окремої функції, котра шукає вільне число і повертає його або -1, якшо вільних чисел немає.
Якщо послідовність пройдена до кінця(12) і програма вийшла за межі послідовності, і зупинилася знову на першому елементі, то рахуємо суму.
Якщо сума правильна, то потрібна послідовність знайдена.
Якщо крок не за межами послідовності, то перевіряємо чи це не перетин сторін. Якщо це перетин, то заповнюємо елемент масиву послідовності числом поки не буде знайдено потрібної суми. Якщо такого числа не знайшлося, то повертаємось.
Якщо цикл зупинився на звичайному елементі, який не є перетином сторін, то шукаємо для нього число.
Пошук числа відбувається наступним чином: В функцію пошуку передається останнє число, яке ми присвоїли елементу(початково воно -1), беремо наступне після останнього і починаємо пошук поки не досягнемо максимального числа(12).
Функція повертає знайдене число. Якщо число не знайдеться. Функція повертає -1 і цикл по послідовності повертається назад.
Якщо ж ми отримали негативний результат пошуку послідовності з наступних кроків циклу, то спробуємо підставити інше число і для пошуку задаємо наступне після останнього число, яке ми вставили.
Програмна реалізація
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <cstdlib>
#define N 12
int searchNum(int last, bool c[N])
{
for (int i = last; i<N; i++)
if (c[i])
return i;
return -1;
}
bool search(int mas[N], bool c[N], int i)
{
if (i == 12)
{
if ((mas[i - 2] + mas[i - 1] + mas[0]) == 17)
{
printf("%d+%d+%d=%d\n", mas[i - 2], mas[i - 1], mas[0], mas[i - 2] + mas[i - 1] + mas[0]);
return true;
}
else
return false;
}
else
if (i % 2 == 0 && i != 0)
{
int last = -1;
int sum = 0;
do
{
if (last != -1)
c[last] = true;
last = searchNum(last + 1, c);
if (last == -1)
return false;
c[last] = false;
mas[i] = last + 1;
sum = mas[i - 2] + mas[i - 1] + mas[i];
}
while (sum<17);
if (sum == 17)
if (search(mas, c, i + 1))
{
printf("%d+%d+%d=%d\n", mas[i - 2], mas[i - 1], mas[i], mas[i - 2] + mas[i - 1] + mas[i]);
return true;
}
else
{
c[last] = true;
return false;
}
else
{
c[last] = true;
return false;
}
}
else
{
int last = -1;
do
{
if (last != -1) c[last] = true;
last = searchNum(last + 1, c);
if (last == -1) return false;
c[last] = false;
mas[i] = last + 1;
while (!search(mas, c, i + 1));
}
}
int main()
{
bool c[N];
int mas[N];
for (int i = 0; i<N; i++)
{
c[i] = true;
}
c[8] = c[5] = c[1] = c[11] = false;
mas[0] = 9;
mas[1] = 6;
mas[2] = 2;
mas[3] = 12;
if (search(mas, c, 4))
for (int j = 0; j<12; j++)
printf("%d ", mas[j]);
_getch();
return 0;
}
Приклад роботи програми:
/
Висновок:
Отже, у ході даної розрахункової роботи, я розробив програму мовою С, котра розставляє числа від 1 до 12 на сторонах шестикутника так, щоб сума чисел на кожному ребрі була рівна 17. Розроблений мною алгоритм є досить простий в реалізації та має хороші часові характеристики(O(n2)). Програма призначена лише для конкретного прикладу і не є універсальною.
18.12.2015 00:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора