Рубрики

Жадный алгоритм для египетской фракции

Каждая положительная дробь может быть представлена как сумма уникальных дробных единиц. Дробь — это дробная единица, если числитель равен 1, а знаменатель — положительное целое число, например, 1/3 — дробная единица. Такое представление называется египетская фракция, поскольку оно использовалось древними египтянами.

Вот несколько примеров:

Egyptian Fraction Representation of 2/3 is 1/2 + 1/6
Egyptian Fraction Representation of 6/14 is 1/3 + 1/11 + 1/231
Egyptian Fraction Representation of 12/13 is 1/2 + 1/3 + 1/12 + 1/156

Мы можем генерировать египетские фракции, используя алгоритм жадности . Для заданного числа вида 'nr / dr', где dr> nr, сначала найдите максимально возможную дробную единицу, а затем повторите для оставшейся части. Например, рассмотрим 6/14, мы сначала находим потолок 14/6, т. Е. 3. Таким образом, первая дробная единица становится 1/3, а затем повторяется для (6/14 — 1/3), т. Е. 4/42.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для печати дроби в египетской форме с использованием Greedy
// Алгоритм
#include <iostream>

using namespace std;

  

void printEgyptian(int nr, int dr)

{

    // Если числитель или знаменатель равен 0

    if (dr == 0 || nr == 0)

        return;

  

    // Если числитель делит знаменатель, то простое деление

    // делает фракцию в 1 / N форме

    if (dr%nr == 0)

    {

        cout << "1/" << dr/nr;

        return;

    }

  

    // Если знаменатель делит числитель, то данное число

    // не дробь

    if (nr%dr == 0)

    {

        cout << nr/dr;

        return;

    }

  

    // Если числитель больше знаменателя

    if (nr > dr)

    {

        cout << nr/dr << " + ";

        printEgyptian(nr%dr, dr);

        return;

    }

  

    // Мы достигаем здесь dr> nr и dr% nr не равен нулю

    // Найти потолок др / нр и напечатать его первым

    // доля

    int n = dr/nr + 1;

    cout << "1/" << n << " + ";

  

    // Повторять для оставшейся части

    printEgyptian(nr*n-dr, dr*n);

 }

  
// Программа для водителя

int main()

{

    int nr = 6, dr = 14;

    cout << "Egyptian Fraction Representation of "

         << nr << "/" << dr << " is\n ";

    printEgyptian(nr, dr);

    return 0;

}

Джава

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

  

class GFG {

  

    static void printEgyptian(int nr, int dr) {

        // Если числитель или

        // знаменатель равен 0

        if (dr == 0 || nr == 0) {

            return;

        }

  

        // Если числитель делит знаменатель,

        // тогда простое деление делает

        // дробь в 1 / n форме

        if (dr % nr == 0) {

            System.out.print("1/" + dr / nr);

            return;

        }

  

        // Если знаменатель делит числитель,

        // тогда данное число не дробно

        if (nr % dr == 0) {

            System.out.print(nr / dr);

            return;

        }

  

        // Если числитель больше знаменателя

        if (nr > dr) {

            System.out.print(nr / dr + " + ");

            printEgyptian(nr % dr, dr);

            return;

        }

  

        // Мы достигаем здесь dr> nr и dr% nr

        // не ноль. Найти потолок

        // др / Н.Р. и напечатать его в качестве первого

        // доля

        int n = dr / nr + 1;

        System.out.print("1/" + n + " + ");

  

        // Повторять для оставшейся части

        printEgyptian(nr * n - dr, dr * n);

    }

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

    public static void main(String[] args) {

        int nr = 6, dr = 14;

        System.out.print("Egyptian Fraction Representation of "

                + nr + "/" + dr + " is\n ");

        printEgyptian(nr, dr);

    }

}

  
/ * Этот код предоставлен Rajput-Ji * /

python3

# Программа Python3 печатать фракцию
# в египетской форме, используя жадный
# Алгоритм

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

import math

  
# определить функцию egyptianFraction
# Которые получают параметр в качестве факса
# числитель и др в качестве знаменателя

def egyptianFraction(nr, dr):

  

    print("The Egyptian Fraction " +

          "Representation of {0}/{1} is".

                format(nr, dr), end="\n")

  

    # пустой список для хранения

    # знаменатель

    ef = []

  

    # пока цикл работает до

    # фракция становится 0, т. е.

    # числитель становится 0

    while nr != 0:

  

        # принимая потолок

        x = math.ceil(dr / nr)

  

        # Хранение значения в списке эф

        ef.append(x)

  

        # обновление новых номеров и др

        nr = x * nr - dr

        dr = dr * x

  

    # печать значений

    for i in range(len(ef)):

        if i != len(ef) - 1:

            print(" 1/{0} +"

                    format(ef[i]), end = " ")

        else:

            print(" 1/{0}" .

                    format(ef[i]), end = " ")

  
# вызов функции

egyptianFraction(6, 14)

  
# Этот код добавлен
# Анубхав Радж Сингх

C #

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

using System;

  

class GFG

{

static void printEgyptian(int nr, int dr)

{

    // Если числитель или

    // знаменатель равен 0

    if (dr == 0 || nr == 0)

        return;

  

    // Если числитель делит знаменатель,

    // тогда простое деление делает

    // дробь в 1 / n форме

    if (dr % nr == 0)

    {

        Console.Write("1/" + dr / nr);

        return;

    }

  

    // Если знаменатель делит числитель,

    // тогда данное число не дробно

    if (nr % dr == 0)

    {

        Console.Write(nr / dr);

        return;

    }

  

    // Если числитель больше знаменателя

    if (nr > dr)

    {

        Console.Write(nr / dr + " + ");

        printEgyptian(nr % dr, dr);

        return;

    }

  

    // Мы достигаем здесь dr> nr и dr% nr

    // не ноль. Найти потолок

    // др / Н.Р. и напечатать его в качестве первого

    // доля

    int n = dr / nr + 1;

    Console.Write("1/" + n + " + ");

  

    // Повторять для оставшейся части

    printEgyptian(nr * n - dr, dr * n);

}

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

public static void Main()

{

    int nr = 6, dr = 14;

    Console.Write( "Egyptian Fraction Representation of " +

                                 nr + "/" + dr + " is\n ");

    printEgyptian(nr, dr);

}
}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

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

  

function printEgyptian($nr, $dr)

{

    // Если числитель или

    // знаменатель равен 0

    if ($dr == 0 || $nr == 0)

        return;

  

    // Если числитель делит знаменатель,

    // тогда простое деление делает

    // дробь в 1 / n форме

    if ($dr % $nr == 0)

    {

        echo "1/", (int)$dr / $nr;

        return;

    }

  

    // Если знаменатель делит числитель,

    // тогда данное число не дробно

    if ($nr%$dr == 0)

    {

        echo (int)($nr / $dr);

        return;

    }

  

    // Если числитель больше знаменателя

    if ($nr > $dr)

    {

        echo (int)($nr/$dr), " + ";

        printEgyptian($nr % $dr, $dr);

        return;

    }

  

    // Мы достигаем здесь dr> nr и dr% nr

    // ненулевой Найти потолок др / нр и

    // распечатать как первую дробь

    $n = (int)($dr / $nr ) + 1;

    echo "1/" , $n , " + ";

  

    // Повторять для оставшейся части

    printEgyptian($nr * $n - $dr, $dr * $n);

}

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

$nr = 6;

$dr = 14;

echo "Egyptian Fraction Representation of ",

                    $nr, "/", $dr, " is\n ";

printEgyptian($nr, $dr);

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


Выход:

Egyptian Fraction Representation of 6/14 is
 1/3 + 1/11 + 1/231 

Алгоритм Жадности работает, потому что дробь всегда сводится к форме, где знаменатель больше, чем числитель, а числитель не делит знаменатель. Для таких сокращенных форм выделенный рекурсивный вызов выполняется для уменьшенного числителя. Таким образом, рекурсивные вызовы продолжают уменьшать числитель, пока не достигнут 1.

Ссылки:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

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

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

Жадный алгоритм для египетской фракции

0.00 (0%) 0 votes