Минимальное количество шагов для уменьшения числа до 1

Ответ 1

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

Если вы посмотрите на двоичное представление n и его наименее значимые биты, вы можете сделать некоторые выводы о том, какая операция приводит к решению. Короче говоря:

• если младший бит равен нулю, то разделите на 2
• если n равно 3 или 2 младших значащих бита равны 01, то вычтите
• Во всех остальных случаях: доп.

Доказательство

Если младший значащий бит равен нулю, следующей операцией должно быть деление на 2. Вместо этого мы можем попробовать 2 сложения и затем деление, но тогда тот же самый результат может быть достигнут в два этапа: разделить и сложить. Аналогично с 2 вычитаниями. И, конечно же, мы можем игнорировать бесполезное последующее добавление & вычитать шаги (или наоборот). Поэтому, если последний бит равен 0, деление - это путь.

Тогда остальные 3-битные комбинации будут похожи на **1. Их четыре. Позвольте написать a011, чтобы обозначить число, которое заканчивается битами 011 и имеет набор префиксных битов, которые будут представлять значение a:

• a001: добавление одного даст a010, после чего должно произойти деление: a01: сделано 2 шага. Мы бы не хотели вычитать один сейчас, потому что это привело бы к a00, к которому мы могли бы прийти в двух шагах от начала (вычесть 1 и разделить). Итак, снова мы добавляем и делим, чтобы получить a1, и по той же причине мы повторяем это снова, давая: a+1. Это заняло 6 шагов, но приводит к числу, которое можно получить за 5 шагов (вычтите 1, разделите 3 раза, добавьте 1), поэтому ясно, что мы не должны выполнять сложение. Вычитание всегда лучше.

• a111: сложение равно или лучше, чем вычитание. В 4 шага мы получаем a+1. Вычитание и деление дадут a11. Добавление сейчас будет неэффективным по сравнению с исходным путем сложения, поэтому мы повторим это вычитание/деление дважды и получим a за 6 шагов. Если a заканчивается на 0, то мы могли бы сделать это за 5 шагов (сложить, разделить три раза, вычесть), если a заканчивается на 1, то даже на 4. Так что сложение всегда лучше.

• a101: вычитание и двойное деление приводят к a1 в 3 этапа. Добавление и разделение приводит к a11. Теперь вычитать и делить было бы неэффективно по сравнению с путем вычитания, поэтому мы добавляем и делим дважды, чтобы получить a+1 за 5 шагов. Но с помощью пути вычитания мы могли бы достичь этого за 4 шага. Так что вычитание всегда лучше.

• a011: сложение и двойное деление приводит к a1. Чтобы получить a потребуется еще 2 шага (5), чтобы получить a+1: еще один (6). Вычитание, деление, вычитание, двойное деление приводит к a (5), для получения a+1 потребуется еще один шаг (6). Таким образом, сложение по крайней мере так же хорошо, как вычитание. Однако есть один случай, который нельзя упускать: если a равно 0, то путь вычитания достигает решения на полпути, за 2 шага, а путь сложения - за 3 шага. Таким образом, сложение всегда приводит к решению, за исключением случаев, когда n равно 3: тогда следует выбрать вычитание.

Таким образом, для нечетных чисел второй-последний бит определяет следующий шаг (кроме 3).

Код Python

Это приводит к следующему алгоритму (Python), который требует одну итерацию для каждого шага и, следовательно, должен иметь сложность O (logn):

def stepCount(n):
    count = 0
    while n > 1:
        if n % 2 == 0:             # bitmask: *0
            n = n // 2
        elif n == 3 or n % 4 == 1: # bitmask: 01
            n = n - 1
        else:                      # bitmask: 11
            n = n + 1
        count += 1
    return count

Посмотрите, как он работает на repl.it.

Фрагмент JavaScript

Вот версия, в которой вы можете ввести значение для n и позволить фрагменту произвести количество шагов:

function stepCount(n) {
    var count = 0
    while (n > 1) {
        if (n % 2 == 0)                // bitmask: *0
            n = n / 2
        else if (n == 3 || n % 4 == 1) // bitmask: 01
            n = n - 1
        else                           // bitmask: 11
            n = n + 1
        count += 1
    }
    return count
}

// I/O
var input = document.getElementById('input')
var output = document.getElementById('output')
var calc = document.getElementById('calc')

calc.onclick = function () {
  var n = +input.value
  if (n > 9007199254740991) { // 2^53-1
    alert('Number too large for JavaScript')
  } else {
    var res = stepCount(n)
    output.textContent = res
  }
}

<input id="input" value="123549811245">
<button id="calc">Caluclate steps</button><br>
Result: <span id="output"></span>

Ответ 2

Мне нравится идея, вызванная жадным взглядом (для случая нечетных чисел), является ли n + 1 или n - 1 более перспективным, но думаю, что решение о том, что выглядит более перспективным, можно сделать немного лучше, чем смотреть на общее количество установленных бит.

Для числа x,

bin(x)[:: -1].index('1')

указывает количество наименьших значащих 0s до первого 1. Идея состоит в том, чтобы определить, является ли это число выше для n + 1 или n - 1, и выберите более высокий из двух (много последовательных наименее- Значительные 0s указывают на большее количество сокращений в два раза).

Это приводит к

def min_steps_back(n):
    count_to_1 = lambda x: bin(x)[:: -1].index('1')

    if n in [0, 1]:
        return 1 - n

    if n % 2 == 0:
        return 1 + min_steps_back(n / 2)

    return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Чтобы сравнить эти два, я побежал

num = 10000
ms, msb = 0., 0.
for i in range(1000):
    n =  random.randint(1, 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999)

    ms += min_steps(n)
    msb += min_steps_back(n)

print ms / num, msb / num

Какие выходы

57.4797 56.5844

показывает, что в среднем это делает меньше операций (хотя и не так).

Ответ 3

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

Логика. Мы должны помнить, что число, кратное 2, всегда будет иметь меньше битов, чем те, которые не делятся на 2.

Чтобы решить вашу проблему, я использую java-код. Я пробовал его с несколькими номерами, и он отлично работает, если он не добавляет комментарий или не редактирует ответ

while(n!=1)
    {
        steps++;
        if(n%2 == 0)
        {
            n=n/2;

        }
        else
        {
            if(Integer.bitCount(n-1) > Integer.bitCount(n+1))
            {
                n += 1;
            }
            else
            {
                n -=1;
            }
        }
    }

    System.out.println(steps);

Код написан в очень простой форме, чтобы каждый мог понять его. Здесь n введено число и шаги - шаги, необходимые для достижения 1

Ответ 4

Решение, предлагаемое Ами Тавой, работает, если рассматривать 3 (добавление к 4 будет производить 0b100 и count_to_1 равно 2, что больше, чем вычитание в 2 для 0b10 и count_to_1 равно 1). Вы можете добавить два шага, когда мы опустим n = 3, чтобы завершить решение:

def min_steps_back(n):
count_to_1 = lambda x: bin(x)[:: -1].index('1')

if n in [0, 1]:
    return 1 - n

if n == 3:
    return 2

if n % 2 == 0:
    return 1 + min_steps_back(n / 2)

return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Извините, я знаю, сделаю лучший комментарий, но я только начал.

Ответ 5

В итоге:

• Если n четное, разделите на 2
• Если n равно 3 или его младшие значащие биты равны 01, вычтите.
• Если n младших битов равно 11, добавьте.

Повторите эти операции для n, пока не достигнете 1, считая количество выполненных операций. Это гарантированно даст правильный ответ.

В качестве альтернативы доказательству из @trincot, здесь приведено меньше случаев, и, как мы надеемся, более ясное:

Доказательство:

Случай 1: n чётно

Позвольте y быть значением числа после выполнения некоторых операций над ним. Для начала у = п.

1. Предположим, что деление n на 2 не является оптимальным подходом.
2. Затем либо добавить или вычесть четное количество раз
   1. Смешивание сложения и вычитания приведет к ненужным операциям, поэтому выполняется только одна из них.
   2. Необходимо добавить/вычесть четное число, так как остановка на нечетном числе приведет к продолжению сложения или вычитания.
3. Пусть 2k, где k - некоторое целое число, будет количеством выполненных сложений или вычитаний
   1. Ограничьте k при вычитании так, чтобы n - 2k> = 2.
4. После сложения/вычитания y = n + 2k или y = n - 2k.
5. Теперь разделите. После деления y = n/2 + k или y = n/2 - k
6. Выполнено 2к + 1 операций. Но того же результата можно было бы достичь в 1 + k операциях, сначала разделив, а затем сложив или вычтя k раз.
7. Таким образом, предположение, что деление не является оптимальным подходом, было неверным, а деление - оптимальным подходом.

Случай 2: n нечетно

Цель здесь - показать, что при столкновении с нечетным n добавление или вычитание приведет к меньшему количеству операций для достижения заданного состояния. Мы можем использовать тот факт, что деление является оптимальным, когда сталкиваемся с четным числом.

Мы представим n с частичной цепочкой битов, показывающей младшие значащие биты: X1, или X01, и т.д., Где X представляет оставшиеся биты и отличен от нуля. Когда X равен 0, правильные ответы ясны: для 1 все готово; для 2 (0b10) разделить; для 3 (0b11) вычтите и разделите.

Попытка 1: Проверьте, лучше ли сложение или вычитание, с одним битом информации:

1. Начало: X1
   1. добавить: (X + 1) 0, разделить: X + 1 (2 операции)
   2. вычесть: X0, разделить: X (2 операции)

Мы зашли в тупик: если бы Х или Х + 1 были четными, оптимальным было бы деление. Но мы не знаем, четны ли X или X + 1, поэтому мы не можем продолжать.

Попытка 2: Проверьте, лучше ли сложить или вычесть, с помощью двух битов информации:

1. Начало: X01
   1. добавить: X10, разделить: X1
      1. добавить: (X + 1) 0, разделить: X + 1 (4 операции)
      2. вычесть: X0, разделить: X (4 операции)
   2. вычесть: X00, разделить: X0, разделить: X (3 операции)
      1. добавить: X + 1 (возможно, не оптимально) (4 операции)

Вывод: для X01 вычитание приведет к как минимум такому количеству операций, как сложение: 3 и 4 операции против 4 и 4 операций для достижения X и X + 1.

2. Начало: X11
   1. добавить: (X + 1) 00, разделить: (X + 1) 0, разделить: X + 1 (3 операции)
      1. вычесть: X (возможно, не оптимально) (4 операции)
   2. вычесть: X10, разделить: X1
      1. добавить: (X + 1) 0, разделить: X + 1 (4 операции)
      2. вычесть: X0, разделить: X (4 операции)

Вывод: для X11 добавление приведет к вычитанию как минимум такого количества операций, как вычитание: 3 и 4 операции против 4 и 4 операций для достижения X + 1 и X.

Таким образом, если n младших значащих битов равны 01, вычтите. Если n младших битов равны 11, добавьте.

Ответ 6

Я очень плохо разбираюсь в двоичных файлах, поэтому не считая lsb или msb. Как насчет программы ниже -

public class ReduceNto1 {
    public static void main(String[] args) {
        int count1 = count(59);//input number
        System.out.println("total min steps - " + count1);
    }
    static int count(int n){
        System.out.println(n + " > ");
        if(n==1){
            return 0;
        }
        else if(n %2 ==0){

            return 1 + count(n/2);
        }else{
            return 1 + Math.min(count(n-1), count(n+1));
        }
    }
}