Developing.ru

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

Переезжает в Алгоритмы, так как относится к иследованию условий, влияющих на эффективнсть сортирови пузырьком.

Давайте уточнять условия задачи:
1) заменить элемент надо в упорядоченном или в любом массиве?
2) какого рода замена имеется в виду? Если я скажу, что "если в отсортированном массиве мы заменим число на другое, равное ему топотребуется 0 перестановок при сортировке", то такое утверждение ничуть не противоречит условию задачи и (увы) является ответом на Ваш вопрос. Наверное все-таки Вы что-то другое имели в виду

Нет, массив еще не упорядочен, в том то и смысл задачи, что мы должны заменить одно число так, чтоб в сортировке пузырьком было меньше всего перестановок=)

Думаю, задача сводится к поиску наименьшего в массиве, после чего присвоить первому элементу массива значение меньше найденного. Правда, возможен вариант, когда наименьший элемент первый, тогда выбирать нужно между 2-м и последним и менять 2-й элемент, если он не наименьший и т.д. Поскольку в пузырьковой сортировке наименьший элемент "всплывает" к началу массива, то, наверное, это правильно.

Я очень запуталась!

Ну помогииите!

Чем? Вариант я предложил. Как вы думаете, что ещё можно предложить по таким образом сформулированной задаче? Конкретизируйте вопрос.