Главная страница
Навигация по странице:

  • Random

  • Environment

  • Алгоритмические языки_ Лабораторная работа №3 -... Методические указания к лабораторной работе 3 по дисциплине Алгоритмические языки и программирование для студентов специальности 230100 (ивт)


    Скачать 329 Kb.
    НазваниеМетодические указания к лабораторной работе 3 по дисциплине Алгоритмические языки и программирование для студентов специальности 230100 (ивт)
    Дата26.08.2021
    Размер329 Kb.
    Формат файлаdoc
    Имя файлаАлгоритмические языки_ Лабораторная работа №3 -...doc
    ТипМетодические указания
    #228015
    страница2 из 6
    1   2   3   4   5   6

    5. Теоретический материал

    Инициализация массива случайными числами


    Для выполнения лабораторной работы №3 придется пользоваться массивами большого размера. Размеры массивов в данной работе могут достигать 15 тысяч элементов, что не позволяет реализовать ввод данных с клавиатуры. Для решения этой задачи предлагается использовать инициализацию массива случайными числами.

    Для работы с генератором случайных чисел необходимо создать объект стандартного класса Random:

    Random Rnd = new Random();

    Инициализация массива выполняется с помощью метода Next класса Random и может выглядеть следующим образом:

    int maxValue = 100;

    int[] a = new int[1000];

    for (int i = 0; i < 1000; i++)

    a[i] = Rnd.Next(0, maxValue); // Случайное число от 0 до 100

    Измерение времени работы программы


    В задании на лабораторную работу требуется измерить время работы программы. Для этого удобно воспользоваться стандартным классом Environment, который содержит свойство TickCount, в котором содержится время (в миллисекундах), прошедшее с момента загрузки операционной системы. Чтобы определить время работы какого-либо фрагмента кода, необходимо выполнить два замера времени (до и после этого фрагмента), а потом вычислить разность полученных значений. Для перевода результата в секунды можно разделить его на 1000.

    Вот как может выглядеть текст функции Main(), в котором производится замер времени работы фрагмента кода:

    static void Main(string[] args)

    {

    // Здесь выполняется инициализация данных (ввод массивов и проч.)

    int t1 = Environment.TickCount;

    // Здесь выполняется основная работа программы

    ......

    int t2 = Environment.TickCount;

    // Печать затраченного времени на экране

    Console.WriteLine("Продолжительность работы: " + (t2 - t1) / 1000.0);

    // Печать полученного массива

    }

    Сортировка пузырьком


    Расположим массив сверху вниз, от нулевого элемента - к последнему.

    Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.



    После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию...

    Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.


    Алгоритм сортировки «пузырьком» представлен ниже:
    i-цикл от 0 до size с шагом 1

    j-цикл от size-1 до i с шагом -1

    если a[j-1] > a[j], то

    x = a[j-1]

    a[j-1] = a[j]

    a[j] = x

    все если

    все j-цикл

    все i-цикл
    Среднее число сравнений и обменов имеют квадратичный порядок роста: O(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.

    Сортировка выбором


    Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

    Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

    На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.


    Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Алгоритм сортировки выбором представлен ниже:

    i-цикл от 0 до size с шагом 1

    k = i

    x = a[i]

    j-цикл от i + 1 до size с шагом 1

    если a[j] < x, то

    k = j

    x = a[j]

    все если

    все j-цикл

    a[k] = a[i]

    a[i] = x

    все i-цикл
    Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

    n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = O(n2)
    Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

    Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

    1   2   3   4   5   6


    написать администратору сайта