Програма за добавяне на две фракции
Опитайте го на GFG практика 
Изход
Дадени два цяло число масива a [] и B [] съдържащи две цели числа, всеки от които представлява числителят и знаменателя съответно на фракция. Задачата е да се намери сумата от двете фракции и да върне числителя и знаменателя на резултата.
Примери:
Вход : a = [1 2] b = [3 2]
Изход : [2 1]
Обяснение: 1/2 + 3/2 = 2/1Вход : a = [1 3] b = [3 9]
Изход : [2 3]
Обяснение: 1/3 + 3/9 = 2/3Вход : a = [1 5] b = [3 15]
Изход : [2 5]
Обяснение: 1/5 + 3/15 = 2/5
Алгоритъм за добавяне на две фракции
- Намерете общ знаменател, като намерите LCM (Най -малко често срещани) от двамата знаменатели.
- Променете фракции да имате един и същ знаменател и да добавите и двата термина.
- Намалете крайната фракция, получена в неговата по -проста форма, като разделите както числителя, така и от знаменателя на най -големия им общ фактор.
#include using namespace std ; // Function to find gcd of a and b int gcd ( int n1 int n2 ) { if ( n1 == 0 ) return n2 ; return gcd ( n2 % n1 n1 ); } //Function to add two fractions vector < int > addFraction ( vector < int > a vector < int > b ) { vector < int > ans ; // Finding gcd of den1 and den2 int den = gcd ( a [ 1 ] b [ 1 ]); // Denominator of final fraction obtained // finding LCM of den1 and den2 // LCM * GCD = a * b den = ( a [ 1 ] * b [ 1 ]) / den ; // Changing the fractions to have same denominator // Numerator of the final fraction obtained int num = ( a [ 0 ]) * ( den / a [ 1 ]) + ( b [ 0 ]) * ( den / b [ 1 ]); // finding the common factor of numerator and denominator int common_factor = gcd ( num den ); // Converting the result into simpler // fraction by dividing them with common factor den = den / common_factor ; num = num / common_factor ; ans . push_back ( num ); ans . push_back ( den ); return ans ; } int main () { vector < int > a = { 1 2 }; vector < int > b = { 3 2 }; vector < int > ans = addFraction ( a b ); cout < < ans [ 0 ] < < ' ' < < ans [ 1 ]; return 0 ; }
C #include // Function to find gcd of a and b int gcd ( int n1 int n2 ) { if ( n1 == 0 ) return n2 ; return gcd ( n2 % n1 n1 ); } // Function to add two fractions void addFraction ( int a [] int b [] int result []) { // Finding gcd of den1 and den2 int den = gcd ( a [ 1 ] b [ 1 ]); // Denominator of final fraction obtained // finding LCM of den1 and den2 // LCM * GCD = a * b den = ( a [ 1 ] * b [ 1 ]) / den ; // Changing the fractions to have same denominator // Numerator of the final fraction obtained int num = ( a [ 0 ]) * ( den / a [ 1 ]) + ( b [ 0 ]) * ( den / b [ 1 ]); // finding the common factor of numerator and denominator int common_factor = gcd ( num den ); // Converting the result into simpler // fraction by dividing them with common factor den = den / common_factor ; num = num / common_factor ; result [ 0 ] = num ; result [ 1 ] = den ; } int main () { int a [] = { 1 2 };; int b [] = { 3 2 };; int ans [ 2 ]; addFraction ( a b ans ); printf ( '%d %d' ans [ 0 ] ans [ 1 ]); return 0 ; }
Java import java.util.ArrayList ; import java.util.List ; public class Main { // Function to find gcd of a and b public static int gcd ( int n1 int n2 ) { if ( n1 == 0 ) return n2 ; return gcd ( n2 % n1 n1 ); } // Function to add two fractions public static List < Integer > addFraction ( List < Integer > a List < Integer > b ) { List < Integer > ans = new ArrayList <> (); // Finding gcd of den1 and den2 int den = gcd ( a . get ( 1 ) b . get ( 1 )); // Denominator of final fraction obtained // finding LCM of den1 and den2 // LCM * GCD = a * b den = ( a . get ( 1 ) * b . get ( 1 )) / den ; // Changing the fractions to have same denominator // Numerator of the final fraction obtained int num = ( a . get ( 0 )) * ( den / a . get ( 1 )) + ( b . get ( 0 )) * ( den / b . get ( 1 )); // finding the common factor of numerator and denominator int common_factor = gcd ( num den ); // Converting the result into simpler // fraction by dividing them with common factor den = den / common_factor ; num = num / common_factor ; ans . add ( num ); ans . add ( den ); return ans ; } public static void main ( String [] args ) { List < Integer > a = new ArrayList <> (); a . add ( 1 ); a . add ( 2 ); List < Integer > b = new ArrayList <> (); b . add ( 3 ); b . add ( 2 ); List < Integer > ans = addFraction ( a b ); System . out . println ( ans . get ( 0 ) + ' ' + ans . get ( 1 )); } }
Python from math import gcd # Function to add two fractions def addFraction ( a b ): # Finding gcd of den1 and den2 den = gcd ( a [ 1 ] b [ 1 ]) # Denominator of final fraction obtained # finding LCM of den1 and den2 # LCM * GCD = a * b den = ( a [ 1 ] * b [ 1 ]) // den # Changing the fractions to have same denominator # Numerator of the final fraction obtained num = ( a [ 0 ]) * ( den // a [ 1 ]) + ( b [ 0 ]) * ( den // b [ 1 ]) # finding the common factor of numerator and denominator common_factor = gcd ( num den ) # Converting the result into simpler # fraction by dividing them with common factor den //= common_factor num //= common_factor return [ num den ] if __name__ == '__main__' : a = [ 1 2 ] b = [ 3 2 ] ans = addFraction ( a b ) print ( f ' { ans [ 0 ] } { ans [ 1 ] } ' )
C# // Function to find gcd of a and b int gcd ( int n1 int n2 ) { if ( n1 == 0 ) return n2 ; return gcd ( n2 % n1 n1 ); } // Function to add two fractions List < int > addFraction ( List < int > a List < int > b ) { List < int > ans = new List < int > (); // Finding gcd of den1 and den2 int den = gcd ( a [ 1 ] b [ 1 ]); // Denominator of final fraction obtained // finding LCM of den1 and den2 // LCM * GCD = a * b den = ( a [ 1 ] * b [ 1 ]) / den ; // Changing the fractions to have same denominator // Numerator of the final fraction obtained int num = ( a [ 0 ]) * ( den / a [ 1 ]) + ( b [ 0 ]) * ( den / b [ 1 ]); // finding the common factor of numerator and denominator int common_factor = gcd ( num den ); // Converting the result into simpler // fraction by dividing them with common factor den = den / common_factor ; num = num / common_factor ; ans . Add ( num ); ans . Add ( den ); return ans ; } public static void Main () { List < int > a = new List < int > { 1 2 }; List < int > b = new List < int > { 3 2 }; List < int > ans = addFraction ( a b ); Console . WriteLine ( ans [ 0 ] + ' ' + ans [ 1 ]); }
JavaScript // Function to find gcd of a and b function gcd ( n1 n2 ) { if ( n1 === 0 ) return n2 ; return gcd ( n2 % n1 n1 ); } // Function to add two fractions function addFraction ( a b ) { let ans = []; // Finding gcd of den1 and den2 let den = gcd ( a [ 1 ] b [ 1 ]); // Denominator of final fraction obtained // finding LCM of den1 and den2 // LCM * GCD = a * b den = ( a [ 1 ] * b [ 1 ]) / den ; // Changing the fractions to have same denominator // Numerator of the final fraction obtained let num = ( a [ 0 ]) * ( den / a [ 1 ]) + ( b [ 0 ]) * ( den / b [ 1 ]); // finding the common factor of numerator and denominator let common_factor = gcd ( num den ); // Converting the result into simpler // fraction by dividing them with common factor den = den / common_factor ; num = num / common_factor ; ans . push ( num ); ans . push ( den ); return ans ; } let a = [ 1 2 ]; let b = [ 3 2 ]; let ans = addFraction ( a b ); console . log ( ans [ 0 ] + ' ' + ans [ 1 ]);
Изход
2 1
Сложност на времето : O (log (min (a b))
Спомагателно пространство : O (1)
