Меню
Блог
Учителю  /  Информатика  /  Бесплатные видеоуроки  /  Разбор решения задачи на массивы (упорядочение элементов)

Разбор решения задачи на массивы (упорядочение элементов)

В этом уроке информатики мы рассмотрим решение задачи на массив, дается детальный разбор

Дан массив элементами которого являются цифры 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)
Эту задачу можно решить любой сортировкой, но есть еще один простой вариант решения, который мы рассмотрим.

Свои вопросы, замечания и предложения оставьте в комментариях.

Спасибо за внимание.

Сохранить у себя:

Комментарии 10

Чтобы добавить комментарий зарегистрируйтесь или на сайт

Алексей, 31.01.2012 11:53
а просто использовать алгоритм, хотя бы пузырьковой сортировки нельзя было?
Проект Видеоуроки

Почему же нельзя :) 
Все можно

Марина, 23.01.2012 13:56
Дмитрий, большое вам спасибо за уроки, с программированием вообще тяжко, сама учусь.
developer, 02.01.2012 04:41
А если я на вход программы подам значение 1100? Программа феерично зациклится. А в таких языках как C/C++/C#/Java вы получите исключение.
   Согласитесь, для избежания проблем необходимо добавить элементарно модифицировать программу и добавить проверку
   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.
Afa, 27.11.2011 20:18
Здравствуйте уважаемый Дмитрий Тарасов! Я поблагодарю вас за помощь учителям.
Назира, 06.07.2011 14:48
Здравствуйте уважаемый Дмитрий Тарасов! Я получаю очень много полезной информации, спасибо Вам. У меня вопрос другой я хотела бы изучить С++. Вы не собираетесь создавать проекты по изучению этого языка программирования?
Элиза Мухамедовна, 16.03.2011 08:05
Уважаемый Дмитрий!Вы проделали очень большую и полезную работу и что замечательно рассказываете и показываете об этом всем,спасибо большое!Вашу методику можно применять и в высшем образовании на лаб.практ. занятиях.
xana, 06.02.2011 01:02
Добрый день Дмитрий. Я очень рада за Ваши успехи в олимпиаде. Желаю Вам творчества в работе. Спасибо за материалы по информатике.
Вера, 05.02.2011 04:15
Классные уроки! Спасибо за помощь учителям.
Вера, 04.02.2011 09:09
Спасибо
Кирилл, 02.02.2011 20:42
Здравствуйте , для начала поблагодарю вас за данный проект , очень много полезной информации нашел для себя . Вот хотелось бы поинтересоваться как просмотреть этот видеоурок в хорошем качестве ?
Проект Видеоуроки

Пока только так, как на сайте.