Question

(Phyton) Составьте программу сложения двух простых дробей. Результат должен быть несократимой дробью. Используйте подпрограмму вычисления НОД по алгоритму Евклида. Простая дробь задается двумя целыми числами: числителем и знаменателем. На phyton! ​

Answer 1

Відповідь:

PascalABC.NET

function GCD(a, b: integer): integer;// НОД

begin  

while b <> 0 do  

begin    

a := a mod b;    

Swap(a, b)  

end;  

Result := a

end;

procedure RedFrac(var a, b: integer); // сокращение дроби begin  

var sgna := Sign(a); // мы должны учитывать знак!  

var sgnb := Sign(b); // мы должны учитывать знак!  

a := Abs(a);  

b := Abs(b);  

var d := GCD(a, b);  

a := (a div d) * sgna;  

b := (b div d) * sgnb

end;

begin  

var (p1, q1) :=      

ReadInteger2('Дробь 1. Введите числитель и знаменатель:');  

var (p2, q2) :=      

ReadInteger2('Дробь 2. Введите числитель и знаменатель:');  

var p3 := p1 * q1 + p2 * q2;  

var q3 := q1 * q2;  

RedFrac(p3, q3);  

Println(p3, '/', q3)

end.

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

=============================================

Алгоритм нахождения НОД делением

Большее число делим на меньшее.

Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

Если есть остаток, то большее число заменяем на остаток от деления.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30 / 18 = 1 (остаток 12)

18 / 12 = 1 (остаток 6)

12 / 6 = 2 (остаток 0)

Конец: НОД – это делитель 6.

НОД (30, 18) = 6

a = 50

b = 130

 

while a != 0 and b != 0:

   if a > b:

       a = a % b

   else:

       b = b % a

 

print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Алгоритм нахождения НОД вычитанием

Из большего числа вычитаем меньшее.

Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30 - 18 = 12

18 - 12 = 6

12 - 6 = 6

6 - 6 = 0

Конец: НОД – это уменьшаемое или вычитаемое.

НОД (30, 18) = 6

a = 50

b = 130

 

while a != b:

   if a > b:

       a = a - b

   else:

       b = b - a

 

print(a)

Функция вычисления НОД

def gcd(a, b):

   while a != b:

       if a > b:

           a = a - b

       else:

           b = b - a        

   print(a)

Блок-схема алгоритма Евклида

Примечание. В модуле math языка программирования Python есть функция gcd(), вычисляющая наибольший общий делитель двух чисел.

>>> import math

>>> math.gcd(30, 18)

6

Answer 2

Вот Python-программа для сложения двух простых дробей и получения несократимой дроби, используя алгоритм Евклида для вычисления НОД:

pythonCopy code
# Функция для вычисления НОД (наибольшего общего делителя) по алгоритму Евклида
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Функция для сложения двух простых дробей
def add_fractions(num1, den1, num2, den2):
    # Находим общий знаменатель
    common_denominator = den1 * den2
    
    # Вычисляем числитель для новой дроби
    new_numerator = (num1 * den2) + (num2 * den1)
    
    # Находим НОД числителя и знаменателя новой дроби
    greatest_common_divisor = gcd(new_numerator, common_denominator)
    
    # Упрощаем дробь, деля числитель и знаменатель на НОД
    simplified_numerator = new_numerator // greatest_common_divisor
    simplified_denominator = common_denominator // greatest_common_divisor
    
    return simplified_numerator, simplified_denominator

# Ввод числителей и знаменателей двух дробей
numerator1 = int(input("Введите числитель первой дроби: "))
denominator1 = int(input("Введите знаменатель первой дроби: "))
numerator2 = int(input("Введите числитель второй дроби: "))
denominator2 = int(input("Введите знаменатель второй дроби: "))

# Вызываем функцию для сложения дробей
result_numerator, result_denominator = add_fractions(numerator1, denominator1, numerator2, denominator2)

# Вывод результата
print(f"Результат сложения: {result_numerator}/{result_denominator}")

Эта программа сначала находит общий знаменатель для двух дробей, затем складывает числители и находит НОД числителя и знаменателя новой дроби, чтобы упростить её до несократимой формы.