Вася изучил алгоритм сортировки пузырьком по неубыванию. Он решил реализовать его для массива целых чисел [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.
Смодулируем ситуацию, на каждой замене сравнивая масив с масивом получившимся у Васи
# Код на 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
Во-первых, поскольку запись числа содержит 3 цифры, то 381>=N^2 (подходят целые N<19) и 381<N^3 (N>7). Теперь разберем второе условие. Если отнять от 381 тройку, то в искомой системе счисления 381 будет заканчиваться на ноль. Это значит, что N является делителем числа 378. Легко проверить, что N=18 подходит под оба условия и является наибольшим возможным основанием в силу неравенства N<19