Programma om twee breuken op te tellen
Probeer het eens op GfG Practice 
Uitvoer
Gegeven twee integer-arrays A[] En B[] met twee gehele getallen die elk respectievelijk de teller en de noemer van een breuk vertegenwoordigen. De taak is om de som van de twee breuken te vinden en de teller en de noemer van het resultaat terug te geven.
Voorbeelden:
Invoer : een = [1 2] b = [3 2]
Uitvoer : [2 1]
Uitleg: 1/2 + 3/2 = 2/1
Invoer : een = [1 3] b = [3 9]
Uitvoer : [2 3]
Uitleg: 1/3 + 3/9 = 2/3Invoer : een = [1 5] b = [3 15]
Uitvoer : [2 5]
Uitleg: 1/5 + 3/15 = 2/5
Algoritme om twee breuken op te tellen
- Vind een gemeenschappelijke noemer door de te vinden LCM (Kleinste Gemene Veelvoud) van de twee noemers.
- Verander de breuken om dezelfde noemer te hebben en beide termen bij elkaar op te tellen.
- Reduceer de verkregen uiteindelijke breuk in zijn eenvoudiger vorm door zowel de teller als de noemer te delen door hun grootste gemeenschappelijke deler.
#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 ]);
Uitvoer
2 1
Tijdcomplexiteit : O(log(min(a b))
Hulpruimte : O(1)
