Minimice las operaciones hasta que a o b supere a N reemplazando a o b con su suma

Dados tres números enteros a, b y N. La tarea es encontrar operaciones de suma mínimas entre a y b, de modo que después de aplicar las operaciones, cualquiera de a o b sea mayor que N. Una operación de suma se define como reemplazar cualquiera de a o b con su suma y manteniendo intacta otra .

Ejemplos :

Entrada : a = 2, b = 3, N = 20
Salida : 4
Explicación : 

• Sumando 2 y 3, 2 + 3 = 5 y reemplazando 2 con 5, ahora a = 5, b = 3
• Nuevamente sume a y b 5 + 3 = 8 reemplace b con 8, ahora a = 5, b = 8
• Nuevamente sume a y b 5 + 8 = 13 reemplace a con 13. ahora a = 13, b = 8
• Nuevamente agregue a y b 13 + 8 = 21 reemplace b con 21, ahora a = 13, b = 21 Aquí, (b>=n) por lo tanto, las operaciones mínimas requeridas son 4

Entrada : a = 2, b = 3, N = 5
Salida : 1
Explicación : Después de reemplazar 2 con 2+3, a se convierte en 5 y b se convierte en 3, por lo tanto, las operaciones mínimas requeridas son 1 

Enfoque : la idea es sumar a y b y almacenar su suma en el mínimo de a y b, cada vez hasta que cualquiera de los números sea mayor que N. La razón detrás de esto es hacer que el elemento mínimo sea más grande cada vez, hace que su suma sea alta. y reduciendo así el número de operaciones requeridas.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the minimum number of operations
// required
int minOperations(int a, int b, int n)
{
    // Store the count of operations
    int count = 0;
    while (1) {
        // If any value is greater than N return count
        if (n <= a or n <= b) {
            return count;
            break;
        }
        else {
            int sum = a + b;
            if (a < b)
                a = sum;
            else
                b = sum;
        }
        count++;
    }
    return count;
}
 
// Driver code
int main()
{
    int p = 2, q = 3, n = 20;
    cout << minOperations(p, q, n) << "\n";
    return 0;
}

// C program for the above approach
#include <stdio.h>
 
// Function to print the minimum number of operations
// required
int minOperations(int a, int b, int n)
{
    // Store the count of operations
    int count = 0;
    while (1) {
        // If any value is greater than N return count
        if (n <= a || n <= b) {
            return count;
            break;
        }
        else {
            int sum = a + b;
            if (a < b)
                a = sum;
            else
                b = sum;
        }
        count++;
    }
    return count;
}
 
// Driver code
int main()
{
    int p = 2, q = 3, n = 20;
    printf("%d\n", minOperations(p, q, n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java program for the above approach
class GFG {
 
    // Function to print the minimum number
    // of operations required
    public static int minOperations(int a, int b, int n) {
 
        // Store the count of operations
        int count = 0;
 
        while (true) {
 
            // If any value is greater than N
            // return count
            if (n <= a || n <= b) {
                return count;
            } else {
                int sum = a + b;
                if (a < b)
                    a = sum;
                else
                    b = sum;
            }
            count++;
        }
    }
 
    // Driver code
    public static void main(String args[]) {
        int p = 2, q = 3, n = 20;
        System.out.println(minOperations(p, q, n));
    }
}
 
// This code is contributed by saurabh_jaiswal.

# python program for the above approach
 
# Function to print the minimum number
# of operations required
def minOperations(a, b, n):
 
    # Store the count of operations
    count = 0
 
    while (1):
 
        # If any value is greater than N
        # return count
        if (n <= a or n <= b):
            return count
            break
 
        else:
            sum = a + b
            if (a < b):
                a = sum
            else:
                b = sum
 
        count += 1
 
    return count
 
# Driver code
if __name__ == "__main__":
 
    p = 2
    q = 3
    n = 20
    print(minOperations(p, q, n))
 
    # This code is contributed by rakeshsahni

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to print the minimum number
        // of operations required
        function minOperations(a, b, n) {
 
            // Store the count of operations
            let count = 0;
 
            while (1) {
 
                // If any value is greater than N
                // return count
                if (n <= a || n <= b) {
                    return count;
                    break;
                }
                else {
                    let sum = a + b;
                    if (a < b)
                        a = sum;
                    else
                        b = sum;
                }
                count++;
            }
            return count;
        }
 
        // Driver code
 
        let p = 2, q = 3, n = 20;
        document.write(minOperations(p, q, n) + "<br>");
 
// This code is contributed by Potta Lokesh
    </script>

// C# program for the above approach
using System;
 
public class GFG {
 
    // Function to print the minimum number
    // of operations required
    public static int minOperations(int a, int b, int n) {
 
        // Store the count of operations
        int count = 0;
 
        while (true) {
 
            // If any value is greater than N
            // return count
            if (n <= a || n <= b) {
                return count;
            } else {
                int sum = a + b;
                if (a < b)
                    a = sum;
                else
                    b = sum;
            }
            count++;
        }
    }
 
    // Driver code
    public static void Main(string []args) {
        int p = 2, q = 3, n = 20;
        Console.WriteLine(minOperations(p, q, n));
    }
}
 
// This code is contributed by AnkThon

4

Complejidad de tiempo : O(min(log(max(a, N), log(max(b, N))) Espacio
auxiliar : O(1)