Рубрики

Повторное вычитание среди двух чисел

Дана пара положительных чисел х и у. Мы многократно вычитаем меньшее из двух целых чисел из большего, пока одно из целых не станет 0. Задача состоит в том, чтобы посчитать количество шагов до того, как мы остановимся (одно из чисел станет 0).

Примеры :

Input : x = 5, y = 13
Output : 6
Explanation : There are total 6 steps before 
we reach 0:
(5,13) --> (5,8) --> (5,3) --> (2,3) 
--> (2,1) --> (1,1) --> (1,0).

Input : x = 3, y = 5
Output : 4
Explanation : There are 4 steps:
(5,3) --> (2,3) --> (2,1) --> (1,1) --> (1,0)

Input : x = 100, y = 19
Output : 13

Простое решение состоит в том, чтобы фактически следовать за процессом и подсчитать количество шагов.

Лучшее решение — использовать следующие шаги. Пусть у будет меньшее из двух чисел
1) если у делит х, вернуть (х / у)
2) еще возврат ((х / у) + решить (у, х% у))

Иллюстрация:
Если мы начнем с (x, y), а y делит x, то ответ будет (x / y), поскольку мы можем вычесть y из x точно (x / y) раз.

Для другого случая мы возьмем пример, чтобы увидеть, как это работает: (100, 19)

Мы можем вычесть 19 из 100 точно [100/19] = 5 раз, чтобы получить (19, 5).

Мы можем вычесть 5 из 19 точно [19/5] = 3 раза, чтобы получить (5, 4).

Мы можем вычесть 4 из 5 точно [5/4] = 1 раз, чтобы получить (4, 1).

Мы можем вычесть 1 из 4 точно [4/1] = 4 раза, чтобы получить (1, 0)

следовательно, всего 5 + 3 + 1 + 4 = 13 шагов.

Ниже приведена реализация, основанная на представленной выше идее.

C ++

// C ++ программа для подсчета шагов до одного
// из двух чисел становится 0.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество шагов до одного
// числа становятся 0 после повторения
// вычитания.

int countSteps(int x, int y)

{

    // Если у делит х, то просто вернуть

    // х / у.

    if (x%y == 0)

        return x/y;

  

    // Остальное повторяется. Обратите внимание, что эта функция

    // работает, даже если x меньше, чем y, потому что

    // в этом случае первый рекурсивный обмен вызовами

    // роли х и у.

    return x/y + countSteps(y, x%y);

}

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

int main()

{

   int x = 100, y = 19;

   cout << countSteps(x, y);

   return 0;

}

Джава

// Java-программа для подсчета
// шаги до одного из
// два числа становятся 0.

import java.io.*;

  

class GFG 

{

      
// Возвращает количество шагов
// перед одним из чисел
// становиться 0 после повторения
// вычитания.

static int countSteps(int x, 

                      int y)

{

    // Если у делит х, то

    // просто возвращаем х / у.

    if (x % y == 0)

        return x / y;

  

    // Остальное повторяется. Обратите внимание, что это

    // функция работает, даже если х

    // меньше чем у, потому что

    // в этом случае сначала рекурсивно

    // вызываем обмен ролями x и y.

    return x / y + countSteps(y, x % y);

}

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

public static void main (String[] args) 

{

    int x = 100, y = 19;

    System.out.println(countSteps(x, y));

      
}
}

  
// Этот код предоставлен aj_36

python3

# Python3 программа для подсчета шагов до
# одно из двух чисел становится 0.

import math

  
# Возвращает количество шагов до одного из
# числа становятся 0 после повторения
# вычитания.

def countSteps(x, y):

      

    # Если у делит х, то просто

    # возврат х / у.

    if (x % y == 0):

        return math.floor(x / y);

  

    # Остальное повториться. Обратите внимание, что эта функция

    # работает, даже если x меньше y

    # потому что в этом случае сначала рекурсивный

    # вызов меняет роли х и у.

    return math.floor((x / y) + 

           countSteps(y, x % y));

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

x = 100;

y = 19;

print(countSteps(x, y));

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

C #

// C # программа для подсчета
// шаги до одного из
// два числа становятся 0.

using System;

  

class GFG

{
// Возвращает количество шагов
// перед одним из чисел
// становиться 0 после повторения
// вычитания.

static int countSteps(int x, 

                      int y)

{

    // Если у делит х, то

    // просто возвращаем х / у.

    if (x % y == 0)

        return x / y;

  

    // Остальное повторяется. Обратите внимание, что это

    // функция работает, даже если х

    // меньше чем у, потому что

    // в этом случае сначала рекурсивно

    // вызываем обмен ролями x и y.

    return x / y + countSteps(y, x % y);

}

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

static public void Main ()

{

int x = 100, y = 19;

Console.WriteLine(countSteps(x, y));
}
}

  
// Этот код предоставлен m_kit

PHP

<?php
// PHP программа для подсчета
// шаги до одного из
// два числа становятся 0.

  
// Возвращает количество шагов
// перед одним из чисел
// становиться 0 после повторения
// вычитания.

function countSteps($x, $y)

{

    // Если у делит х, то

    // просто возвращаем х / у.

    if ($x % $y == 0)

        return floor(((int)$x / $y));

  

    // Остальное повторяется. Обратите внимание, что это

    // функция работает, даже если х

    // меньше, чем у, потому что в этом

    // регистр первого рекурсивного вызова

    // обменивается ролями x и y.

    return floor(((int)$x / $y) + 

                   countSteps($y, $x % $y));

}

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

$x = 100;

$y = 19;

echo countSteps($x, $y);

  
// Этот код предоставлен aj_36
?>


Выход :

13

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

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

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

Повторное вычитание среди двух чисел

0.00 (0%) 0 votes