Question

Python. Даны два числа n и k. Вывести перестановку из n чисел (n чисел от 1 до n без повторений) такую, чтобы сортировка пузырьком по возрастанию на соответствующем массиве сделала ровно k обменов. Если возможных ответов несколько — выведите любой.

Answer 1

Ответ:

n, k = map(int, input().split())

a = []

for i in range(1, n+1):

a.append(i)

def bubble_change(a):

global k

n = len(a)

for i in range(k):

if a[i] > a[i+1]:

a[i], a[i+1] = a[i+1], a[i]

else:

k += 1

bubble_change(a)

print(' '.join(map(str, a)))

Answer 2

Для решения этой задачи вам следует сначала найти перестановку из n чисел (от 1 до n) такую, чтобы сортировка пузырьком на этом массиве сделала ровно k обменов. Это можно сделать следующим образом:

1. Сначала создайте массив, содержащий числа от 1 до n в возрастающем порядке.

2. Затем выполните k обменов, чтобы получить требуемое количество обменов. Обмен можно выполнить путем обмена двух соседних элементов.

Вот пример кода на Python, который решает эту задачу:

pythonCopy code
def find_permutation(n, k):
    if k < n - 1 or k > (n - 1) * (n // 2):
        # Проверка на возможность сортировки пузырьком с k обменами
        return []

    # Создаем начальную перестановку
    permutation = list(range(1, n))

    # Выполняем k обменов
    for i in range(n - 1):
        if k <= 0:
            break
        swaps = min(k, n - i - 1)
        for j in range(i, i + swaps + 1)[::-1]:
            permutation[j] = permutation[j - 1]
        k -= swaps

    return permutation

n = 5  # Замените на желаемое значение n
k = 7  # Замените на желаемое значение k

result = find_permutation(n, k)
if result:
    print("Перестановка с {} обменами: {}".format(k, result))
else:
    print("Невозможно создать перестановку с {} обменами для n = {}".format(k, n))

Вы можете заменить n и k на желаемые значения и использовать этот код для нахождения перестановки.