Відмінності між версіями «* Типи алгоритмів»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 11 проміжних версій цього учасника)
Рядок 1: Рядок 1:
−
+
<center><h1>'''Типи алгоритмів'''</h1></center>
−
В алгоритмах команди записуються один за одним у певному порядку. Виконуються вони не обов'язково в записаній послідовності: залежно від порядку виконання команд можна виділити три типи алгоритмів:
+
  
−
•  лінійні алгоритми;
+
Є 4 типи алгоритмів:
  
−
•  алгоритми з розгалуженнями;
+
- прості;
  
−
•  алгоритми з повтореннями.
+
- розгалужені;
  
−
+
- циклічні;
  
−
<center>'''Лінійні алгоритми'''</center>
+
- універсальні.   
 +
   
  
−
+
'''Лінійні алгоритми (прості)'''
−
Алгоритм, у якому команди виконуються в порядку їх запису, тобто послідовно один за одним, називається лінійним.
+
  
−
Наприклад, лінійним є наступний алгоритм посадки дерева:
+
[[Файл:Bbb.jpg|350px]]
  
−
1)  викопати в землі ямку;
 
  
−
2) вилучити в ямку саджанець;
+
'''Алгоритми з розгалуженнями'''  
  
−
3)  засипати ямку із саджанцем землею;
+
[[Файл:Iges.jpg|350px]]
  
−
4)  полити саджанець водою.
 
  
−
+
'''Алгоритми з повтореннями (циклічні)'''  
−
<center>'''Алгоритми з розгалуженнями'''</center>
+
  
−
Ситуації, коли заздалегідь відома послідовність необхідних дій, зустрічаються вкрай рідко. У житті часто доводиться ухвалювати рішення залежно від обстановки. Якщо йде дощ, ми беремо парасоль і надягаємо плащ; якщо пекуче, надягаємо легкий одяг. Зустрічаються й більш складні умови вибору, У деяких випадках від обраного рішення залежить подальша доля людини.
+
[[Файл:Загруже.jpg|350p]]
  
−
Логікові ухвалення рішення можна описати так:
 
  
−
ЯКЩО ТО ІНАКШЕ
+
'''Універсальні алгоритми''' – це такі, які містять в собі вище перечисленні  алгоритми.
  
−
''Приклади:''
 
  
−
•  ЯКЩО прагнеш бути здоровий, ТО загартовуйся, ІНАКШЕ валяйся весь день на дивані;
+
<center><h1>'''Алгоритми сортування'''</h1></center>
  
−
•  ЯКЩО  низько  ластівки  літають, ТО  буде  дощ, ІНАКШЕ дощу не буде;
+
Група 1:
  
−
•  ЯКЩО уроки виучені, ТО йди гуляти, ІНАКШЕ вчи уроки.
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B2%D0%B8%D0%B1%D0%BE%D1%80%D0%BE%D0%BC сортування вибором]
  
−
У деяких випадках можуть бути відсутні;
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%BE%D1%8E сортування вставкою]
  
−
ЯКЩО ТО
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BE%D0%B1%D0%BC%D1%96%D0%BD%D0%BE%D0%BC сортування обміном]
  
−
''Приклад:''
 
  
−
•  ЯКЩО назвався груздем, ТО полізай у кузов.
+
Група 2:
  
−
Форма організації дій, при якій залежно від виконання деякої умови відбувається одна або інша послідовність кроків, називається розгалуженням.
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BF%D1%96%D0%B4%D1%80%D0%B0%D1%85%D1%83%D0%BD%D0%BA%D0%BE%D0%BC сортування підрахунком]
  
−
Зобразимо б виді блок-схеми послідовність дій учня 6 класу Мухіна Васі, яку він уявляє собі так: «Якщо Павлик будинку, будемо вирішувати завдання по математиці. А якщо ні, то слід подзвонити Марині й разом готовити доповідь по біології. Якщо ж Марини немає будинку, то треба сісти за твір.»
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%B0_%D1%80%D0%BE%D0%B7%D1%80%D1%8F%D0%B4%D0%B0%D0%BC%D0%B8 сортування за розрядами]
  
−
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BA%D0%BE%D0%BC%D1%96%D1%80%D0%BA%D0%B0%D0%BC%D0%B8 сортування комірками]
  
−
<center>'''Алгоритми з повтореннями'''</center>
 
  
−
+
Група 3:
−
На практиці часто зустрічаються завдання, у яких одне або кілька дій буває необхідно повторити кілька раз, поки дотримується деяке заздалегідь установлене умова.
+
  
−
Форма організації дій, при якій виконання однієї й тієї ж послідовності команд повторюється, поки виконується деяке заздалегідь установлене умова, називається циклом (повторенням).
+
[http://uk.wikipedia.org/wiki/%D0%9F%D1%96%D1%80%D0%B0%D0%BC%D1%96%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B5_%D1%81%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F пірамідальне сортування]
  
−
Алгоритм, що містить цикли, називається циклічним алгоритмом або алгоритмом з повтореннями.
+
[http://uk.wikipedia.org/wiki/%D0%A8%D0%B2%D0%B8%D0%B4%D0%BA%D0%B5_%D1%81%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F швидке сортування]
  
−
Ситуація, при якій виконання циклу ніколи не закінчується, називається зацикленням. Слід розробляти алгоритми, що не допускають таких ситуацій.
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%BB%D0%B8%D1%82%D1%82%D1%8F%D0%BC сортування злиттям]
  
−
Розглянемо приклад з математики.
 
  
−
Натуральне число називають простим, якщо воно має тільки два дільники: одиницю й саме це число .
+
Група 4:
  
−
2, 3, 5, 7 — прості числа; 4, 6, 8 — ні. В III столітті до нашої ери грецький математик Ератосфен запропонував наступний алгоритм для знаходження всіх простих чисел, менших заданого числа n;
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%B7%D0%BB%D0%B8%D1%82%D1%82%D1%8F%D0%BC_%D0%BC%D0%BE%D0%B4%D0%B8%D1%84%D1%96%D0%BA%D0%BE%D0%B2%D0%B0%D0%BD%D0%B5 сортування злиттям модифіковане]
  
−
1) виписати всі натуральні числа від 1 до n;
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0 сортування Шелла]
  
−
2) викреслити 1;
 
  
−
3) підкреслити найменше з невідмічених чисел;
+
Група 5:
  
−
4) викреслити всі числа, кратні підкресленому на попередньому кроці;
+
[http://uk.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%BE%D1%8E Сортування перестановкою]
  
−
5) якщо в списку є невідмічені числа, то перейти до кроку 3, а якщо ні, то всі підкреслені числа — прості.
 
  
−
Це циклічний алгоритм. При його виконанні повторення кроків 3-5 відбувається, поки у вихідному списку залишаються невідмічені числа.
+
 
 +
[http://lpml-uko.blogspot.com/2011/12/10.html Деякі алгоритми сортування під час танцю]

Поточна версія на 17:34, 31 жовтня 2012

Типи алгоритмів

Є 4 типи алгоритмів:

- прості;

- розгалужені;

- циклічні;

- універсальні.


Лінійні алгоритми (прості)

Bbb.jpg


Алгоритми з розгалуженнями

Iges.jpg


Алгоритми з повтореннями (циклічні)

350p


Універсальні алгоритми – це такі, які містять в собі вище перечисленні алгоритми.


Алгоритми сортування

Група 1:

сортування вибором

сортування вставкою

сортування обміном


Група 2:

сортування підрахунком

сортування за розрядами

сортування комірками


Група 3:

пірамідальне сортування

швидке сортування

сортування злиттям


Група 4:

сортування злиттям модифіковане

сортування Шелла


Група 5:

Сортування перестановкою


Деякі алгоритми сортування під час танцю

Отримано з https://wiki.cusu.edu.ua/index.php?title=*_Типи_алгоритмів&oldid=78583