Блог

Главная - Вопросы по программированию - Максимальное число после K обменов с использованием рекурсии

Максимальное число после K обменов с использованием рекурсии

#python #recursion

#python #рекурсия

Вопрос:

Я должен сделать функцию maximize(x, k), в которой x — целое число, а k — максимальное количество обменов, и вывести максимальное число после выполнения максимальных k обменов. Также должны использоваться две функции swap(s, i, j) и sort(sort), которые, как следует из названия, меняют местами символы строки в соответствии с индексом и сортируют от самого высокого к самому низкому соответственно. Я пытался, но не могу этого сделать, не имея другой переменной i в функции maximize. Можно ли каким-либо образом это сделать без переменной i в функции maximize, просто передав две переменные x и k. Вот мой код:

 def swap(s,i,j):
    return s[0:i] s[j] s[i 1:j] s[i] s[j 1:len(s)]

def sort(s):
    return "".join((sorted(s)[::-1]))

def maximize(x,k,i):
    if k==0 or i==len(str(x)):
        return x

    s=str(x)
    t=sort(s)

    if t[i]>s[i]:
        j=s.find(t[i],i,len(s))
        s=swap(s,i,j)
        return maximize(int(s),k-1,i 1)
    else:
        return maximize(int(s),k,i 1)

print(maximize(223953,2,0))

Комментарии:

1. max() это встроенная функция, которую вы, вероятно, собираетесь использовать

2. Извини, я тебя не понял. Как я должен использовать эту max() функцию? Не могли бы вы объяснить немного больше, или было бы действительно полезно, если бы вы могли написать код, используя функцию max() .

3. Я, конечно, что-то неправильно понял, но, как только строка отсортирована от наивысшей к наименьшей, найдено максимальное значение, так какова цель функции подкачки? (в вашем примере сортировка выдает 953322, но после некоторых обменов ваша функция возвращает 953223, что меньше …)

4. Это потому, что это должно быть сделано с максимальным количеством k свопов, которое в данном случае равно 2. Я надеюсь, вы это понимаете. Таким образом, 2 свопа будут заменять первые 2 на 9, а затем вторые 2 на 5.

Ответ №1:

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

 def swap(s,i,j):
    return s[0:i] s[j] s[i 1:j] s[i] s[j 1:len(s)]

def sort(s):
    return "".join((sorted(s)[::-1]))

def maximize(x,k):
    if not k or x<10: return x   # stop when no more swaps or no more digits
    s = str(x)
    if s == sort(s): return x    # stop if already at max value
    i = s.index(max(s))          # find position of highest digit
    if i>0: s = swap(s,0,i)      # swap if not already first
    suffix = maximize(int(s[1:]),k - (i>0)) # recurse for rest of digits (don't reduce swap count if no swap done)
    return int(s[0] str(suffix)) # combine biggest digit with maximized remainder

print(maximize(223953,2)) # 953223