Рубрики

Проблема с монетами Фробениуса

Если даны две монеты номиналом «X» и «Y» соответственно, найдите наибольшую сумму, которую невозможно получить, используя эти две монеты (при условии бесконечного запаса монет), а затем общее количество таких недостижимых сумм, если такой стоимости не существует. «NA».

Примеры :

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.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Одним из важных наблюдений является то, что если GCD X и Y не одно, то все значения, которые могут быть образованы данными двумя монетами, являются кратными GCD. Например, если X = 4 и Y = 6. Тогда все значения кратны 2. Таким образом, все значения, не кратные 2, не могут быть образованы X и Y. Таким образом, существует бесконечно много значений, которые не могут быть образованы 4 и 6, и наш ответ становится «NA».

Эта общая проблема для n монет известна как классическая проблема монет Форбениуса.

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 amount = (X -1) * (Y - 1) /2 
 

Следовательно, теперь мы можем легко ответить на поставленный выше вопрос, выполнив следующие шаги:

  1. Рассчитать GCD X и Y
  2. Если GCD равен 1, то требуемое наибольшее количество составляет (X * Y) — (X + Y), а общее количество составляет (X-1) * (Y-1) / 2
  3. Остальное печать «NA»
  4. Ниже приведена программа, основанная на том же.

    C ++

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

    using namespace std;

      
    // Сервисная функция для поиска gcd

    int gcd(int a, int b)

    {

        int c;

        while (a != 0)

        {

            c = a;

            a = b%a;

            b = c;

        }

        return b;

    }

      
    // Функция для печати желаемого результата

    void forbenius(int X,int Y)

    {

        // Решение не существует

        // если GCD не 1

        if (gcd(X,Y) != 1)

        {

            cout << "NA\n";

            return;

        }

      

        // Остальное применим формулу

        int A = (X*Y)-(X+Y);

        int N = (X-1)*(Y-1)/2;

      

        cout << "Largest Amount = " << A << endl;

        cout << "Total Count = " << N << endl;

    }

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

    int main()

    {

        int X = 2,Y = 5;

        forbenius(X,Y);

      

        X = 5, Y = 10;

        cout << endl;

        forbenius(X,Y);

        return 0;

    }

    Джава

    // Java-программа для поиска самых больших
    // число, которое не может быть сформировано
    // из заданных двух монет

    import java.io.*;

      

    class GFG

    {
    // Сервисная функция для поиска gcd

        static int gcd(int a, int b)

        {

            int c;

            while (a != 0)

            {

                c = a;

                a = b % a;

                b = c;

            }

            return b;

        }

      

        // Функция для печати

        // желаемый вывод

        static void forbenius(int X, 

                              int Y)

        {

            // Решение не существует

            // если GCD не 1

            if (gcd(X, Y) != 1)

            {

                System.out.println( "NA");

                return;

            }

          

            // Остальное применим формулу

            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 );

        }

          

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

        public static void main(String[] args)

        {

            int X = 2,Y = 5;

            forbenius(X, Y);

            X = 5;

            Y = 10;

            System.out.println();

            forbenius(X, Y);

              

        }

    }

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

    python3

    # Python3 программа для поиска самых больших
    # число, которое не может быть сформировано
    # из заданных двух монет

      
    # Сервисная функция для поиска gcd

    def gcd(a, b):

        while (a != 0):

            c = a;

            a = b % a;

            b = c;

          

        return b;

      
    # Функция для печати желаемого выхода

    def forbenius(X, Y):

      

        # Решение не существует

        # если GCD не 1

        if (gcd(X, Y) != 1):

            print("NA");

            return;

      

        # Остальное применить формулу

        A = (X * Y) - (X + Y);

        N = (X - 1) * (Y - 1) // 2;

      

        print("Largest Amount =", A);

        print("Total Count =", N);

      
    Код водителя

    X = 2

    Y = 5;

    forbenius(X, Y);

      

    X = 5

    Y = 10;

    print("");

    forbenius(X, Y);

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

    C #

    // C # программа для поиска самых больших
    // число, которое не может быть сформировано
    // из заданных двух монет

    using System;

      

    class GFG

    {
    // Сервисная функция для поиска gcd

        static int gcd(int a, int b)

        {

            int c;

            while (a != 0)

            {

                c = a;

                a = b%a;

                b = c;

            }

            return b;

        }

      

        // Функция для печати

        // желаемый вывод

        static void forbenius(int X, int Y)

        {

            // Решение не существует

            // если GCD не 1

            if (gcd(X,Y) != 1)

            {

                Console.WriteLine( "NA");

                return;

            }

          

            // Остальное применим формулу

            int A = (X * Y) - (X + Y);

            int N = (X - 1) * (Y - 1) / 2;

          

            Console.WriteLine("Largest Amount = " + A );

            Console.WriteLine("Total Count = " + N );

        }

          

          

          

      

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

        public static void Main()

        {

            int X = 2,Y = 5;

            forbenius(X,Y);

            X = 5;

            Y = 10;

            Console.WriteLine();

            forbenius(X,Y);

          

        }

    }

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

    PHP

    <?php
    // PHP программа, чтобы найти самый большой
    // число, которое не может быть сформировано
    // из заданных двух монет

      
    // Сервисная функция для поиска gcd

    function gcd($a, $b)

    {

        $c;

        while ($a != 0)

        {

            $c = $a;

            $a = $b % $a;

            $b = $c;

        }

          

        return $b;

    }

      
    // Функция для печати желаемого результата

    function forbenius($X, $Y)

    {

        // Решение не существует

        // если GCD не 1

        if (gcd($X, $Y) != 1)

        {

            echo "NA\n";

            return;

        }

      

        // Остальное применим формулу

        $A = ($X * $Y) - ($X + $Y);

        $N = ($X - 1) * ($Y - 1) / 2;

      

        echo "Largest Amount = ", $A, "\n";

        echo "Total Count = ", $N, "\n";

    }

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

      

        $X = 2; $Y = 5;

        forbenius($X, $Y);

      

        $X = 5; $Y = 10;

        echo "\n";

        forbenius($X, $Y);

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


    Выход :

    Largest Amount = 3
    Total Count = 2
    
    NA
    

    Ссылки:
    https://en.wikipedia.org/wiki/Coin_problem

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

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

    Проблема с монетами Фробениуса

    0.00 (0%) 0 votes