j := 0;
for i := 0 to arrSize-1 do
begin
if (arr <> 1) then
begin
arr[j] = arr;
j := j + 1;
end
end;
for i := j to arrSize-1 do
arr := 1;
(Паскаль) Упорядочевание одномерного массива
Добрый вечер уважаемому сайту. Помогите решить задачку.
У меня небольшой вопрос по массиву на Pascal.
Есть массив состоящий из 10 элементов вида: 0 1 1 1 1 0 0 0 0 0
Надо сделать массив: 0 0 0 0 0 0 1 1 1 1 путем того, что единицы переместились по массиву.
У меня небольшой вопрос по массиву на Pascal.
Есть массив состоящий из 10 элементов вида: 0 1 1 1 1 0 0 0 0 0
Надо сделать массив: 0 0 0 0 0 0 1 1 1 1 путем того, что единицы переместились по массиву.
ИМХО. Довольно странное задание.
Тут смотря как правило формулировать. Можно задаться правилом чтоб все единицы в массиве перенести в его конец, а остальную часть не трогать, можно просто отсортировать масив.
Напиши бульбашку. Помоему она тут будет самой уместной.
Тут смотря как правило формулировать. Можно задаться правилом чтоб все единицы в массиве перенести в его конец, а остальную часть не трогать, можно просто отсортировать масив.
Напиши бульбашку. Помоему она тут будет самой уместной.
Нужно просто переместить единицы в конец, сортировка в данном случае не причём.
Ну тогда чтото типа такого (псевдокод)
Надеюсь нигде не ошибся. Програмку сам заделаеш.
Код:
Надеюсь нигде не ошибся. Програмку сам заделаеш.
Спасибо, правда всё нормально получается.
А если в массиве будет так 2 1 1 1 1 0 0 0 0 0, чтобы массив стал
0 0 0 0 0 2 1 1 1 1 т.е передвигались любые числа кроме нуля в массиве. Как можно это сделать?
И такой вропрос как можно сделать задержку по времени, чтобы показать движение чисел по массиву?
0 0 0 0 0 2 1 1 1 1 т.е передвигались любые числа кроме нуля в массиве. Как можно это сделать?
И такой вропрос как можно сделать задержку по времени, чтобы показать движение чисел по массиву?
Цитата: АлексейМ
Нужно просто переместить единицы в конец, сортировка в данном случае не причём.
Это и есть частный случай сортировки. Вероятно, наиболее подходит радиксная. Два прохода по массиву.
Цитата: АлексейМ
А если в массиве будет так 2 1 1 1 1 0 0 0 0 0, чтобы массив стал
0 0 0 0 0 2 1 1 1 1 т.е передвигались любые числа кроме нуля в массиве. Как можно это сделать?
И такой вропрос как можно сделать задержку по времени, чтобы показать движение чисел по массиву?
0 0 0 0 0 2 1 1 1 1 т.е передвигались любые числа кроме нуля в массиве. Как можно это сделать?
И такой вропрос как можно сделать задержку по времени, чтобы показать движение чисел по массиву?
Ты говорил что единицы в конец. Тут получается что нули в начало. Сути дела это не меняет. Делаеш примерно тоже, но идеш с конца в начало и пропускаеш/дописываеш не 1, а 0
Цитата: andriano
Это и есть частный случай сортировки. Вероятно, наиболее подходит радиксная. Два прохода по массиву.
Не знаю про радиксную сортировку, но в даном случае сортировка вообще ни при чем. И достаточно одного прохода. Смотри мой код выше.
Цитата: Rebbit
Не знаю про радиксную сортировку, но в даном случае сортировка вообще ни при чем. И достаточно одного прохода. Смотри мой код выше.
1. Не "вообще ни при чем", а именно она и есть. Вне зависимости от тогог, что лично ты знаешь, и что - нет.
2. Если проход один, зачем цикла два?
Цитата: andriano
1. Не "вообще ни при чем", а именно она и есть. Вне зависимости от тогог, что лично ты знаешь, и что - нет.
Перемещение по масиву и сортировка - разние вещи. Сортировка за О(N) невозможна а тут пожалуйста.
Цитата: andriano
2. Если проход один, зачем цикла два?
Сори, я с утра после праздника плохо соображаю. Подумал про два вложеных цикла. Да за два прохода надо. Хотя именно для этой задачи можно и в одном цикле с двумя индексами.
Цитата: Rebbit
Перемещение по масиву и сортировка - разние вещи. Сортировка за О(N) невозможна а тут пожалуйста.
А кто сказал, что сортировка за O(N) невозможна?
В общем случае - да, невозможна. А в частном (когда нужно упорядочить множество элементов, принимающих конечное число значений) - запросто.
Судя по первоначальному письму, элементы могут принимать только два значения: 0 и 1. Следовательно, на первом подходе подсчитываем количество тех и других, а на втором - заполняем массив. (как вариант: на первом проходе подсчитываем количества и обнуляем, а на втором - заполняем только единицы в верхней части массива).
Кстати, последнее решение, пожалуй, лучше всего, т.к. не содержит условных переходов (кроме возврата к началу цикла, который хорошо предсказывается процессором), на которых сбивается предсказатель ветвлений, и из-за которых происходят существенные задержки выполнения программы на суперскалярном процессоре.
[COLOR=Red]Автору нарушение: в Паскаль разрешено задавать вопросы только если есть свои нароботки, а не написание кода с нуля. Также называй нормально темы. Название должно отражать суть вопроса, а не его общую тематику "Задача с одномерным массивом".[/COLOR]
