Задать вопрос
28 февраля, 04:21

Вася изучил алгоритм сортировки пузырьком по неубыванию.

Он решил реализовать его для массива целых чисел [13, 18, 7, 4, 10, 14, 15, 17, 2, 5, 9, 16, 11, 3, 20, 6, 19, 12, 8, 1] так: выбираем два случайных соседних элемента в массиве, если левый больше правого, меняем их местами, иначе ничего не делаем. Из любопытства, после каждого обмена он выводил новый массив на экран.

Через какое-то время на экране оказался массив [4, 7, 2, 5, 10, 9, 13, 11, 3, 14, 6, 15, 12, 8, 1, 16, 17, 18, 19, 20], а компьютер завис. Сколько операций обмена было сделано за время работы программы? В качестве ответа укажите одно натуральное число, например, 100.

Пример. Пусть был массив [5, 4, 3, 2, 1], а через некоторое время появился массив [4, 5, 3, 1, 2].

Тогда за время работы программы было сделано две операции обмена - поменялись местами числа 5 и 4 и числа 2 и 1.

+2
Ответы (1)
  1. 28 февраля, 05:14
    0
    Назовём инверсией пару элементов массива, в котором элемент с меньшим номером больше элемента с большим номером. Заметим, что после каждого обмена число инверсий в массиве уменьшается на 1. Тогда, посчитав число инверсий до работы программы и после, и вычтя из первого второе, мы получим число операций обмена.

    Массив небольшой, и можно подсчитывать инверсии как угодно.

    python 3.5:

    before = [13, 18, 7, 4, 10, 14, 15, 17, 2, 5, 9, 16, 11, 3, 20, 6, 19, 12, 8, 1]

    after = [4, 7, 2, 5, 10, 9, 13, 11, 3, 14, 6, 15, 12, 8, 1, 16, 17, 18, 19, 20]

    def countInversions (arr) :

    counter = 0

    for i in range (len (arr) - 1) :

    for j in range (i + 1, len (arr)) :

    if arr[i] > arr[j]:

    counter + = 1

    return counter

    print (countInversions (before) - countInversions (after))

    Ответ: 60.
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «Вася изучил алгоритм сортировки пузырьком по неубыванию. Он решил реализовать его для массива целых чисел [13, 18, 7, 4, 10, 14, 15, 17, 2, ...» по предмету 📘 Информатика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы
Похожие вопросы по информатике
У Вити имеются три одинаковых непрозрачных пластиковых стакана. Он расставил их перед собой и написал чисола к1 к 2 к3 соотвественно на левом средном правом стаканах Патом витя придумал такой алгоритм перемещения стаканов меняем местами левый и
Ответы (1)
1. for + random a. вывести случайное количество случайных чисел b. вывести на экран 10 случайных чисел c. вывести на экран 10 случайных чисел, значение которых лежит в отрезке [0,10] d.
Ответы (1)
В записи m[7]=9 m обозначает 1) имя массива 2) имя элемента массива 3) номер элемента массива 4) значение элемента массива в записи m[7]=
Ответы (1)
1.) Вывести на экран одномерный целочисленный массив, состоящий из 10 целых чисел из диапазона [-100; 100] 2.) Задан одномерный целочисленный массив, состоящий из 7 случайных чисел.
Ответы (1)
Дан символьный массив А[N]. Определить для каждого символа массива А, сколько раз он встречается в массиве. (С++) Как это можно реализовать через метод сортировки пузырьком? И надо ли оно вообще?
Ответы (1)