problema de la moneda de frobenius

Posted on by Rudeus Greyrat

Dadas dos monedas de denominaciones «X» e «Y» respectivamente, encuentre la cantidad más grande que no se puede obtener usando estas dos monedas (suponiendo que haya una cantidad infinita de monedas) seguido del número total de dichas cantidades no obtenibles, si no existe tal valor imprimir «N / A».

Ejemplos:

Input : X=2, Y=5  
Output: Largest amount = 3
        Total count  = 2
We cannot represent 1 and 3 from infinite supply
of given two coins. The largest among these 2 is 3.
We can represent all other amounts for example 13
can be represented 2*4 + 5.

Input : X=5, Y=10
Output: NA
There are infinite number of amounts that cannot
be represented by these two coins.

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Una observación importante es que, si el MCD de X e Y no es uno, entonces todos los valores que se pueden formar con dos monedas dadas son múltiplos del MCD. Por ejemplo, si X = 4 e Y = 6. Entonces todos los valores son múltiplos de 2. Entonces, todos los valores que no son múltiplos de 2, no pueden estar formados por X e Y. Por lo tanto, existen infinitos valores que no pueden estar formados por 4 y 6, y nuestra respuesta se convierte en «NA».

Este problema general para n monedas se conoce como problema clásico de monedas de Forbenius.

When the number of coins is two, there is 
explicit formula if GCD is not 1. The formula
is:
  Largest amount A = (X * Y) - (X + Y)
  Total count = (X -1) * (Y - 1) /2

Por lo tanto, ahora podemos responder fácilmente a la pregunta anterior siguiendo los pasos a continuación:

  1. Calcular MCD de X e Y
  2. Si GCD es 1, entonces la cantidad más grande requerida es (X*Y)-(X+Y) y el recuento total es (X-1)*(Y-1)/2
  3. De lo contrario, escriba «NA»

    4. A continuación se muestra el programa basado en el mismo.

    C++

    // C++ program to find the largest number that
    // cannot be formed from given two coins
    #include <bits/stdc++.h>
    using namespace std;
      
    // Utility function to find gcd
    int gcd(int a, int b)
    {
        int c;
        while (a != 0)
        {
            c = a;
            a = b%a;
            b = c;
        }
        return b;
    }
      
    // Function to print the desired output
    void forbenius(int X,int Y)
    {
        // Solution doesn't exist 
        // if GCD is not 1
        if (gcd(X,Y) != 1)
        {
            cout << "NA\n";
            return;
        }
      
        // Else apply the formula
        int A = (X*Y)-(X+Y);
        int N = (X-1)*(Y-1)/2;
      
        cout << "Largest Amount = " << A << endl;
        cout << "Total Count = " << N << endl;
    }
      
    // Driver Code
    int main()
    {
        int X = 2,Y = 5;
        forbenius(X,Y);
      
        X = 5, Y = 10;
        cout << endl;
        forbenius(X,Y);
        return 0;
    }

    Java

    // Java program to find the largest
    // number that cannot be formed 
    // from given two coins
    import java.io.*;
      
    class GFG
    {
    // Utility function to find gcd
        static int gcd(int a, int b)
        {
            int c;
            while (a != 0)
            {
                c = a;
                a = b % a;
                b = c;
            }
            return b;
        }
      
        // Function to print the
        // desired output
        static void forbenius(int X, 
                              int Y)
        {
            // Solution doesn't exist 
            // if GCD is not 1
            if (gcd(X, Y) != 1)
            {
                System.out.println( "NA");
                return;
            }
          
            // Else apply the formula
            int A = (X * Y) - (X + Y);
            int N = (X - 1) * (Y - 1) / 2;
          
            System.out.println("Largest Amount = " + A );
            System.out.println("Total Count = " + N );
        }
          
        // Driver Code
        public static void main(String[] args)
        {
            int X = 2,Y = 5;
            forbenius(X, Y);
            X = 5;
            Y = 10;
            System.out.println();
            forbenius(X, Y);
              
        }
    }
      
    // This code is contributed by Sam007

    Python3

    # Python3 program to find the largest 
    # number that cannot be formed
    # from given two coins
      
    # Utility function to find gcd
    def gcd(a, b):
        while (a != 0):
            c = a;
            a = b % a;
            b = c;
          
        return b;
      
    # Function to print the desired output
    def forbenius(X, Y):
      
        # Solution doesn't exist 
        # if GCD is not 1
        if (gcd(X, Y) != 1):
            print("NA");
            return;
      
        # Else apply the formula
        A = (X * Y) - (X + Y);
        N = (X - 1) * (Y - 1) // 2;
      
        print("Largest Amount =", A);
        print("Total Count =", N);
      
    # Driver Code
    X = 2; 
    Y = 5;
    forbenius(X, Y);
      
    X = 5; 
    Y = 10;
    print("");
    forbenius(X, Y);
      
    # This code is contributed by mits

    C#

    // C# program to find the largest
    //  number that cannot be formed 
    // from given two coins
    using System;
      
    class GFG
    {
    // Utility function to find gcd
        static int gcd(int a, int b)
        {
            int c;
            while (a != 0)
            {
                c = a;
                a = b%a;
                b = c;
            }
            return b;
        }
      
        // Function to print the
        // desired output
        static void forbenius(int X, int Y)
        {
            // Solution doesn't exist 
            // if GCD is not 1
            if (gcd(X,Y) != 1)
            {
                Console.WriteLine( "NA");
                return;
            }
          
            // Else apply the formula
            int A = (X * Y) - (X + Y);
            int N = (X - 1) * (Y - 1) / 2;
          
            Console.WriteLine("Largest Amount = " + A );
            Console.WriteLine("Total Count = " + N );
        }
          
          
          
      
        // Driver Code
        public static void Main()
        {
            int X = 2,Y = 5;
            forbenius(X,Y);
            X = 5;
            Y = 10;
            Console.WriteLine();
            forbenius(X,Y);
          
        }
    }
          
    // This code is contributed by Sam007

    PHP

    <?php
    // php program to find the largest 
    // number that cannot be formed
    // from given two coins
      
    // Utility function to find gcd
    function gcd($a, $b)
    {
        $c;
        while ($a != 0)
        {
            $c = $a;
            $a = $b % $a;
            $b = $c;
        }
          
        return $b;
    }
      
    // Function to print the desired output
    function forbenius($X, $Y)
    {
        // Solution doesn't exist 
        // if GCD is not 1
        if (gcd($X, $Y) != 1)
        {
            echo "NA\n";
            return;
        }
      
        // Else apply the formula
        $A = ($X * $Y) - ($X + $Y);
        $N = ($X - 1) * ($Y - 1) / 2;
      
        echo "Largest Amount = ", $A, "\n";
        echo "Total Count = ", $N, "\n";
    }
      
    // Driver Code
      
        $X = 2; $Y = 5;
        forbenius($X, $Y);
      
        $X = 5; $Y = 10;
        echo "\n";
        forbenius($X, $Y);
      
    // This code is contributed by ajit.
    ?>

    Producción :

    Largest Amount = 3
Total Count = 2

NA

    Referencias:
    https://en.wikipedia.org/wiki/Coin_problem

    Este artículo es una contribución de Ashutosh Kumar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *