Вопрос по информатике:
Вася изучил алгоритм сортировки пузырьком по неубыванию.
Он решил реализовать его для массива целых чисел [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.
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 28.09.2018 00:34
- Информатика
- remove_red_eye 13801
- thumb_up 21
Ответы и объяснения 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.
- 28.09.2018 19:44
- thumb_up 18
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.