Голландский флаг

Разминка для мозгов » Задачи » Голландский флаг

Добавлено: 09.02.09 в 12:00

Камешки: красные, белые, синие располагаются в столбик. Надо упорядочить камешки таким образом, чтобы их цвета шли в том же порядке, что и цвета голландского флага - красные, белые, синие.

Предположим, что камешки пронумерованы в порядке их следования сверху вниз. Камешками ведает робот. Он может выполнять 2 команды:

определить цвет i-го камня (1 <= i <= n)
поменять местами i-ый и j-ый камешки (1 <= i,j <= n)

n - число камешков в столбике.

У этой задачи пока что нет ответа/решения. Вы можете прислать свой вариант в комментарии.

источник: Книга "100 задач по программированию"

Комментарии

Google says:

Аноним (16.02.10):

если у робота нет команды сравнения, то задача бессмысленна. если есть, то:

шаг 1. проиндексировать цвета;
шаг 2. отсортировать по номерам цветов любым алгоритмом сортировки

PS строго говоря, у робота должны быть ещё пара-тройка-четвёрка доступных примитивов

Аст (31.03.10):

Сравнения тут незачем.
n раз проверяем камни от 2 до n и меняем местами камни i, i-1 если он красный;
n раз проверяем камни от 1 до n-1 и меняем местами камни i, i+1 если он синий.
после этого все камни будут упорядочены как требуется в условии.

bgrfh (26.09.10):

копец я не смог решить ету задачу.
блин я не знаю цвета голланского флага!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
ааааааааааааааааааааааааааааааааааааааааааааааааааааааааАААААААААААААААААААА

CAIIIA (19.12.10):

по столбику придется пройтись минимум два раза:
1.закидываем первый цвет(запоминая, номер поавшегося не "первого" цвета, меняем "первый цвет")
2.второй раз собираем второй цвет, третий автоматически остаётся на верху.

		Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи. Petruchek.Info

Petruchek.Info

Голландский флаг