Задача «Ровно k обменов»

Question

Только начал изучать Python. Пожалуйста, помогите решить задачу:

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

Входные данные: Даны натуральное число ? (?≤100) и целое неотрицательное ?. Гарантируется, что для всех наборов тестовых данных решение существует.

Выходные данные: Выведите искомую перестановку в одной строке. Числа разделяйте пробелами.

Често говоря, я в принципе не понял условие задачи, а именно: откуда взять массив для последующей перестановки его частей и как его заполнить? Тем не менее, я попытался написать код, но тут возникли ещё дополнительные проблемы.

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 1

Сортировка пузырьком делает столько обменов, сколько в массиве инверсий (максимум n*(n-1)/2). Массив ниоткуда брать не нужно, надо сгенерировать такой, содержащий числа от 1 до n, чтобы в нём было нужное количество инверсий.

Предлагаю подход, основанный на следующей логике - если мы имеем сортированный массив из чисел 1 ..n-1, то при добавлении числа n в конец число инверсий останется нулевым, если добавить его перед последним элементом, то возникнет одна инверсия, перед двумя последними - две инверсии и т.д. до первого места - тогда инверсий будет n-1

Итак:
-если количество инверсий k больше или равно n-1, поставить на первое место число nи сделать k = k - (n-1), уменьшить n
иначе поставить его на место n-1-k, остальные места заполнить числами по порядку и на этом закончить.

-продолжить с числом n-1 и так далее, пока n не станет равно 0

def genkinv(n, k):
    a = []
    while n > 0:
        if k > n - 1:
            a.append(n)
            k -= (n - 1)
            n -= 1
        else:
            for i in range(1, n - k):
                a.append(i)
            a.append(n)
            for i in range(n - k, n):
                a.append(i)
            k = 0
            n = 0
    return a

print(genkinv(5, 7))

>>[5, 4, 1, 2, 3]

Answer 2

смотрите как я переделал ваш код

import random
n=int(input("Введите количество элементов в массиве"))
k=int(input("Введите количество шагов прогонки"))
a = []
i=0
while i<n:
    s=random.randint(1,n)
    print(s)
    if s not in a:
        a.append(s)
        i+=1
print(a)
j=1
n = len(a)
while j<k:
    for i in range(n-1):
        if a[i] < a[i+1]:a[i],a[i+1] = a[i+1], a[i]
    j+= 1

print(a)

вводим два числа. заполняем список случайными числами. потом указанное число раз меняем местами все элементы, что попадают под условие. Фишка в том, что по условию вы сами вводите сколько раз вам надо выпролнгить замену местами.

Answer 3

def genkinv(l):
    n, k = l[0], l[1]
    a = []
    while n > 0:
        if k > n - 1:
            a.append(n)
            k -= (n - 1)
            n -= 1
        else:
            for i in range(1, n - k):
                a.append(i)
            a.append(n)
            for i in range(n - k, n):
                a.append(i)
            k, n = 0, 0

    answer = [str(f) for f in a]
    return ' '.join(answer)

l = input().split()
l = [int(i) for i in l]
print(genkinv(l))

БЛОГ НА HUSL

Задача «Ровно k обменов»

Ответы (3 шт):