неділя, 21 січня 2018 р.

База даних Клас в MS Access

Практична робота 4. База даних Клас в MS Access
Завдання 1. Самостійно створіть базу даних КЛАС, яка повинна містити такі таблиці: «Відомості про учнів(иць)», «Відомості про документи», Фото учнів, «Відомості про татів», «Відомості про матерів»,   «Відомості про вчителів»,  «Відомості про підручники»,  «Відомості про події у класі»,  «Відомості про чергування у класі», «Колективні проекти класу».
Таблиця 1 має назву: «Відомості про учнів(иць)», вона складається з 9 полів(формат):
Код(авторнумерація), Прізвище(текст), Ім’я(текст), По батькові(текст), Дата народження(маска вводу: 00-00-0000), Мобільний телефон(маска вводу: 000-000-0000), Домашня адреса(текст), Навантаження (у вигляді списку: активіст 1 ланки,  активіст 2 ланки, активіст 3 ланки, член активу класу, староста, президент класу, член парламенту школи), Протипоказання(так/ні). Застосуйте вирівнювання «по центру».
Таблиця 2 має назву: «Відомості про документи», вона складається з 8 полів(формат):
Код(авторнумерація), Прізвище(текст), Ім’я(текст), По батькові(текст), Номер особової справи(маска вводу: 00-000), Індентифікаційний код(маска вводу: 0000000000000), Номер учнівського квитка(маска вводу: 000-000). Копія свідоцтва дитини(так/ні).
Таблиця 3 має назву: «Фото учня(иці)», і має 6 полів(формат);
Код(авторнумерація), Прізвище(текст), Ім’я(текст), По батькові(текст), Фотопортрет (Поле объекта OLE). Фотоколаж(Поле объекта OLE). В таблиці створити 5 записів(рядків) з фотками в комірках.
Таблиця 4 має назву: «Відомості про татів» і має 11 полів: (у таблиці створити 5 записів про татів)
Код(авторнумерація), Прізвище батька(текст), Ім’я батька(текст), По батькові тата(текст), Дата народження батька(маска вводу: 00-00-0000), Мобільний телефон батька(маска вводу: 000-000-0000), Домашня адреса батька(текст), Освіта батька(у вигляді списку: повна вища, неповна вища, середня спеціальна,повна середня, базова середня, початкова) Місце роботи батька(у вигляді списку: військовий, бізнесмен, чиновник, службовець, робітник, безробітний).Ідентифікаційний код(текстовий). Кількість дітей у сім’ї(числовий).
Таблиця 5 має назву: «Відомості про матерів» і складається з 11 полів:  (у таблиці створити 5 записів про мам).
Код(авторнумерація), Прізвище мами (текст), Ім’я мами(текст), По батькові мами(текст), Дата народження мами(маска вводу: 00-00-0000), Мобільний телефон мами(маска вводу: 000-000-0000), Домашня адреса мами(текст), Освіта мами(у вигляді списку: повна вища, неповна вища, середня спеціальна,повна середня, базова середня, початкова) Місце роботи мами(у вигляді списку:військова, бізнесмен, чиновник, службовець, робітниця, безробітна).Ідентифікаційний код(текстовий). Кількість дітей у сім’ї(числовий).
Таблиця 6 має назву: «Відомості про вчителів» складається з 10 полів, (у таблиці створити 5 записів (рядків):
Код(авторнумерація), Прізвище учителя(текст), Ім’я учителя(текст), По батькові учителя(текст), Дата народження учителя(маска вводу: 00-00-0000), Мобільний телефон учителя(маска вводу: 000-000-0000), Предмет учителя(текстовий).    Сайт учителя(гіперпосилання). Номер класу учителя, Домашня адреса учителя.
Таблиця 7 має назву: «Відомості про підручники» має 20 полів: Код, ПІБ учня, Предмети(усі-усі), Кіль-сть книг.
Таблиця 8 має назву:  «Відомості про події» складається з 4 полів: Код, Дата події, Опис події, Фото події.
Таблиця 9 має назву:   «Відомості чергування» складається з 3 полів: Код, Дата , Номер чергової ланки.

Таблиця 10 має назву:   «Колективні проекти класу» складається з 3 полів: Код, Дата, Назва, Відповідальні. 

Завдання 2.
Створіть форми у відповідності до  створених таблиць, збережіть ці форми і введіть по два записи у кожну таблицю, використовуючи форму.

пʼятниця, 12 січня 2018 р.

Завдання для програмування з масивами

 
Задача 1. Напишіть програму, яка визначає, скільки разів зустрічається задане число х в даному масиві.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). У третьому рядку міститься одне ціле число х, що не перевершує по модулю 1000. Вивести одне число - скільки разів зустрічається х в даному масиві.
Приклад.
Вхідні дані.
5
1 2 3 4 5
3
Вихідні дані.

 
 
Задача 2. Напишіть програму, яка визначає, чи зустрічається задане число х в даному масиві.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). У третьому рядку міститься одне ціле число х, що не перевершує по модулем 1000. Вивести одне число - скільки разів зустрічається х в даному масиві.
Приклад.
Вхідні дані.
5
1 2 3 4 5
3
Вихідні дані.
ТАК
 

 
Задача 3. Напишіть програму, яка знаходить в масиві елемент, найближчий за величиною до даного числа.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). У третьому рядку міститься одне ціле число х, що не перевершує по модулем 1000. Вивести значення елемента масиву, найближче до х. Якщо таких чисел декілька, виведіть будь-яке з них.
Приклад.
Вхідні дані.
5
1 2 3 4 5
6
Вихідні дані.
5
 


 
Задача 4. Напишіть програму, яка виводить номера елементів масиву, рівних заданому числу.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). У третьому рядку міститься одне ціле число х, що не перевершує по модулем 1000. Вивести номери елементів, рівних заданому, в порядку зростання. Якщо таких елементів немає, нічого виводити не потрібно.
Приклад.
Вхідні дані.
5
1 2 3 4 5
3
Вихідні дані.
3
 

 

Задача 5. Напишіть програму, яка знаходить значення максимального елемента масиву.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). Вивести одне число - значення максимального елемента в масиві.
Приклад.
Вхідні дані.
5
1 2 3 4 5
Вихідні дані.
5
 


 
Задача 6 Напишіть програму, яка знаходить номер максимального елемента масиву.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). Вивести одне число - номер максимального елемента в масиві.
Приклад.
Вхідні дані.
5
1 2 3 4 5
Вихідні дані.
5 

 
   
 
Задача 7. Напишіть програму, яка знаходить кількість нульових елементів масиву.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). Вивести одне число - кількість нулів в масиві.
Приклад.
Вхідні дані.
5
1 2 0 4 5
Вихідні дані.
1
 

 
 
Задача 8. Напишіть програму, яка знаходить кількість додатних елементів масиву.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). Вивести одне число - кількість додатніх елементів в масиві.
Приклад.
Вхідні дані.
5
1 2 0 4 5
Вихідні дані.
4



Задача 9. Напишіть програму, яка визначає, чи є в масиві пара сусідніх елементів з однаковими знаками.
 
Технічні умови. У першому рядку задається одне натуральне число N, яке не перевищує 1000 - розмір масиву. У другому рядку вводяться N чисел - елементи масиву (цілі числа, що не перевищують по модулю 1000). Необхідно вивести слово YES, якщо існує пара сусідніх елементів з однаковими знаками. В іншому випадку слід вивести слово NO.
Приклад.
Вхідні дані.
5
-1 2 -4 5 -3
Вихідні дані.
НЕМАЄ


 
Задача 10. Напишіть програму, яка визначить, чи збігаються два рядки.
 
Технічні умови. У першому рядку задається одне слово. У другому рядку друге слово. Необхідно вивести слово YES, якщо рядки збігаються, і слово NO в іншому випадку.
Приклад.
Вхідні дані.
абс
абс
Вихідні дані.
ТАК

   
Задача 11. Дано рядок, що містить пропуски. Знайдіть, скільки в ній слів.
 
Технічні умови. У першому рядку задається один рядок. Необхідно вивести кількість слів.
Приклад.
Вхідні дані.
У місті, де я народився
Вихідні дані.
7

 
 
Задача 12. Дано два рядки. Визначте, чи є перший рядок підрядком другого рядка.
 
Технічні умови. У першому рядку задається перший рядок. У другому рядку - другий рядок. Необхідно вивести слово YES, якщо перший рядок є підрядком другого рядка, або слово NO в іншому випадку.
Приклад.
Вхідні дані.
abac
ababacaba
Вихідні дані.
ТАК

Пошук в ширину

Пошук в ширину BFS_queue
Хвильовий алгоритм є неефективною реалізацією пошуку в ширину, тому що на кожному кроці потрібно перебирати всі вершини, відбираючи ті, які були виявлені на останньому кроці. Для ефективної реалізації слід використовувати чергу.
 
У чергу будуть закладатися вершини після того, як до них буде визначено найкоротшу відстань.
 
З черги послідовно витягуються вершини та розглядаються ребра, що виходять з них. Якщо ребро веде у вершину, відстань до якої невизначено, то вона стає рівною на одиницю більше, ніж відстань до оброблюваної вершини, а нова вершина додається в кінець черги.
 
Таким чином, якщо з черги витягнута вершина з відстанню d, то в кінець черги будуть додаватися вершини з відстанню d + 1, тобто в будь-який момент виконання алгоритму чергу складається з вершин, віддалених на відстань d, за якими слідують вершини, віддалені на відстань d + 1.
 
Запишемо алгоритм пошуку в ширину на мові Pascal
 
v  ar Q, D: масив [1..1001] longint;
a: масив [1..1000, 1..1000] longint;
i, j, n, s, f, голова, хвіст, u, v: longint;
процедура Push (x: longint);
 почати
Q [хвіст]: = x;
хвіст: = хвіст + 1
 кінець; 
функція поп;
 почати
поп: = Q [голова];
голова: = голова + 1
 кінець; 
Почніть
{зчитуємо вихідні дані: кількість вершин графа, матрицю суміжності, номери стартової і кінцевої вершини}
читати (n);
для i: = 1 до n зробити
 для j: = 1 до n зробити
     читати (a [i, j]);
читати (s, f);
{заповнюємо масив довжин D}
для i: = 1 до n робити D [i]: = -1;
{відстань від старту до старту дорівнює нулю}
D [s]: = 0;
{кладемо стартову вершину в чергу. У черзі Q індекс head - номер першого елемента черги, tail - номер комірки після останнього елемента}
голова: 1;
хвіст: 1; 
Натиснути (ы);
{Поки черга не порожня, тобто, там є хоча б один елемент, тобто head і tail відрізняються хоча б на 1}
а голова <хвоста роблять
 почати
  u: = pop; // забираємо першу вершину з черги
{перебираємо всі вершини графа}
  для v: = 1 до n зробити
  {якщо знайшли сусіда, до якого відстань ще не обчислено}
  якщо (a [u, v] = 1) і [d [v] = -1)
   потім починай
           {обчислюємо його і кладемо цього сусіда в чергу}
           d [v]: = d [u] + 1;
           Push (v)
           кінець;
кінець;
написати (d [f]);
кінець 

Хвильовий алгоритм

Алгоритм пошуку в ширину (англ. Breadth-first search, BFS) дозволяє знайти найкоротші шляхи з однієї вершини незваженого (орієнтованого або неорієнтованого) графа до всіх інших вершин. Під найкоротшим шляхом мається на увазі шлях, що містить найменшу кількість ребер.
Нехай до вершини u знайдена найкоротша відстань і вона дорівнює d, а до вершини v найкоротша відстань не менше, ніж d. Тоді якщо вершини u і v - суміжні, то найкоротша відстань до вершини v дорівнює d + 1.
Через d [i] будемо позначати найкоротшу відстань до вершини i. Нехай початкова вершина має номер s, тоді d [s] = 0. Для всіх вершин суміжних з s відстань дорівнює 1. Для вершин, суміжних з тими, до яких відстань дорівнює 1, відстань дорівнює 2 (якщо тільки вона не дорівнює 0 або 1) і т. д. \
Хвильовий алгоритм здійснює процес обчислення найкоротших відстаней до вершин таким чином.
Для кожної вершини в масиві d будемо зберігати найкоротшу відстань до цієї вершини, якщо ж відстань невідома - будемо вважати її нескінченою.
На самому початку відстань до всіх вершин дорівнює нескінченість, крім початкової вершини, до якої відстань дорівнює 0.
Потім перебираємо всі вершини, до яких відстань дорівнює 0, перебираємо суміжні з ними вершини і для них записуємо відстань рівну 1. Потім перебираємо всі вершини, до яких відстань дорівнює 1, перебираємо їх сусідів, записуємо для них відстань, рівну 2 (якщо вона до цього була рівна -1). Потім перебираємо вершини, до яких відстань була рівна 2 і тим самим визначаємо вершини, до яких відстань дорівнює 3 і т. д. Цей цикл можна повторювати або поки виявляються нові вершини на черговому кроці, або n-1 раз (де n - число вершин в графі), так як довжина найкоротшого шляху в графі не може перевершувати n-1. 
процедура BFS (s: ціле число);
почати
для i: = 1 до n do d [i]: = нескінченність;
d [s]: = 0;
для k: = 1 до n-1 робити
 для i: = 1 до n зробити
  для j: = 1 до n зробити
    якщо (d [i] = k) і [a, i] = 1) і [d] [d] [i] +1)
      тоді d [j]: = d [i] +1
кінець; 

Топологічне сортування

Топологічне сортування
Нехай дано орієнтований граф, що не містить циклів. 
Тоді вершини цього графа можна впорядкувати так, що всі ребра йтимуть 
від вершин з меншим номером до вершин з більшим номером.
Для топологічного сортування графа досить запустити алгоритм DFS 
та при виході з вершини додати вершину в кінець списку з відповіддю. 
Після закінчення алгоритму список з відповіддю розгорнути 
в протилежному порядку.

пошук циклу в орієнтованому графі.

Ще одне застосування DFS - пошук циклу в орієнтованому графі.
Цикл в орієнтованому графі можна виявити при наявності ребра, що веде з поточної вершини в вершину, яка зараз знаходиться в стадії обробки, тобто алгоритм DFS зайшов у таку вершину, але ще не вийшов з неї.
У такому алгоритмі DFS будемо фарбувати вершини в три кольори.
Кольором 0 («білий») будемо позначати ще невідвідані вершини.
Кольором 1 («сірий») будемо позначати вершини в процесі обробки.
Кольором 2 («чорний») будемо позначати вже оброблені вершини.
Вершина фарбується в колір 1 при заході в цю вершину і в колір 2 - при виході.
Цикл в графі існує, якщо алгоритм DFS виявляє ребро, кінець якого пофарбований в колір 1.
процедура DFS (початок: ціле число);
 були: ціле;
почати
  Колір [початок]: = 1;
  для i: = 1 до n зробити
якщо [почати, i] = 1 
          тоді, якщо Color [i] = 0, то DFS (i)
                                 якщо Color [i] = 1, то CycleFound: = true;
   Колір [початок]: = 2;
кінець; 

Визначення кількості компонент зв'язності



Визначення кількості компонент зв'язності
Алгоритм обходу в глибину дозволяє вирішувати безліч різних завдань. Наприклад, реалізуємо за допомогою алгоритму обходу в глибину підрахунок числа компонент зв'язності в неорієнтованому графі.
Для цього будемо обходити всі вершини графа і перевіряти, чи була чергова вершина переглянута раніше. Якщо не була - то це означає, що знайдена нова компонента зв'язності. Для виділення всієї компоненти зв'язності необхідно запустити DFS від цієї вершини.
 NComp: = 0;
для i: = 1 до n зробити
 Якщо не відвідали [i] тоді
почати
NComp: = NComp + 1;
DFS (i);
кінець; 
 http://foxford.ru/wiki/informatika/algoritm-poiska-v-glubinu

Алгоритм пошуку (або обходу) в глибину



Алгоритм пошуку (або обходу) в глибину
 (англ. Depth-first search, DFS)
 дозволяє побудувати обхід орієнтованого або неорієнтованого графа, при якому відвідуються всі вершини, які доступні з початкової вершини. 
Результатом алгоритму пошуку в глибину є деякий маршрут, рухаючись по якому можна обійти послідовно всі вершини графа, які доступні з початкової вершини.
Обхід в глибину можна уявити собі таким чином. Нехай дослідник знаходиться в деякому лабіринті (графі) і він хоче обійти весь лабіринт (відвідати всі доступні вершини в графі). Дослідник знаходиться в деякій вершині і бачить ребра, що виходять з цієї вершини. Очевидна послідовність дій дослідника така:
  1.  Піти в якусь суміжну вершину.
  2. Обійти все, що досяжне з цієї вершини.
  3. Повернутися в початкову вершину.
  4. Повторити алгоритм для всіх інших невідвіданих вершин, суміжних з початковою.
Для реалізації алгоритму знадобиться відзначати, в яких вершинах був дослідник, а в яких - ні. Позначку робитимемо в списку Visited, де Visited [i] = True для відвіданих вершин, і Visited [i] = False для невідвіданих. Позначка «про відвідування вершини» ставиться при заході в цю вершину.
 Алгоритм обходу в глибину оформимо у вигляді рекурсивної процедури DFS, де start - номер вершини, з якої запускається обхід.
процедура DFS (початок: ціле число);
були: ціле;
почати
  isited [start]: = true;
для i: = 1 до n зробити
якщо (a [start, i] = 1) і (відвідав [i] = false)
потім DFS (i)
 кінець; 
У цьому алгоритмі n - число вершин у графі, вершини нумеруються числами від 1 до n, таблиця a зберігає матрицю суміжності. Для запуску алгоритму, наприклад, для вершини з номером start необхідно викликати DFS. Після цього виклику всі вершини, доступні з start, будуть відзначені в списку Visited
 
http://foxford.ru/wiki/informatika/algoritm-poiska-v-glubinu