Рубрики

Преобразовать число m в n, используя минимальное количество заданных операций

Преобразуйте число m в n с минимальными операциями. Допустимые операции:

  1. Умножьте на 2, т.е. сделайте m = 2 * m
  2. Вычтите 1, т.е. сделайте m = m — 1

Выведите -1, если конвертировать невозможно.

Примеры :

Input : m = 3, n = 11
Output : 3
1st operation: *2 = 3*2 = 6
2nd operation: *2 = 6*2 = 12
3rd operation: -1 = 12-1 = 11

Input : m = 15, n = 20
Output : 6
1st operation: -1 '5' times = 15 + (-1*5) = 10
2nd operation: *2 = 10*2 = 20

Input : m = 0, n = 8
Output : -1
Using the given set of operations 'm' 
cannot be converted to 'n'

Input : m = 12, n = 8
Output : 4

Идея основана на следующих фактах.
1) Если m меньше 0 и n больше 0, то это невозможно.
2) Если m больше n, тогда мы можем достичь n, используя только вычитания.
3) В противном случае (m меньше n), мы должны выполнить m * 2 операций. Следующие два случая возникают.
…… а) Если n нечетно, мы должны сделать операцию -1, чтобы достичь его.
…… б) Если n четное, мы должны сделать операцию * 2, чтобы достичь его.

Алгоритм:

int convert(m,n)
    if (m == n) 
    return 0;
    
    // not possible
    if (m <= 0 && n > 0)  
    return -1;

    // m is greater than n
    if (m > n) 
        return m-n;

    // n is odd
    if (n % 2 == 1) 
    // perform '-1' 
    return 1 + convert(m, n+1);
        
    // n is even
    else 
    // perform '*2' 
    return 1 + convert(m, n/2);

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

m = 3, n = 11
                convert(3,11)
                     |       --> n is odd:   operation '-1'
                convert(3,12) 
                     |       --> n is even:  operation '*2' 
                convert(3,6)
                     |       --> n is even:  operation '*2' 
                convert(3,3) 
                     |       --> m == n
                   return 
Therefore, the sequence of operations is '*2', '*2', '-1'.

C ++

// реализация C ++ для преобразования
// число от m до n, использующее минимум
// количество заданных операций
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска минимума
// количество заданных операций
// для преобразования m в n

int convert(int m, int n)

{

    if (m == n)

        return 0;

  

    // единственный способ сделать

    // -1 (м - н) раз

    if (m > n)

        return m - n;

  

    // невозможно

    if (m <= 0 && n > 0)

        return -1;

  

    // n больше, а n нечетно

    if (n % 2 == 1)

  

        // выполнить '-1' на m

        // (или +1 на n)

        return 1 + convert(m, n + 1);

  

    // n четно

    else

        // выполнить '* 2' на m

        // (или n / 2 на n)

        return 1 + convert(m, n / 2);

}

  
// Код драйвера

int main()

{

    int m = 3, n = 11;

    cout << "Minimum number of operations : "

         << convert(m, n);

    return 0;

}

Джава

// Реализация Java для преобразования
// число от m до n, использующее минимум
// количество заданных операций

  

class ConvertNum 

{

    // функция для поиска минимума

    // количество заданных операций

    // для преобразования m в n

    static int convert(int m, int n)

    {

        if (m == n)

            return 0;

      

        // единственный способ сделать

        // -1 (м - н) раз

        if (m > n)

            return m - n;

      

        // невозможно

        if (m <= 0 && n > 0)

            return -1;

      

        // n больше, а n нечетно

        if (n % 2 == 1)

      

            // выполнить '-1' на m

            // (или +1 на n)

            return 1 + convert(m, n + 1);

      

        // n четно

        else

            // выполнить '* 2' на m

            // (или n / 2 на n)

            return 1 + convert(m, n / 2);

    }

      

    // Код драйвера

    public static void main (String[] args) 

    {

        int m = 3, n = 11;

        System.out.println("Minimum number of "

                                "operations : "

                                  convert(m, n));

    }

}

python3

# Реализация Python для преобразования
# число от m до n, используя минимум
# количество заданных операций

  
# Функция поиска минимума
# количество заданных операций
# для преобразования m в n

def conver(m, n):

  

    if(m == n):

        return 0

  

    # единственный способ сделать

    # -1 (м - н): раз

    if(m > n):

        return m - n

  

    # невозможно

    if(m <= 0 and n > 0):

        return -1

  

    # n больше, а n нечетно

    if(n % 2 == 1):

  

        # выполнить '-1' на м

        # (или +1 на n):

        return 1 + conver(m, n + 1)

  

    # n четно

    else:

          

        # выполнить '* 2' на м

        # (или n / 2 на n):

        return 1 + conver(m, n / 2)

  
# Код драйвера

m = 3

n = 11

print("Minimum number of operations :",

                          conver(m, n))

  
# Этот код предоставлен
# Sanjit_Prasad

C #

// C # реализация для преобразования
// число от m до n, использующее минимум
// количество заданных операций

using System;

  

class GFG

{

    // функция для поиска минимума

    // количество заданных операций

    // для преобразования m в n

    static int convert(int m, int n)

    {

        if (m == n)

            return 0;

      

        // единственный способ сделать

        // -1 (м - н) раз

        if (m > n)

            return m - n;

      

        // невозможно

        if (m <= 0 && n > 0)

            return -1;

      

        // n больше, а n нечетно

        if (n % 2 == 1)

      

            // выполнить '-1' на m

            // (или +1 на n)

            return 1 + convert(m, n + 1);

      

        // n четно

        else

            // выполнить '* 2' на m

            // (или n / 2 на n)

            return 1 + convert(m, n / 2);

    }

      

    // Код драйвера

    public static void Main () 

    {

        int m = 3, n = 11;

        Console.Write("Minimum number of "

                           "operations : "

                             convert(m, n));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// Реализация PHP для преобразования
// число от m до n, использующее минимум
// количество заданных операций

  
// Функция для поиска минимума
// количество заданных операций
// для преобразования m в n

function convert($m, $n)

{

    if ($m == $n)

        return 0;

  

    // единственный способ сделать

    // -1 (м - н) раз

    if ($m > $n)

        return $m - $n;

  

    // невозможно

    if ($m <= 0 && $n > 0)

        return -1;

  

    // n больше, а n нечетно

    if ($n % 2 == 1)

  

        // выполнить '-1' на m

        // (или +1 на n)

        return 1 + convert($m, $n + 1);

  

    // n четно

    else

        // выполнить '* 2' на m

        // (или n / 2 на n)

        return 1 + convert($m, $n / 2);

}

  
// Код драйвера
{

    $m = 3; $n = 11;

    echo "Minimum number of "

              "operations : "

              convert($m, $n);

    return 0;

}     

  
// Этот код добавлен
// нитин митталь.
?>


Выход :

Minimum number of operations : 3

Ссылки :
http://tech.queryhome.com/112705/convert-number-with-minimum-operations-operations-allowed

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Преобразовать число m в n, используя минимальное количество заданных операций

0.00 (0%) 0 votes