Разбор решения задачи на массивы (упорядочение элементов)
Плеер:
YouTube
Вконтакте
В этом уроке информатики мы рассмотрим решение задачи на массив, дается детальный разбор
Дан массив элементами которого являются цифры 0,1,2. Нужно упорядочить эти элементы не используя второй массив. Например при n=10 до a (2,2,1,2,1,0,0,2,1,0) после a (0,0,0,1,1,1,2,2,2,2)
Эту задачу можно решить любой сортировкой, но есть еще один простой вариант решения, который мы рассмотрим.
Свои вопросы, замечания и предложения оставьте в комментариях.
Спасибо за внимание.
Получите комплекты видеоуроков + онлайн версии
Сохранить у себя:
Похожие записи
,
Бесплатные видеоуроки по информатике
25913
Нравится
0
Почему же нельзя :)
Все можно
Согласитесь, для избежания проблем необходимо добавить элементарно модифицировать программу и добавить проверку
program smas;
const
size = 10;
var
a: array [1..size] of byte;
&<Пук-пук>;
k: integer;
begin
read(k);
if k > size then
k := size;
// остальной код программы
end.
Далее вопрос по циклам:
for i := n + 1 to n + e do
a[i] := 1;
for i := n + e + 1 to n + e + d do
a[i] := 2;
Зачем вы все время вычисляете начальное значение i? Вы же в предыдущем цикле получили его значение и больше не меняли его.
Далее - вы же говорили, что сумма n + e + d будет равна k(что очевидно), но зачем вы в последнем цикле еще раз вычисляете это k?
В итоге с исправлением этих ситуаций код приобретает более простой и понятный вид
for i := i to n + e do
a[i] := 1;
for i := i to k do
a[i] := 2;
А теперь по поводу самого алгоритма.
Чем использование массива принципиально отличается от использования N переменных, кроме как способа размещения данных в памяти?
Если не использовать массивы - только сортировка. Ваш алгоритм в таком случае является крайне неудобным и не универсальным, т.к. при ширине допустимых значений, например 10 - код становится уже достаточно неудобным.
Но сложность алгоритмов сортировки в лучшем случае O(n), в худшем такие алгоритмы дают сложность O(n log n), алгоритмы со сложностью большей чем O(n log n) не рассматриваю. Т.е. в лучшем случае они дают такую же сложность, что и использование массивов и ваш алгоритм. Но с точки зрения программиста - ваш код является крайне неудобным и на практике использован никогда не будет. А если рассматривать не буквальное выполнения ограничения на использование массива, а физическое понимание происходящего в программе, то вы не выполнили это требование, т.к. использовали тот же массив, только разбросали его элементы по памяти.
Вот решение с массивами:
program smas;
const
size = 25;
countDiff = 16;
var
a: array [1..size] of byte;
i, j, l, tmp: integer;
k: integer;
counter: array [1..countDiff] of byte;
begin
read(k);
if k > size then
k := size;
for i := 1 to countDiff do
counter[i] := 0;
for i := 1 to k do
begin
a[i] := random(countDiff);
write(a[i]:3);
tmp := a[i] + 1;
counter[tmp] := counter[tmp] + 1;
end;
writeln;
l := 1;
for i := 1 to countDiff do
begin
tmp := i - 1;
for j := 1 to counter[i] do
begin
a[l] := tmp;
l := l + 1;
end;
end;
for i := 1 to k do
write(a[i]:3);
writeln;
end.
Пока только так, как на сайте.