Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Курсова робота
Предмет:
Програмування
Група:
КІ-14
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота з програмування
Завдання
Завдання 1
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, структури, рядки символів) структури даних:
int i1;
short int i2 ;
unsigned short int i3 ;
long int i4;
unsigned long int i5 ;
float r1;
double r2;
long double r3;
char ch ;
char sl[15];
char m[2][5];
struct
{
char a1[10],a2[10];
char b1,b2,b3;
int c1,c2;
} str;
Завдання 2
Реалізувати променевий пошук.
Завдання 3
Матриця розміру N*M визначає деякий лабіринт. B матриці елемент 1 означає стіну, а 0 означає вільне місце. В першому рядку матриці визначаються входи x(і), а в останньому виходи y(і), і=1,..,k, що повинні бути нульовими елементами. Рух у лабіринті здійснюється тільки по вертикалі або горизонталі.
Визначити, чи можна :
а) провести людину через лабіринт від заданого входу в лабіринт до заданого виходу;
б) провести k людина від входу x(і) до виходу y(і) відповідно, і=1,..,k, таким чином, щоб кожне вільне місце відвідувалось не більше одного разу;
в) те ж, але людину можна виводити через кожний з виходів.
Використовуючи для розв’язання задачі динамічної структури даних ”Список”
Анотація
В курсовій роботі реалізовано три різні програми.
В першому завданні описано основні типи даних. Показано особливості їх запису в пам’яті комп’ютера. Наведено приклади ручного переведення даних різних типів до такого виду в якому вони записані в пам’яті комп’ютера. І створено програму яка показує представлення даних різних типів в пам’яті комп’ютера.
В другому завданні реалізований «Променевий пошук». Показано його
особливості реалізації. Алгоритм пошуку слів з використанням «променевого пошуку» - досить похожий до пошуку слів в словнику.
В третьому завданні наведено алгоритм проходження лабіринту. Наведено приклад програми проходження лабіринту при трьох умовах.
Зміст
Завдання на курсову роботу………………..
Анотація……………………………………...
Зміст………………………………………….
Вступ…………………………………………
1. Завдання 1…………………………………
1.1. Теоретична частина…………………..
1.2. Опис алгоритму……………………….
1.3. Система тестів ………………………..
1.4. Текст програми………………………..
2. Завдання 2…………………………………..
2.1. Теоретична частина……………………
2.2. Опис алгоритму………………………..
2.3. Система тестів………………………….
2.4. Текст програми…………………………
2.5. Результати виконання програми……...
2.6. Дослідження методу …………………..
3. Завдання 3…………………………………..
3.1. Теоретична частина……………………
3.2. Опис алгоритму………………………..
3.3. Система тестів…………………………
3.4. Текст програми………………………...
3.5. Результати виконання програми……...
Висновок………………………………………
Список літератури……………………………
Додатки………………………………………..
Вступ
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана.
В першій задачі досліджуються основні типи даних таких як: int,short,unsigned short int,long int,unsigned long int, float, double,long double,char,struct.
В цьому завданні ми переводимо дані з десяткової системи числення до двійкової. При цьому ми виділяємо байти числа (вісім розрядів). Для кожного типу даних їх різна кількість. Після переведення, результат записуємо в зворотному порядку, щоб він був аналогічний запису в пам’яті комп’ютера(при ручному переведенні). В програмній реалізації щоб показати представлення даних в пам’яті комп’ютера використовуємо вказівник на кожен байт числа записаного в пам’яті комп’ютера. Це вказівник типу unsigned char (без знакове – тобто дані записані за цією адресою сприймає як число).
Дане завдання добре ілюструє розміщення даних в пам’яті комп’ютера, що має велике навчальне значення.
В другому завданні реалізовано «Променевий пошук». Для його реалізації потрібно дані записати в М-арне дерево. Слова в нього записуються відповідно встановлених правил.(Слово записуємо в дереві за вказівником який відповідає першій його букві, якщо він нульовий. Якщо ні беремо наступну букву слова і просуваємося по дереві дальше.) «Променевий пошук» швидко повідомляє якщо дані відсутні в базі даних і він не робить лишніх проходжень по дереву при пошуку даних. «Променевий пошук» доцільно використовувати при пошуку великої кількості даних з досить малою базою даних.
В третьому завданні реалізована програма проходження лабіринту. Щоб пройти лабіринт я при кожному кроці намагаюся повернути наліво. При цьому кожен новий крок записую в список, а крок, що повторюється видаляю із списку. Від так в списку, якщо залишаться елементи то вони будуть показувати проходження лабіринту без повторень, якщо список порожній то виходу з даного входу лабіринту нема.
В загальному, в курсові роботі вирішено багато складних моментів, що описані в алгоритмах, або показані на блок схемах. Що має велике навчальне значення.
Завдання 1
У цій частині викладені основні теоретичні відомості необхідні для розв’язання першого завдання курсової роботи.
1.1. Теоретична частина до першого завдання .
Дані цілого типу
Для визначення даних цілого типу використовуються різні ключові слова, які визначають діапазон значень і розмір області пам'яті, що виділяється під змінні .
Назва типу
Індефікатор
Діапазон значень
Розмір пам’яті
Коротке ціле
short int
від -32768 до 32767
2
Без знакове коротке ціле
unsigned short int
від 0 до 65535
2
Ціле зі знаком
int
від -2 147 483 648 до
2 147 483 647
4
Довге ціле зі знаком
long int
від -2 147 483 648 до
2 147 483 647
4
Довге ціле без знаку
unsigned long int
от 0 до 4 294 967 295
4
Дані дійсного типу
Дані типи призначенні для обчислення даних, які мають цілу та дробову частину , тобто дроби.
Назва типу
Індефікатор
Діапазон значень
Розмір пам’яті
Дійсне
float
- 3.14E-38 до 3.14E+38
4
Дійсне подвійної точності
double
-1.7E-308 до 1.7E+308
8
Довге дійсне подвійної точності
long double
-1.7E-308 до 1.7E+308
8
Внутрішнє представлення даних дійсного типу:
a) float
б)double
1.1.4. Дані символьного типу
Char – символьний тип даних займає 1 байт пам’яті комп’ютера. Кожний символ має свій код по таблиці ASCII ( від 1 до 255 символів). Наприклад символ "A" має код 65(10)=41(16)=01000001(2), а символ "Z" має код 90(10)=5A(16) =01011010(2).
Рядок представляється як масив символів, який закінчується термінальним нулем і може бути описаний як - char імя [довжина].
Наприклад:
1.1.5. Дані конструйованого типу
1.1.5.1. Масив
Елементи масивів можуть бути різних типів, але в одному масиві всі його елементи є однакового типу. Розмір пам’яті, яку займає масив рівна добутку кількості елементів на розмір пам’яті одного елементу. Елементи масиву з найменшим індексом зберігаються по найменшій адресі, а у багатовимірному масиві найбільший правий індекс заміняється першим.
2.1.5.6. Структура
Структура – це структура даних, яка складається із фіксованого числа даних, що називаються полями структури. Поля структури зберігаються у пам’яті як неперервна послідовність змінних, перше поле зберігається по найменшій адресі. Якщо структура містить варіантні частини, то кожна варіантна частина записується по тій самій адресі.
1.2.Опис алгоритму
У завданні потрібно дослідити внутрішнє представлення різних типів даних.
Дані у комп’ютері представляються найменшими одиницями пам’яті - бітами (у двійковій системі числення), але оскільки користувач має доступ лише до байта пам’яті, то потрібно мати вказівник типу unsigned char, щоб можна було зчитувати байти числа з пам’яті та два масиви символів, перший масив для того, щоб записувати проміжні байти(byte[8]) , а другий, щоб записати кінцевий результат(value). Оскільки результат буде в десятковій системі числення , то потрібно перевести його до шістнадцяткової системи числення, а саме діленням на основу ситеми числення 16. Таким чином кінцевий результат буде повністю відображати побайтове представлення досліджуваної змінної у пам’яті комп’ютера.
Система тестів
1.3.1 Тип даних int:
Число 6 (10) ;
6:16=0, залишок 6;
Отже 6(10)=00 00 00 06(16)=00000000 00000000 00000000 00000110(2);
Оскільки число типу int займає 4 байти в пам’яті комп’ютера і вони розміщені в зворотньому порядку, то
Очікуваний результат: 00000110 00000000 00000000 00000000(2);
В пам’яті комп’ютера: 00000110 00000000 00000000 00000000 (2)=
=06 00 00 00(16);
1.3.2 Тип даних short int:
Число -6 (10)=-6 (16)= - 00000000 00000110 (2);
-00000000 00000110 -прямий код;
-11111111 11111001 -зворотній код;
+ 1
11111111 11111010 -доповняльний код;
Оскільки число типу short int займає 2 байти в пам’яті комп’ютера і вони розміщені в зворотньому порядку, то:
Очікуваний результат: 11111010 11111111(2);
В пам’яті комп’ютера: 11111010 11111111 (2) = FA FF(16) ;
1.3.3 Тип даних unsigned short int:
Число 750(10) ;
750:16=46, залишок 14(10)=E(16);
46 :16=2, залишок 14(10)=E(16);
2 :16= 0, залишок 2(10)= 2(16);
Отже 750(10)=2EE(16)=00000010 11101110(2);
Оскільки число типу unsigned short int , то знак не враховуємо, отже
Очікуваний результат: 11101110 00000010(2);
В пам’яті комп’ютера: 11101110 00000010(2)=EE 02(16);
1.3.3 Тип даних long int:
Число -750(10)= -2EE(16)= -00000000 00000000 00000010 11101110(2);
-00000000 00000000 00000010 11101110(2)–прямий код ;
-11111111 11111111 11111101 00010001(2)–зворотній код;
+ 1
11111111 11111111 11111101 00010010 (2)–доповняльний код ;
Оскільки число типу long int займає 4 байти в пам’яті комп’ютера і вони розміщені в зворотньому порядку, то
Очікуваний результат: 00010010 11111101 11111111 11111111(2);
В пам’яті комп’ютера: 00010010 11111101 11111111 11111111(2)=12 FD FF FF(16)
1.3.4 Тип даних unsigned long int:
Число 750(10)=2EE(16)== 00000000 00000000 00000010 11101110(2);
Оскільки число типу unsigned long int займає 4 байти в пам’яті комп’ютера і вони розміщені в зворотньому порядку, то
Очікуваний результат: 11101110 00000010 00000000 00000000(2);
В пам’яті комп’ютера: 11101110 00000010 00000000 00000000(2)=EE 02 00 00
1.3.5 Тип даних float:
Число 9.1989(10)
Число типу float займає 4 байти в пам’яті комп’ютера, тобто 32 біта
Перший з яких відповідає за знак(позначимо s) , 8 відповідає за порядок і 23 за мантису.
Визначаємо двійкове представлення дробової частини числа:
0.1989
16
3.1824
16
2.9184
16
14.6944
16
11.1104
16
1.7664
Отже двійкове представлення числа 9.1989(10) таке
1001.0011 0010 1110 1011 0001 1100 (2)=9.32EB1
1.001 0011 0010 1110 1011 0001(2)*10³- нормалізоване число;
23 біта
Оскільки ми зсунули число на два порядки вліво, то порядок буде такий:
e= 127+3=123(10)=1000 0010(2) ;
Число додатнє отже s=0.
Число записується за такою системою:
s+e+m , отже
Число: 01000001 00010011 00101110 10110010(2)
Оскільки число в пам’яті комп’ютера розміщене в зворотньому порядку, то
Очікуваний результат: 10110010 00101110 00010011 01000001(2) – B2 2E 13 41(16) ;
В пам’яті комп’ютера: 10110010 00101110 00010011 01000001;
1.3.6 Тип даних double:
Число 1149.862528(10) ;
Число типу double займає 8 байт в пам’яті комп’ютера, тобто 64 біта. Перший з яких відповідає за знак , 11- відповідає за порядок і 52 за мантису.
Визначаємо двійкове представлення цілої частини числа:
1149:16=71 залишок 13 (D);
71:16=4 залишок 7;
Визначаємо двійкове представлення дробової частини числа:
0.862528
2
13.800448 D
2
12.807168 C
2
12.914688 C
2
14.635008 E
2
10.160128 A
2
2.562048
Отже двійкове представлення числа 1149.862528(10) - 47D.DCCEA2 (16)
таке
0100 0111 1101. 1101 1100 1100 1110 1010 0010
1.00 0111 1101. 1101 1100 1100 1110 1010 0010 *10¹º¹º - нормалізоване число;
Оскільки ми зсунули кому вліво, то порядок буде такий:
e= 1023+10= 1033(10) =100 0000 1001(2)
Число додатнє отже s=0.
Число записується за такою системою:
s+e+m , отже
Число: 01000000 10010001 11110111 01110011 00111010 10001010 00000000 00000000 – 40 91 F7 72 3A 80 00 00(16);
Оскільки число в пам’яті комп’ютера розміщене в зворотньому порядку, то
Очікуваний результат: 00000000 00000000 10001010 00111010 01110011 11110111 10010001 01000000 – 00 00 80 3A 72 F7 91 40;
В пам’яті комп’ютера: : 00000000 00000000 10001010 00111010 01110011 11110111 10010001 01000000 – 00 00 80 3A 72 F7 91 40; 1.3.7 Тип даних long double:
Тип даних long double має аналогічне внутрішнє представлення до типу double.
Число 1149.862528(10) - 47D.DCCEA2 (16) =-0100 0111 1101. 1101 1100 1100 1110 1010 0010(2) ;
1.00 0111 1101. 1101 1100 1100 1110 1010 0010 *10¹º¹º - нормалізоване число;
Оскільки ми зсунули число на два порядки вліво, то порядок буде такий:
e= 1023+10= 1033(10) =100 0000 1001(2)
Число відємне отже s=1.
Число записується за такою системою:
s+e+m , отже
Число: 11000000 10010001 11110111 01110011 00111010 10001010 00000000 00000000 – C0 91 F7 72 3A 80 00 00(16);
Оскільки число в пам’яті комп’ютера розміщене в зворотньому порядку, то
Очікуваний результат: 00000000 00000000 10001010 00111010 01110011 11110111 10010001 11000000 – 00 00 80 3A 72 F7 91 C0;
В пам’яті комп’ютера: : 00000000 00000000 10001010 00111010 01110011 11110111 10010001 11000000 – 00 00 80 3A 72 F7 91 C0;
1.3.7 Тип даних char:
Число типу char займає 8 байт в пам’яті комп’ютера,преважно воно служить для представлення символів.Нехай запишемо символ ‘F’,
Поглянувши в таблицю кодування символів,можна побачити, що
Він представляється як число 70(10)=46(16)=01000110(2) .
Отже:
Очікуваний результат: 46(16)=01000110(2) ;
В пам’яті комп’ютера: 46(16)=01000110(2) ;
1.3.8Рядок символів:
Нехай char sl[15]="Fedun"
Поглянувши в таблицю кодування символів можна записати:
‘F’=70(10) =46 (16) =01000110 (2) ;
‘e’=101(10 )=65(16) =01100101 (2) ;
‘d’=100(10) =64(16) =01100100 (2) ;
‘u’=117(10) = 75(16) =01110101 (2) ;
‘n’=110(10) =6E(16) =01101110 (2) ;
Отже :
Очікуваний результат: 01000110 01100101 01100100 01110101 01101110 00000000;
В пам’яті комп’ютера: 01000110 01100101 01100100 01110101 01101110 00000000;
;
1.3.9 Структура:
struct
{
char a1[10],a2[10];
char b1,b2,b3;
int c1,c2;
}str;
str.a1[0]='L'; str.a1[1]='v'; str.a1[2]='i'; str.a1[3]='v'; str.a1[4]='\0';
str.a2[0]='L'; str.a2[1]='a'; str.a2[2]='z'; str.a2[3]='a'; str.a2[4]='r';
str.a2[5]='e'; str.a2[6]='n'; str.a2[7]='k'; str.a2[8]='a'; str.a2[9]='\0';
str.c1=40; str.c2=624; str.b1=',';str.b2=','; str.b3='/';
Поглянувши в таблицю кодування символів можна записати:
'L'=76(10) =01001100 (2), 'v'=118 (10) =01110110 (2)'i'=105 (10) = 01101001 (2)'a'=97 (10) =01100001 (2)'z'=122 (10) =01111010 (2)'r'=114(10) =01110010, ‘e’=101 (10) =01100101 (2), 'n'=100 (10) =01101110, 'k'=107 (10) =01101011, ','=44 (10) =00101100, '/'=47 (10)=01011111, 40 (10) =00101000, 624(10)=1001110000 (2)=270(16).
Пусті комірки рядка масиву по замовчуванні заповнюються числом -52(10)=11001100(2).
Отже :
Очікуваний результат: 01001100 01110110 01101001 01110110 00000000 11001100 11001100 11001100 11001100 11001100 01001100 01100001 01111010 01100001 01110010 01100101 01101110 01101011 01100001 00000000 00101100 00101100 00101111 11001100 00101000 00000000 00000000 00000000 11000010 00000010 00000000 00000000;
Lviv - 4C 76 69 76 (16)
Lazarenca – 4C 61 7A 61 72 65 6E 63 61
“,”- 2C(16)
“/”- 2F(16)
40(10)- 28 00 00 00(16)
624(10)- 70 02 00 00(16)
1.4. Текст програми
Текст програми можна зайти на гнучкому диску або в додатку.
У програмі розроблене текстове меню, яке дозволяє оперативно
задавати параметри роботи програми.
Функція void cyrillic(char* text) призначена для виводу кирилиці в текстовому режимі ,оскільки вона використовує функцію ОС Windows ,то потрібно підключити заголовочний файл windows.h .
Представлення різних типів даних в пам´яті комп’ютера
Функція void predstav_chusel() – підпрограма загальної функції main(). При звертанні до функції void predstav_chusel() ми обераємо режим роботи і функція виводить на екран представлення різних типів даних в пам´яті комп’ютера.
Функція void read_from_mem(void *ptr,int size) призначена для зчитування переданих їй даних з пам’яті комп’ютера та подальшого виведення на екран монітора результату її роботи.Для роботи функції потрібно передати два параметри вказівник на дані будь-якого типу та довжину цього типу в байтах.
Текст програми знаходиться в додатку 1.
Завдання 2
У цьому завданні реалізований променевий пошук.
2.1. Теоретична частина
Замість методів пошуку, заснованих на порівнянні ключів, можна скористатися представленням ключів в вигляді послідовності цифр або букв. Розглянемо, наприклад «по буквені мітки» в великих словниках які дозволяють миттєво знайти сторінки із словами, що починаються із заданої букви.
Розвинувши ідею по буквених міток до її логічного закінчення, можна получити схему пошуку, основану на повторному індексуванні яке представлене в таблиці 1. Припустимо, що необхідно повірити, чи являється даний аргумент пошуку одним з 31 найбільш вживаного англійського слова. Дані представлені в табл.1 в вигляді структури променя. Промінь, по суті, - це М-арне дерево, вузли якого представляють М-місні вектори з компонентами, що відповідають цифрам або буквам. Кожен вузол рівня l являється набором всіх ключів, які починаються з певної послідовності l символів, яка називається його префіксом; вузол визначає розгалуження на М шляхів в залежності від l+1 символу.
Наприклад, промінь з табл.1 вміщає 12 вузлів; вузол(1) представляє собою корінь, в якому ми шукаємо першу букву. Якщо першою буквою є, скажемо, N, з таблиці слідує, що це або слово NOT, або такого слова взагалі нема в таблиці. В той же час, якщо перша буква – W, то вузол (1) відправить нас до вузла (9) для пошуку другої букви тим же способом. Вузол (9) вказує, що друга буква повинна бути A, H або I. Префікс вузла (10) – НА. Пусті записи в таблиці означають відсутність зв’язків.
Вузли-вектори в табл..1 розташовані в відповідності з кодами символів. Це означає, що «променевий пошук» буде досить швидким, оскільки треба просто вибрати слова з масивів з використанням символів наших ключів в якості індексів.
Таблиця 1
Промінь для 31 найбільш вживаних англійських слів
Замітимо, що « невдалий пошук» виконується швидше в випадку променя порівняно з схожими алгоритмами пошуку (бінарного дерева пошуку). Для наших конкретних даних невдалий пошук буде виконуватися значно частіше, ніж «вдалий», а тому для них «променевий пошук» кращий з точки зору швидкості роботи.
«Променева пам'ять» для комп’ютерного пошуку була вперше рекомендована Рене де ла Бріанде. Він стверджував, що можна зберегти пам'ять (за рахунок часу роботи) при використанні зв’язаного списку для кожного вузла-вектора, оскільки більшість елементів вектора переважно пусті. Насправді ця ідея приводить до заміщення променя «лісом» на мал..1 Пошук в такому «лісі» виконується шляхом знаходження кореня, що відповідає першому символу і т.д.
Мал..1
2.2. Опис алгоритму
Алгоритм («променевого пошуку»). Дана таблиця записана в формі М-арного променя. Алгоритм виконує пошук по заданому аргументу К. Вузол променя представляє собою вектори, індекси яких змінюються від А до Z; кожен компонент такого вектора представляє собою ключ чи вказівник (може, пусту).
[Ініціалізація.] Встановити вказівну змінну Р так, щоб вона вказувала на корінь променя.
[Розгалуження.] Установити к рівним наступному символу вхідного аргумента ключа К зліва на право. ( Якщо аргумент повністю посканований, установити к рівним «пустому» символу чи символу «кінець слова». ( 0 ). Позначимо через Х к-й елемент в NODE(P). Якщо Х представляє собою вказівник, перейти до кроку 3, якщо Х – ключ, перейти до кроку 4.
[Просування.]. Якщо Х!=Λ, встановити Р <- Х і повернутися до кроку 2; в іншому випадку алгоритм завершується невдачею.
[Порівняння.]. Якщо Х!=К, алгоритм завершиться успішно; в іншому випадку алгоритм завершується невдачею.
Тобто: Ми маємо згенеровані в М-арному дереві дані (слова) і якесь слово. Беремо першу букву слова, стаємо в корінь дерева і перевіряємо відповідний вказівник дерева (що відповідає букві). Якщо він рівний 0 то кінець програми. Слова немає в послідовності. Інакше прирівнюємо ключ, що міститься за даною адресою і задане слово. Якщо вони рівні то це і є наше слово. Якщо ні – то беремо наступну букву слова і ще на рівень просуваємося по дереві. При цьому враховуємо вище наведені умови.
2.3. Система тестів
Мал..2
А.) Нехай наше слово the. І на мал..2 ми маємо частину з генерованого дерева.
2.3.1. Беремо першу букву t (дії виконуємо згідно алгоритму).Вказівника на неї є, але це не задане слово.
2.3.2. Беремо наступну букву h.Вказівника на неї є, але це не задане слово.
2.3.3. Беремо наступну букву e.Вказівника на неї є і задане слово збігається з словом в нашій базі даних.(the\ Отже ми маємо дані про слово. В нашому випадку це частота вживання.) Кінець програми.
В.) Нехай наше слово then. І на мал..2 ми маємо частину з генерованого дерева.
2.3.1. Беремо першу букву t (дії виконуємо згідно алгоритму).Вказівника на неї є, але це не задане слово.
2.3.2. Беремо наступну букву h.Вказівника на неї є, але це не задане слово.
2.3.3. Беремо наступну букву e. Вказівника на неї є, але це не задане слово.
2.3.4. Беремо наступну букву n. Вказівника на неї нема, отже даного слова немає в нашій базі даних. Кінець програми.
2.4. Дослідження методу
І так, промінь здатний виконати М-шляхове розгалуження за один раз; ми побачимо, що середній час пошуку для великих N включає всього близько logM N = lg N / lg M ітерацій при випадкових вхідних даних. Ми також побачимо, що «чиста» схема променя потребує, в цілому, приблизно N / ln M вузлів для розміщення N випадкових ключів; отже, загальна кількість необхідної пам’яті пропорційна MN / ln M.
2.5. Текст програми
Програма використовує:
2.5.1. promPOSHUK() головна підпрограма.
2.5.2. struct slova для формування М-арного дерева в якому будуть записані слова і дані про них.
2.5.3. функцію init1 () яка безпосередньо формує М-арне дерево.
2.5.4. функцію POSHUK() яка шукає задане слово.
2.5.5. допоміжні функції tree posh0() – функція пошуку нульового сина дерева і функція void NULLslov() – обнуління синів дерева.
Програма знаходиться в додатку 2.
2.5. Результати виконання програми
Завдання 3
3.1. Теоретична частина
Список – це набір елементів (частіше всього структурних змінних), розміщених в динамічні пам’яті і зв’язаних між собою вказівниками на ці елементи. Використаний спосіб зв’язання елементів визначає тип списку.
Списки бувають лінійні і кільцеві, однозв’язні і багато зв’язні. Єлемент однозв’язного списку вміщає крім безпосередньо «корисної» інформації також інформацію про наступний або попередній елемент списку. Відповідно елемент двозв’язаного списку має інформацію, як про наступний елемент, так і про попередній елемент. Останній елемент кільцевого списку має вказівник на перший елемент списку.
Якщо список розташований в оперативні пам’яті, то інформація для пошуку наступного об’єкта – адрес (вказівник) в пам’яті. Якщо зв’язаний список зберігається в файлі на диску, то інформація про наступний елемент може включати зміщення елемента від початку файлу, знаходження вказівника запису/читання файлу, ключ запису чи будь-яку другу інформацію, дозволяючу однозначно знайти наступний елемент списку.
Графічно списки можна відобразити наступним чином:
Однозв’язаний
лінійний список
NULL
Двозв’язаний лінійний список Однозв’язаний кільцевий список
NULL
NULL
Самими поширеними випадками лінійного однозв’язного списку є черга чи стек.
3.2. Опис алгоритму
Ми проходимо матрицю при, цьому запам’ятовуємо «звідки ми йшли» також ми записуємо в список послідовність проходження. Якщо ми проходимо якусь комірку вже другий раз то з списку видаляємо «адресу» цієї комірки.
При проходженні лабіринту ми постійно притримуємося «лівої стінки».
А1. Вводимо розміри лабіринту. Навколо нього «будуємо стіну» з «1». Вводимо вхід і вихід (якщо це потрібно).(Починаємо з входу).
А2. Перевіряємо чи вхід і вихід != 1, якщо так то переходимо до кроку А7. Якщо ні продовжуємо.
А3. Останнє проходження було «↓».
Перевірка для подальшого проходження буде виконуватися в такому порядку: (вибираємо те яке швидше зустрінеться)
а) →
б) ↓
в) ←
г) ↑
Якщо ми дійшли до виходу, або повернулися на місце входу то перейти на крок А7. Якщо ні то перейти до відповідного кроку (що відповідає останньому проходженню).
А4. Останнє проходження було «→».
Перевірка для подальшого проходження буде виконуватися в такому порядку: (вибираємо те яке швидше зустрінеться)
а) ↑
б) →
в) ↓
г) ←
Якщо ми дійшли до виходу, або повернулися на місце входу то перейти на крок А7. Якщо ні то перейти до відповідного кроку (що відповідає останньому проходженню).
А5. Останнє проходження було «↑».
Перевірка для подальшого проходження буде виконуватися в такому порядку: (вибираємо те яке швидше зустрінеться)
а) ←
б) ↑
в) →
г) ↓
Якщо ми дійшли до виходу, або повернулися на місце входу то перейти на крок А7. Якщо ні то перейти до відповідного кроку (що відповідає останньому проходженню).
А6. Останнє проходження було «←».
Перевірка для подальшого проходження буде виконуватися в такому порядку: (вибираємо те яке швидше зустрінеться)
а) ↓
б) ←
в) ↑
г) →
Якщо ми дійшли до виходу, або повернулися на місце входу то перейти на крок А7. Якщо ні то перейти до відповідного кроку (що відповідає останньому проходженню).
А7. Вихід з програми.
3.3. Система тестів
3.3.1. Нехай маємо лабіринт (матрицю) 6*10
0000100011
1001001001
0010100111
1010101001
0110001010
1001010100
3.3.2. Описуємо «1»
111111111111
100001000111
110010010011
100101001111
110101010011
101100010101
110010101001
111111111111
Сформований лабіринт.
3.3.3. Нехай нам потрібно пройти від 7 входу до 5 виходу.(Пам’ятаємо, що рахунок починаємо з 0. В тих місцях де ми вказуємо вхід і вихід, 1 автоматично заміниться на 0. 1-це стіна, 0-прохід.)
Прохід від входу до виходу
111111 1↓ 1 1 11
100001 ↓←←1 11
110010 ↓1 ↑ ←11
100101 ↓0 1 1 11
110101 ↓1 0 0 11
10110↓←1 0 1 01
11001↓ 10 1 0 01
11111↓ 11 1 1 11
3.3.4. Нехай нам потрібно пройти від 3 входу до 5 виходу.
1 1 1 1 1 1111111
1→ → ↑ ←1000111
1 1 ↑← 1 0010011
1→ ↑ 1 0 1001111
1 1 ↑ 1 0 1010011
1 0 1 1 0 0010101
1 1 0 0 1 0101001
1 1 1 1 1 1111111 Проходу нема.
3.3.5. Пройти від входу 6 до 5 виходу ←↑→↓
111111↓ 1 1 1 11
100001↓ 1 1 1 11
110010↓ 1 ↑ ←11
100101↓ 0 1 1 11
110101↓ 1 0 0 11
10110↓←1 0 1 01
11001↓1 0 1 0 01
11111↓1 1 1 1 11
3.4. Текст програми
Програма використовує:
3.4.1. laBirynt() – головна підпрограма.
3.4.2. Структуру struct node() для створення списку.
3.4.3. Підпрограми які безпосереднь виконують специфічне проходження лабіринту: void f11(char* f,int m,int n) - походження лабіринту від входу до виходу,без повторень; void f33(char* f,int m,int n) – походження лабіринту від входу до будь-якого виходу,без повторень; void fff(char* f,int m,int n)-звичайне походження лабіринту від входу до виходу.
3.4.5. Функції роботи із списком: list Find(list head_list,int search_data)- пошук вузла із заданим значеенням у списку; list FindAfter(list node),
list FindBefore(list head_list, list node)- пошук вузла перед заданим значенням; void Delete(list *head_list_ptr, list *node_ptr) - вилучення заданого вузла зі списку; void AddEnd(list *head_list_ptr,int new_data,char new_ch ) - додавання в кінець списку.
Програма міститься в додатку 3.
Головна програма курсової яка об’єднує всі три програми міститься в додатку 4.
3.5. Результати виконання програми
Висновок
Виконавши завдання курсової роботи я закріпив і розширив теоретичні і практичні знання з програмування, навчився застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач.
Отримав навики розробки більш складних програмних продуктів і оформлення програмної документації.
Список літератури
Кнут Д. Искусство програмирования, том 1. Основные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 720 с.
Кнут Д. Искусство програмирования, том 2. Получисленные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 763 с.
Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы , построение и анализ. Классические.
1. Додаток
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include<windows.h>
/*****************************************************************************/
//представлення даних
struct pio
{
char a1[10];
char a2[10];
char b1,b2,b3;
int c1,c2;
};
/****Функція виведення кирилиці****/
void cyrillic(char* text)
{
char* x;
int l,i,size=sizeof(text);
l=strlen(text);
x=(char*)malloc(size);
for(i=0;i<l;i++)
{
x[i]=text[i];
if(x[i]=='і')x[i]='i';
if(x[i]=='І')x[i]='I';
}
x[i]='\0';
CharToOem(x,x);
printf(x);
}
void read_from_mem(void* ptr,int size)
{
int i,j;
char read_value[100]={0};
char str_byte[3]={0};
char chab[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
for(i=0;i<size;i++)
{
for(j=1;j>=0;j--)
{
str_byte[j] = chab[*((unsigned char*)ptr)%16];//приведееня типів
*((unsigned char*)ptr)/=16;
}
strcat(read_value,str_byte);
strcat(read_value," ");
((char*) ptr)++;
}
printf("\n");
puts(read_value);
}
void main()
{
int i1,i,j;
short int i2 ;
unsigned short int i3 ;
long int i4;
unsigned long int i5 ;
float r1;
double r2;
long double r3;
unsigned char ch ;
char sl[15]="Fedun";
char m[2][5]={0,9,8,9,5,6,4,7,8,3};
struct pio str;
do
{
cyrillic("\n\tПрограма представлення різних типів даних в пам'яті комп'ютера\n");
cyrillic("\n\tНажміть:\n 1 -якщо вибераєте автозаповнення; \n 2 - якщо вибераєте заповнення вручну; \n 0 - якщо хочете покинути дану програму;\n\t");
scanf("%d",&i);
if(i==1)
{
i1=6;
r1 = 9.1989;
ch = 'F';
strcpy(str.a1,"Lviv"); //str.a1="Лвів";
strcpy(str.a2,"Lazarenca"); //str.a2[10]="Лазаренка";
str.b1 = ',' ;
str.b2 = ',' ;
str.b3 = '/' ;
str.c1=40;str.c2=624;
}
if(i==2)
{
//*** Ручний ввід даних ***//
cyrillic("\t\t\t***Ви обрали самостійний ввід даних ***\n\n");
cyrillic(" Введіть число типу INT ( - день народження )\n");
printf("INT-> ");
scanf("%d",&i1);
cyrillic("Введіть число типу FLOAT (дробове число: ціла частина - місяць народження, дробова частина - рік народження;)\n");
printf("FLOAT-> ");
scanf("%f",&r1);
cyrillic("Введіть число типу CHAR (- перша літера Прізвища (велика літера);)\n");
printf("CHAR-> ");
scanf("%s",&ch);
cyrillic("Введіть дані для структури\n a1,a2,b1,b2,b3,c1,c2");
cyrillic("\n- назва міста в адресі прописки ( літери, перша - велика, решта - малі);");
printf("\na1->");
scanf("%s",&str.a1);
cyrillic("\nназва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);");
printf("\na2->");
scanf("%s",&str.a2);
cyrillic("\nдані типу char b1,b2,b3");
printf("\nb1->");
scanf("%s",&str.b1);
printf("\nb2->");
scanf("%s",&str.b2);
printf("\nb3->");
scanf("%s",&str.b3);
cyrillic("\nномер будинку в адресі прописки;");
printf("\nc1->");
scanf("%d",&str.c1);
cyrillic("\nномер квартири в адресі прописки;");
printf("\nc2->");
scanf("%d",&str.c2);
printf("STRUCT:");
cyrillic("Введіть РЯДОК СИМВОЛІВ (- Прізвище ( перша - велика, решта - малі);)\n");
cyrillic("РЯДОК СИМВОЛІВ -> ");
scanf("%s",&sl) ;
cyrillic("Введіть МАСИВ СИМВОЛІВ(m[i,j] - символ, який дорівнює відповідній цифрі номера мобільного телефону;");
printf("\nm[0][0]=");
scanf("%s",&m[0][0]);
printf("\nm[0][1]=");
scanf("%s",&m[0][1]);
printf("\nm[0][2]=");
scanf("%s",&m[0][2]);
printf("\nm[0][3]=");
scanf("%s",&m[0][3]);
printf("\nm[0][4]=");
scanf("%s",&m[0][4]);
printf("\nm[1][0]=");
scanf("%s",&m[1][0]);
printf("\nm[1][1]=");
scanf("%s",&m[1][1]);
printf("\nm[1][2]=");
scanf("%s",&m[1][2]);
printf("\nm[1][3]=");
scanf("%s",&m[1][3]);
printf("\nm[1][4]=");
scanf("%s",&m[1][4]);
}
if(i==1||i==2)
{
i2 = -i1;
i3 = i1*125,334;
i4 = -i3;
i5 = i3;
r2 = r1*125;
r3 = -r2;
printf("\n \t typ int %d -> ",i1);
read_from_mem(&i1,sizeof(i1));
printf("\n \t typ short int%d -> ",i2);
read_from_mem(&i2,sizeof(i2));
printf("\n \t typ unsigned short int %d -> ",i3);
read_from_mem(&i3,sizeof(i3));
printf("\n \t typ long int %Ld -> ",i4);
read_from_mem(&i4,sizeof(i4));
printf("\n \t typ unsigned long int %Ld -> ",i5);
read_from_mem(&i5,sizeof(i5));
printf("\n \t typ float %f - ",r1);
read_from_mem(&r1,sizeof(r1));
printf("\n \t typ double %f ->",r2);
read_from_mem(&r2,sizeof(r2));
printf("\n \t typ long double r3; %Lf -> ",r3);
read_from_mem(&r3,sizeof(r3));
printf("\n \t typ char %c -> ",ch);
read_from_mem(&ch,sizeof(ch));
printf("\n \t typ char %s -> ",sl);
for(i=0;sl[i]!=0;i++)
{
printf("%x ",sl[i]);
}
printf("\n\n\tmasyv typu char:\n\t");
for(i=0;i<2;i++)
{
for(j=0;j<5;j++)
printf("%c - %x\n\t",m[i][j],m[i][j]);
}
printf("\n\tSTRUCT:\n\t");
printf("typ st.char %s -> ",str.a1);
for(i=0;str.a1[i]!=0;i++)
{
printf("%x ",str.a1[i]);
}
printf("\n\ttyp st.char %s -> ",str.a2);
for(i=0;str.a2[i]!=0;i++)
{
printf("%x ",str.a2[i]);
}
printf("\n\ttyp st.char %c -> ",str.b1); read_from_mem(&str.b1,sizeof(str.b1));
printf("\n\ttyp st.char %c -> ",str.b2); read_from_mem(&str.b2,sizeof(str.b2));
printf("\n\ttyp st.char %c -> ",str.b3); read_from_mem(&str.b3,sizeof(str.b3));
printf("\n\ttyp st.int %d -> ",str.c1);
read_from_mem(&str.c1,sizeof(str.c1));
printf("\n\ttyp st.int %d -> ",str.c2);
read_from_mem(&str.c2,sizeof(str.c2));
}
}while(i!=0 );
return 0;
}
Додаток 2.
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include<windows.h>
struct slova
{
char sl[10];
int kilkist;
struct* synu[123];
};
typedef struct slova *tree;
/*--Ініціалізація вказівника на дерево----*/
void Init09(tree *pto)
{
*pto = NULL;
}
/*--Обнулення синів дерева---*/
void NULLslov(tree pto)
{
int i;
for(i=0;i<123;i++)
{
pto->synu[i]=NULL;
}
}
/*-----Допоміжна функція для пошуку нульового сина дерева----*/
tree posh0(tree pto,int buf)
{
return pto->synu[buf];
}
/*---фОРМУВАННЯ М-АРНОГО ДЕРЕВА----*/
tree init1 ()
{
int i,j,buf;
tree t1,p2,p3;
char sliv[12][6]={"not","and","as","are","ar","bus","be","by","to","that","then","the"};
int m[12]={123,34,56,67,21,324,535,567,876,967,987,678};
Init09(&t1);
t1= malloc(sizeof(struct slova));
strcpy(t1->sl,"0");
NULLslov(t1);
for(i=0;i<12;i++)
{
p2=t1;
for(j=0;j<6;j++)
{
buf=sliv[i][j];
if(posh0(p2,buf)==NULL)
{
p3=malloc(sizeof(struct slova));
strcpy(p3->sl,sliv[i]);
p3->kilkist=m[i];
NULLslov(p3) ;
p2->synu[buf]=p3;
break;
}
else
{
p2=p2->synu[buf];
}
}
}
return t1;
}
/*---ПРОМЕНЕВИЙ ПОШУК ЗАДАНОГО ЕЛЕМЕНТА ---*/
void POSHUK(tree pto,char new_s[10])
{
int i,buf;
for(i=0;strcmp(pto->sl,new_s)!=0;i++)
{
buf=new_s[i];
pto=pto->synu[buf];
if(pto==0)break;
}
if(pto!=0)
{
printf(" SLOVO - %s ",pto->sl);
printf("\n VIDNOSNA CASTOTA VJYVANNIA PROTIAGOM HODYNY\n\t%d\n",pto->kilkist);
}
else
printf("\nDanogo slova nema v poslidovnosti!!!\n");
}
void promPOSHUK()
{
int i=0;
tree derevo;
char slovo[10];
derevo=init1();
system("cls");
printf("\nPrograma mistyti naibilish vgyvani English slova");
do
{
printf("\nVvedit 0 - zakincyty programy\n\n\t 1 - poshuk slova --");
scanf("%d",&i);
if(i==1)
{
printf("\nVvedit slovo dlia poshuku: ");
printf("\n\t( z maloi bukvy )\n\t");
scanf("%s",slovo);
POSHUK(derevo,slovo);
}
}while(i==1 );
free(derevo);
return 0;
Додаток 3.
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include<windows.h>
#include <assert.h>
//лабіринт
struct node
{
int data;
char ch;
struct node *next;
};
typedef struct node *list;
int k=0;
//ініціаоізація списку
void Init(list *head_list_ptr)
{
*head_list_ptr = NULL;
return;
}
// перевірка чи список порожній
int Empty(list head_list)
{
return head_list == NULL;
}
//Додавання в кінець списку
void AddEnd(list *head_list_ptr,int new_data,char new_ch )
{
list new_node;
list new_node1=*head_list_ptr;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->ch =new_ch;
new_node->next = NULL;
if (Empty(*head_list_ptr)) *head_list_ptr = new_node;
else
{
if(new_node1)while (new_node1->next) new_node1 =new_node1->next ;
new_node1->next = new_node;
//FindLast(*head_list_ptr)->next = new_node;
//new_node1=FindLast(*head_list_ptr);
//new_node1->next = new_node;
}
return ;
}
//Пошук останнього елемента списку
list FindLast(list head_list)
{
if (head_list) while (head_list->next) head_list = head_list->next;
return head_list;
}
//пошук вузла перед заданим значенням
list FindBefore(list head_list, list node)
{
while ((head_list->next != node) && head_list) head_list = head_list->next;
return head_list;
}
list FindAfter(list node)
{
return node->next;
}
// Пошук вузла із заданим значеенням у списку
list Find(list head_list,int search_data)
{
while ((head_list) && (head_list->data != search_data)) head_list = head_list->next;
return head_list;
}
// Вилучення заданого вузла зі списку
void Delete(list *head_list_ptr, list *node_ptr)
{
list tmp , save_ptr=*node_ptr;
assert(*head_list_ptr);
assert(*node_ptr);
if (*node_ptr == *head_list_ptr)
*head_list_ptr = (*head_list_ptr)->next;
else
if (!((*node_ptr)->next))
{
tmp = FindBefore(*head_list_ptr,*node_ptr);
tmp->next = NULL;
}
else
{
tmp = (*node_ptr)->next;
(*node_ptr)->data = tmp->data;
(*node_ptr)->next = tmp->next;
save_ptr = tmp;
};
free(save_ptr);
return ;
}
void fff(char* f,int m,int n)
{
int i=0,j=0,vh,vuh;
cyrillic("\n\tВведіть вхід\n");
scanf("%d",&vh);
cyrillic("\n\tВведіть вихід\n");
scanf("%d",&vuh);
i=vh;
f[i]='0';
f[(n+2)*(m+1)+vuh]='0';
if (f[i+n+2]!='1' && f[(n+2)*m+vuh]!='1')
{
while((i!=vh && j!=0) || (i==vh && j==0)) //|| i!=(n+2)*m+vuh
{
...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора