Вася выучил алгоритм сортировки пузырьком по неубыванию. Он решил реализовать его
Вася выучил метод сортировки пузырьком по неубыванию. Он решил реализовать его для массива целых чисел [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.
Задать свой вопрос
Пашок
не понятно какой конкретно алгоритм пузырька употребляется. Есть немножко различные варианты.
Zalepa Anna
К примеру в приведенном образце вариант [4, 5, 3, 1, 2] никогда не получится из [5, 4, 3, 2, 1]
Валерий Лабизов
поэтому что будут подмены 5 и 4 и сразу 5 и 3
1 ответ
Галя Гаврюсева
Смодулируем ситуацию, на каждой подмене сравнивая масив с масивом получившимся у Васи
Код на 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] gt; 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
Код на 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] gt; 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
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
задание экономиоти
Рассмотри ситуацию: человек живёт на Крайнем Се-вере. С помощью каких
Экономика.
Человек живет на Крайнем Севере. С помощью каких благ удовлетворяются потребности
Экономика.
там лежат три яйца.у дома рос клен.Это гнездо сойки.на клёне гнездо
Русский язык.
Тыныштық күйіндегі карусель 35 с-та 3,0 рад/с бұрыштық жылдамдықпен үдей қозғалады.
Разные вопросы.
Сочинение на тему "Русский язык не сможет умереть!"
Математика.
Приветствую!
Меня зовут Станислав, я представляю компанию under.site.
Хотел бы предложить интересное решение
Разные вопросы.
Масса трёх одинаковых пакетов чая 180г чему равна масса
Математика.
Газообразный аммиак объёмом 2.24 л (н.у.) был полностью поглощён 14.68 мл
Химия.
Упражнение 2 Выпишите глаголы и вставьте пропущенные буквы
Русский язык.
Радиус окружности, описанной около равностороннего треугольника, равен 6. Найдите сторону треугольника
Геометрия.
Облако тегов