Задача флага Нидерландов - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:57Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:31, 1 сентября 2022

2022-09-01T06:31:02Z

Shersh: /* Псевдокод */

2015-09-24T19:04:59Z

‎Псевдокод

Oxygen3 в 21:57, 7 июня 2015

2015-06-07T21:57:13Z

Oxygen3 в 21:56, 7 июня 2015

2015-06-07T21:56:47Z

Oxygen3 в 21:55, 7 июня 2015

2015-06-07T21:55:26Z

Oxygen3 в 21:51, 7 июня 2015

2015-06-07T21:51:37Z

Oxygen3 в 21:46, 7 июня 2015

2015-06-07T21:46:02Z

Oxygen3: Новая страница: «'''Задача флага Нидерландов''' (англ. ''Dutch national flag problem, DNF''). Флаг Нидерландов состоит из тре...»

2015-06-07T21:28:22Z

Новая страница: «'''Задача флага Нидерландов''' (англ. ''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>.
}}
===Пример===
<tex> [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] </tex><br>
<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\texttt{++}</tex>, <tex>right\texttt{--}</tex>.
===Псевдокод===
sort('''int''' a[])
'''int''' left = 1, right = n;
'''while''' (left < right)
'''while''' (arr[left] == 0 '''and''' left < right)
left++
'''while''' (arr[right] == 1 '''and''' left < right)
right--
'''if''' (left < right)
swap(a[left], a[right])
left++
right--
'''return''' a

==Сортировка набора, состоящего из 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> в конце.
}}
===Пример===
<tex> [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] </tex><br>
<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>, то меняем местами <tex>a[lo]</tex> и <tex>a[mid]</tex>, <tex>lo\texttt{++}</tex>, <tex>mid\texttt{++}</tex>.
# Если <tex>a[mid] = 1</tex>, то <tex>mid\texttt{++}</tex>.
# Если <tex>a[mid] = 0</tex>, то меняем местами <tex>a[mid]</tex> и <tex>a[hi]</tex>, <tex>hi\texttt{--}</tex>.

Инвариант работы алгоритма:
# <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>
===Псевдокод===
sort('''int''' a[])
'''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
'''return''' a
== См. также ==
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]

== Источники информации ==
* [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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]

← Предыдущая		Версия 16:05, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.		Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.

← Предыдущая		Версия 06:31, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.		Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.

@@ Строка 19: / Строка 19: @@
 ===Псевдокод===
-  '''int'''[] sort('''int'''[] a)
+  '''int'''[] sort('''int'''[] a):
       '''int''' left = 0, right = n - 1
       '''while''' (left < right)

@@ Строка 6: / Строка 6: @@
 Дан массив <tex>a[0..n-1]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется разделить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
 }}
 ===Пример===
 Исходный массив: <tex> a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]</tex> <br>
@@ Строка 38: / Строка 37: @@
 Дан массив <tex>a[0..n-1]</tex> из <tex>n</tex> чисел <tex>0</tex>, <tex>1</tex> и <tex>2</tex>. Требуется разделить их друг от друга так, чтобы сначала шли все <tex>0</tex>, потом все <tex>1</tex> и все <tex>2</tex> в конце.
 }}
 ===Пример===
 Исходный массив: <tex> a =  [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]</tex><br>

@@ Строка 8: / Строка 8: @@
 ===Пример===
-Исходный массив: <tex> a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]</tex>
+Исходный массив: <tex> a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]</tex> <br>
 Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex>
@@ Строка 40: / Строка 40: @@
 ===Пример===
-Исходный массив: <tex> a =  [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]</tex>
+Исходный массив: <tex> a =  [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]</tex><br>
 Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex>

@@ Строка 4: / Строка 4: @@
 {{Задача
 |definition =
-Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется разделить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
+Дан массив <tex>a[0..n-1]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется разделить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
 }}
@@ Строка 12: / Строка 12: @@
 ===Алгоритм===
-Будем поддерживать два указателя. Инициализируем первый индекс <tex>left = 1</tex> и второй индекс <tex>right = n</tex>.
+Будем поддерживать два указателя. Инициализируем первый индекс <tex>left = 0</tex> и второй индекс <tex>right = n - 1</tex>.
 У будем делать следующее пока <tex>left < right</tex>
@@ Строка 21: / Строка 21: @@
 ===Псевдокод===
   '''int'''[] sort('''int'''[] a)
-      '''int''' left = 0, right = n - 1;
+      '''int''' left = 0, right = n - 1
       '''while''' (left < right)
           '''while''' (arr[left] == 0 '''and''' left < right)
@@ Строка 36: / Строка 36: @@
 {{Задача
 |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> в конце.
+Дан массив <tex>a[0..n-1]</tex> из <tex>n</tex> чисел <tex>0</tex>, <tex>1</tex> и <tex>2</tex>. Требуется разделить их друг от друга так, чтобы сначала шли все <tex>0</tex>, потом все <tex>1</tex> и все <tex>2</tex> в конце.
 }}
@@ Строка 44: / Строка 44: @@
 ===Алгоритм===
-Будем поддерживать три указателя. Инициализация: <tex>lo = 1; mid = 1; hi = n;</tex>.
+Будем поддерживать три указателя. Инициализация: <tex>lo = 0; mid = 0; hi = n - 1</tex>.
 У будем делать следующее пока <tex>mid \leqslant right</tex>
@@ Строка 52: / Строка 52: @@
 Инвариант работы алгоритма:
-# <tex>a[1..lo-1] = 0</tex>
+# <tex>a[0..lo-2] = 0</tex>
-# <tex>a[lo..mid-1] = 1</tex>
+# <tex>a[lo-1..mid-2] = 1</tex>
-# <tex>a[mid..hi]</tex> неизвестны
+# <tex>a[mid-1..hi-1]</tex> неизвестны
-# <tex>a[hi+1..n] = 2</tex>
+# <tex>a[hi..n-1] = 2</tex>
 ===Псевдокод===
   '''int'''[] sort('''int'''[] a)
-      '''int''' lo = 0, mid = 0, hi = n - 1;
+      '''int''' lo = 0, mid = 0, hi = n - 1
       '''while''' mid <tex>\leqslant</tex> right
           '''switch''' (a[mid])