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

0 голосов
31 просмотров

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

Информатика (22 баллов) | 31 просмотров
0

не понятно какой именно алгоритм пузырька используется. Есть немного разные варианты.

оставил комментарий (55.0k баллов)
0

Например в приведенном примере вариант [4, 5, 3, 1, 2] никогда не получится из [5, 4, 3, 2, 1]

оставил комментарий (55.0k баллов)
0

потому что будут замены 5 и 4 и сразу 5 и 3

оставил комментарий (55.0k баллов)
Дан 1 ответ
0 голосов
Правильный ответ

Смодулируем ситуацию, на каждой замене сравнивая масив с масивом получившимся у Васи

# Код на ruby 2.2.3p173
def zadanie(a,b)
    count = 0
    for j in 0...a.size-1
        for i in 0...a.size-j-1
            if a[i] > a[i + 1]
                a[i], a[i + 1] = a[i + 1], a[i]
                count += 1
                puts "Обмен №#{count} #{a[i+1]} и #{a[i]}, a = #{a}"
                return count if a == b
            end
        end
    end

    p count
    return a
end

# # Примеры применения
p zadanie( [5, 12, 9, 11, 19, 6, 4, 1, 18, 14, 7, 20, 10, 13, 2, 17, 3, 15, 8, 16] , [5, 4, 1, 6, 9, 7, 11, 10, 12, 2, 13, 3, 14, 15, 8, 16, 17, 18, 19, 20])

Вывод
Обмен №1 12 и 9
Обмен №2 12 и 11
a = [5, 9, 11, 12, 19, 6, 4, 1, 18, 14, 7, 20, 10, 13, 2, 17, 3, 15, 8, 16]
Обмен №3 19 и 6
Обмен №4 19 и 4
a = [5, 9, 11, 12, 6, 4, 19, 1, 18, 14, 7, 20, 10, 13, 2, 17, 3, 15, 8, 16]
Обмен №5 19 и 1
Обмен №6 19 и 18
a = [5, 9, 11, 12, 6, 4, 1, 18, 19, 14, 7, 20, 10, 13, 2, 17, 3, 15, 8, 16]
Обмен №7 19 и 14
Обмен №8 19 и 7
a = [5, 9, 11, 12, 6, 4, 1, 18, 14, 7, 19, 20, 10, 13, 2, 17, 3, 15, 8, 16]
Обмен №9 20 и 10
Обмен №10 20 и 13
a = [5, 9, 11, 12, 6, 4, 1, 18, 14, 7, 19, 10, 13, 20, 2, 17, 3, 15, 8, 16]
Обмен №11 20 и 2
Обмен №12 20 и 17
a = [5, 9, 11, 12, 6, 4, 1, 18, 14, 7, 19, 10, 13, 2, 17, 20, 3, 15, 8, 16]
Обмен №13 20 и 3
Обмен №14 20 и 15
a = [5, 9, 11, 12, 6, 4, 1, 18, 14, 7, 19, 10, 13, 2, 17, 3, 15, 20, 8, 16]
Обмен №15 20 и 8
Обмен №16 20 и 16
a = [5, 9, 11, 12, 6, 4, 1, 18, 14, 7, 19, 10, 13, 2, 17, 3, 15, 8, 16, 20]
Обмен №17 12 и 6
Обмен №18 12 и 4
a = [5, 9, 11, 6, 4, 12, 1, 18, 14, 7, 19, 10, 13, 2, 17, 3, 15, 8, 16, 20]
Обмен №19 12 и 1
Обмен №20 18 и 14
a = [5, 9, 11, 6, 4, 1, 12, 14, 18, 7, 19, 10, 13, 2, 17, 3, 15, 8, 16, 20]
Обмен №21 18 и 7
Обмен №22 19 и 10
a = [5, 9, 11, 6, 4, 1, 12, 14, 7, 18, 10, 19, 13, 2, 17, 3, 15, 8, 16, 20]
Обмен №23 19 и 13
Обмен №24 19 и 2
a = [5, 9, 11, 6, 4, 1, 12, 14, 7, 18, 10, 13, 2, 19, 17, 3, 15, 8, 16, 20]
Обмен №25 19 и 17
Обмен №26 19 и 3
a = [5, 9, 11, 6, 4, 1, 12, 14, 7, 18, 10, 13, 2, 17, 3, 19, 15, 8, 16, 20]
Обмен №27 19 и 15
Обмен №28 19 и 8
a = [5, 9, 11, 6, 4, 1, 12, 14, 7, 18, 10, 13, 2, 17, 3, 15, 8, 19, 16, 20]
Обмен №29 19 и 16
Обмен №30 11 и 6
a = [5, 9, 6, 11, 4, 1, 12, 14, 7, 18, 10, 13, 2, 17, 3, 15, 8, 16, 19, 20]
Обмен №31 11 и 4
Обмен №32 11 и 1
a = [5, 9, 6, 4, 1, 11, 12, 14, 7, 18, 10, 13, 2, 17, 3, 15, 8, 16, 19, 20]
Обмен №33 14 и 7
Обмен №34 18 и 10
a = [5, 9, 6, 4, 1, 11, 12, 7, 14, 10, 18, 13, 2, 17, 3, 15, 8, 16, 19, 20]
Обмен №35 18 и 13
Обмен №36 18 и 2
a = [5, 9, 6, 4, 1, 11, 12, 7, 14, 10, 13, 2, 18, 17, 3, 15, 8, 16, 19, 20]
Обмен №37 18 и 17
Обмен №38 18 и 3
a = [5, 9, 6, 4, 1, 11, 12, 7, 14, 10, 13, 2, 17, 3, 18, 15, 8, 16, 19, 20]
Обмен №39 18 и 15
Обмен №40 18 и 8
a = [5, 9, 6, 4, 1, 11, 12, 7, 14, 10, 13, 2, 17, 3, 15, 8, 18, 16, 19, 20]
Обмен №41 18 и 16
Обмен №42 9 и 6
a = [5, 6, 9, 4, 1, 11, 12, 7, 14, 10, 13, 2, 17, 3, 15, 8, 16, 18, 19, 20]
Обмен №43 9 и 4
Обмен №44 9 и 1
a = [5, 6, 4, 1, 9, 11, 12, 7, 14, 10, 13, 2, 17, 3, 15, 8, 16, 18, 19, 20]
Обмен №45 12 и 7
Обмен №46 14 и 10
a = [5, 6, 4, 1, 9, 11, 7, 12, 10, 14, 13, 2, 17, 3, 15, 8, 16, 18, 19, 20]
Обмен №47 14 и 13
Обмен №48 14 и 2
a = [5, 6, 4, 1, 9, 11, 7, 12, 10, 13, 2, 14, 17, 3, 15, 8, 16, 18, 19, 20]
Обмен №49 17 и 3
Обмен №50 17 и 15
a = [5, 6, 4, 1, 9, 11, 7, 12, 10, 13, 2, 14, 3, 15, 17, 8, 16, 18, 19, 20]
Обмен №51 17 и 8
Обмен №52 17 и 16
a = [5, 6, 4, 1, 9, 11, 7, 12, 10, 13, 2, 14, 3, 15, 8, 16, 17, 18, 19, 20]
Обмен №53 6 и 4
Обмен №54 6 и 1
a = [5, 4, 1, 6, 9, 11, 7, 12, 10, 13, 2, 14, 3, 15, 8, 16, 17, 18, 19, 20]
Обмен №55 11 и 7
Обмен №56 12 и 10
a = [5, 4, 1, 6, 9, 7, 11, 10, 12, 13, 2, 14, 3, 15, 8, 16, 17, 18, 19, 20]
Обмен №57 13 и 2
Обмен №58 14 и 3
a = [5, 4, 1, 6, 9, 7, 11, 10, 12, 2, 13, 3, 14, 15, 8, 16, 17, 18, 19, 20]

Ответ 58

(55.0k баллов)
Похожие задачи