1

Только начал изучать 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)))

Пожалуйста, помогите!

2
  • 1
    массив у вас задается командой a.append(i). То есть к списку a в конец добавляется значение i. В питоне нет массивов, есть списки. И дальнейшая работа тут идет со списком. 24 мая 2020 в 15:08
  • 1
    потом, судя по всему конструкция for i in range(1, n+1): a.append(i) и так заполяет все по возрастанию. Вам надо использовать random() 24 мая 2020 в 15:19

3 ответа 3

4

Сортировка пузырьком делает столько обменов, сколько в массиве инверсий (максимум 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]
3
  • Спасибо Вам, я понял Вашу логику, но у меня не получается написать сам код. Помогите, пожалуйста 24 мая 2020 в 20:55
  • 1
    Ну буквально же достаточно реализовать то, что сказано (изменил выход по n=0 вместо k) Добавил код.
    – MBo
    25 мая 2020 в 2:21
  • Спасибо большое! 25 мая 2020 в 8:23
0

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

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)

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

5
  • А Вы внимательно прочитали условие?
    – MBo
    24 мая 2020 в 16:46
  • а что тут не так? вроде внимательно. 24 мая 2020 в 17:03
  • 𝑛 чисел от 1 до 𝑛 без повторений
    – MBo
    24 мая 2020 в 17:05
  • вы правы. сейчас исправлю 24 мая 2020 в 17:05
  • 1
    исправил, добавил условие, исключающее повторения. 24 мая 2020 в 17:25
0
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))
2
  • пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 30 мар в 16:05
  • 1
    И что это такое? Зачем повторять имеющийся ответ?
    – MBo
    30 мар в 16:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.