Студопедия
Новини освіти і науки:
Контакти
 


Тлумачний словник






Алгоритм 1.

Розглянемо деяку перестановку з натуральних чисел 13 5 4 2

Знайдемо першу з кінця перестановки впорядковану пару (3 5). Перше число називають числом, що обриває. Хвіст перестановкиутворює послідовність чисел, яка починається з числа, що обриває.

Підалгоритм ревпорядкування хвоста перестановки.

1. замінити число, що обриває, на найменше з хвоста перестановки, яке більше його.

2. всі інші числа з хвоста перестановки разом з тим, що обриває розташивати впорядку зростання:

1 3 5 4 2 число, яке обриває - 3.

3 5 4 2 хвіст перестановки

Робота буде закінчена, коли всі числа будуть розташовані в порядку спадання.

 

Таблиця 4.1. Таблиця трасування створення перестановок

 

№ перестановки   перестановк а число, що обриває хвіст перестановки ревпорядкува ння хвоста перестановки
1 2 3 4 3 4 4 3
1 2 4 3 2 4 3 3 2 4
1 3 2 4 2 4 4 2
1 3 4 2 3 4 2 4 2 3
1 4 2 3 2 3 3 2
1 4 3 2 1 4 3 2 2 1 3 4
2 1 3 4 3 4 4 3
2 1 4 3 1 4 3 3 1 4
2 3 1 4 1 4 4 1
2 3 4 1 3 4 1 4 1 3
2 4 1 3 1 3 3 1
2 4 3 1 2 4 3 1 3 1 2 4
3 1 2 4 2 4 4 2
3 1 42 1 4 2 2 1 4
3 2 1 4 1 4 4 1
3 2 4 1 2 4 1 4 1 2
3 4 1 2 1 2 2 1
3 4 2 1 3 4 2 1 4 1 2 3
4 1 2 3 2 3 3 2
4 1 3 2 1 3 2 2 1 3
4 2 1 3 1 3 3 1
4 2 3 1 2 3 1 3 1 2
4 3 1 2 1 2 2 1
4 3 2 1 2 3 3 2

Таким чином маємо 4!=24 перестановки.

Алгоритм 1 зобразимо так:

 
 

 


рис. 4.1. Блок-схема алгоритму 1 побудови перестановок.

Для цього алгоритму треба використати підалгоритм впорядкування деякого буферного масиву, який ми називаємо хвостом перестановки.

Для розгляду другого алгоритму побудови перестановок використаємо

таке поняття, як обертання- це процес, в якому перше число стає на останнє місце.

 

Таблиця 4.2 Трасування створення перестановок за допомогою алгоритму 2.

 

№ перестановки перестановка    
1 2 3 4 m=4:<1 2 3 4> 2 3 4 1
2 3 4 1 m=4:<2 3 4 1> 3 4 1 2
3 4 1 2 m=4:<3 4 1 2> 4 1 2 3
4 1 2 3 m=4:<4 1 2 3> m=3:<l 2 3> 1 2 3 4 (Im=m) 3 1 2 4
3 1 2 4 m=3:<3 1 2> 2 3 1 4
2 3 1 4 m=3:<2 3 1> m=2: <1 2> 1 2 3 4 (Im=m) 2 1 3 4

 

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


Читайте також:

  1. Rete-алгоритм
  2. Алгоритм
  3. Алгоритм
  4. Алгоритм RLE
  5. Алгоритм безпосередньої заміни
  6. Алгоритм Берлекемпа-Мессі
  7. Алгоритм відшукання оптимального плану.
  8. Алгоритм Дейкстри.
  9. Алгоритм Деккера.
  10. Алгоритм Деккера.
  11. Алгоритм діагностики при травмах живота.




<== попередня сторінка | наступна сторінка ==>
Перестановка | Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:


 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.001 сек.