55
правок
Изменения
Новая страница: «'''Проблема флага Нидерладндов''' (англ. ''Dutch national flag problem, DNF'') {{---}} задача дискретной матема...»
'''Проблема флага Нидерладндов''' (англ. ''Dutch national flag problem, DNF'') {{---}} задача дискретной математики, которую предложил Эдсгер Дейкстра. Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.
==Сортировка набора, состоящего из 0 и 1==
{{Задача
|definition =
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется отелить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
}}
===Пример===
Input array = <tex> [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] </tex><br>
Output array = <tex> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex>
===Алгоритм===
Будем поддерживать два указателя. Инициализируем первый индекс <tex>left = 1</tex> и второй индекс <tex>right = n</tex>.
У будем делать следующее пока <tex>left < right</tex>
# Увеличиваем <tex>left</tex> на <tex>1</tex> пока не <tex>a[left] = 0</tex>;
# Уменьшаем <tex>right</tex> на <tex>1</tex> пока не <tex>a[right] = 1</tex>;
# Если <tex>left < right</tex>, то меняем местами <tex>a[left]</tex> и <tex>a[right]</tex>, <tex>left++</tex>, <tex>right--</tex>.
===Псевдокод===
'''int''' left = 1, right = n;
'''while''' (left < right)
'''while''' (arr[left] == 0 && left < right)
left++
'''while''' (arr[right] == 1 && left < right)
right-–
'''if''' (left < right)
swap(a[left], a[right])
left++
right–
==Сортировка набора, состоящего из 0, 1 и 2==
{{Задача
|definition =
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex>, <tex>1</tex> и <tex>2</tex>. Требуется отелить их друг от друга так, чтобы сначала шли все <tex>0</tex>, потом все <tex>1</tex> и все <tex>2</tex> в конце.
}}
===Пример===
Input array = <tex> [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] </tex><br>
Output array = <tex> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex>
===Алгоритм===
Будем поддерживать три указателя. Инициализация: <tex>lo = 1; mid = 1; hi = n;</tex>.
У будем делать следующее пока <tex>mid \leqslant right</tex>
# Если <tex>a[mid] = 0</tex>, то меняем местами a[lo] и a[mid], lo++, mid++;
# Если <tex>a[mid] = 1</tex>, то mid++;
# Если <tex>a[mid] = 0</tex>, то меняем местами a[mid] и a[hi], hi--;
Инвариант работы алгоритма:
# <tex>a[1..lo-1] = 0</tex>
# <tex>a[lo..mid-1] = 1</tex>
# <tex>a[mid..hi]</tex> неизвестны
# <tex>a[hi+1..n] = 2</tex>
===Псевдокод===
'''int''' lo = 1, mid = 1, hi = n;
'''while''' mid <tex>\leqslant</tex> right
'''switch''' (a[mid])
'''case''' 0:
swap(a[lo++], a[mid++]);
break;
'''case''' 1:
mid++;
break;
'''case''' 2:
swap(a[mid], a[hi--]);
break;
== Источники информации ==
* [http://en.wikipedia.org/wiki/Dutch_national_flag_problem Wikipedia {{---}} Dutch national flag problem]
* [http://www.geeksforgeeks.org/segregate-0s-and-1s-in-an-array-by-traversing-array-once/ GeeksforGeeks {{---}} Segregate 0s and 1s in an array]
* [http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/ GeeksforGeeks {{---}} Sort an array of 0s, 1s and 2s]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
==Сортировка набора, состоящего из 0 и 1==
{{Задача
|definition =
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется отелить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
}}
===Пример===
Input array = <tex> [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] </tex><br>
Output array = <tex> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex>
===Алгоритм===
Будем поддерживать два указателя. Инициализируем первый индекс <tex>left = 1</tex> и второй индекс <tex>right = n</tex>.
У будем делать следующее пока <tex>left < right</tex>
# Увеличиваем <tex>left</tex> на <tex>1</tex> пока не <tex>a[left] = 0</tex>;
# Уменьшаем <tex>right</tex> на <tex>1</tex> пока не <tex>a[right] = 1</tex>;
# Если <tex>left < right</tex>, то меняем местами <tex>a[left]</tex> и <tex>a[right]</tex>, <tex>left++</tex>, <tex>right--</tex>.
===Псевдокод===
'''int''' left = 1, right = n;
'''while''' (left < right)
'''while''' (arr[left] == 0 && left < right)
left++
'''while''' (arr[right] == 1 && left < right)
right-–
'''if''' (left < right)
swap(a[left], a[right])
left++
right–
==Сортировка набора, состоящего из 0, 1 и 2==
{{Задача
|definition =
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex>, <tex>1</tex> и <tex>2</tex>. Требуется отелить их друг от друга так, чтобы сначала шли все <tex>0</tex>, потом все <tex>1</tex> и все <tex>2</tex> в конце.
}}
===Пример===
Input array = <tex> [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] </tex><br>
Output array = <tex> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex>
===Алгоритм===
Будем поддерживать три указателя. Инициализация: <tex>lo = 1; mid = 1; hi = n;</tex>.
У будем делать следующее пока <tex>mid \leqslant right</tex>
# Если <tex>a[mid] = 0</tex>, то меняем местами a[lo] и a[mid], lo++, mid++;
# Если <tex>a[mid] = 1</tex>, то mid++;
# Если <tex>a[mid] = 0</tex>, то меняем местами a[mid] и a[hi], hi--;
Инвариант работы алгоритма:
# <tex>a[1..lo-1] = 0</tex>
# <tex>a[lo..mid-1] = 1</tex>
# <tex>a[mid..hi]</tex> неизвестны
# <tex>a[hi+1..n] = 2</tex>
===Псевдокод===
'''int''' lo = 1, mid = 1, hi = n;
'''while''' mid <tex>\leqslant</tex> right
'''switch''' (a[mid])
'''case''' 0:
swap(a[lo++], a[mid++]);
break;
'''case''' 1:
mid++;
break;
'''case''' 2:
swap(a[mid], a[hi--]);
break;
== Источники информации ==
* [http://en.wikipedia.org/wiki/Dutch_national_flag_problem Wikipedia {{---}} Dutch national flag problem]
* [http://www.geeksforgeeks.org/segregate-0s-and-1s-in-an-array-by-traversing-array-once/ GeeksforGeeks {{---}} Segregate 0s and 1s in an array]
* [http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/ GeeksforGeeks {{---}} Sort an array of 0s, 1s and 2s]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
