Dado un número entero N , la tarea es imprimir todas las fracciones propias de modo que el denominador sea menor o igual que N.
Fracciones Propias: Se dice que una fracción es fracción propia si el numerador es menor que el denominador.
Ejemplos:
Entrada: N = 3
Salida: 1/2, 1/3, 2/3Entrada: N = 4
Salida: 1/2, 1/3, 1/4, 2/3, 3/4
Método:
recorrer todos los numeradores sobre [1, N-1] y, para cada uno de ellos, recorrer todos los denominadores en el rango [numerador+1, N] y verificar si el numerador y el denominador son coprimos o no. Si se encuentra que es coprimo, imprima la fracción.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement the // above approach #include <bits/stdc++.h> using namespace std; // Function to print all // proper fractions void printFractions(int n) { for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { // If the numerator and the // denominator are coprime if (__gcd(i, j) == 1) { string a = to_string(i); string b = to_string(j); cout << a + "/" + b << ", "; } } } } // Driver Code int main() { int n = 3; printFractions(n); return 0; }
Java
// Java program to implement the // above approach class GFG{ // Function to print all // proper fractions static void printFractions(int n) { for(int i = 1; i < n; i++) { for(int j = i + 1; j <= n; j++) { // If the numerator and the // denominator are coprime if (__gcd(i, j) == 1) { String a = String.valueOf(i); String b = String.valueOf(j); System.out.print(a + "/" + b + ", "); } } } } static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void main(String[] args) { int n = 3; printFractions(n); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the # above approach # Function to print # all proper functions def printfractions(n): for i in range(1, n): for j in range(i + 1, n + 1): # If the numerator and # denominator are coprime if __gcd(i, j) == 1: a = str(i) b = str(j) print(a + '/' + b, end = ", ") def __gcd(a, b): if b == 0: return a else: return __gcd(b, a % b) # Driver code if __name__=='__main__': n = 3 printfractions(n) # This code is contributed by virusbuddah_
C#
// C# program to implement the // above approach using System; class GFG{ // Function to print all // proper fractions static void printFractions(int n) { for(int i = 1; i < n; i++) { for(int j = i + 1; j <= n; j++) { // If the numerator and the // denominator are coprime if (__gcd(i, j) == 1) { string a = i.ToString(); string b = j.ToString(); Console.Write(a + "/" + b + ", "); } } } } static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver code public static void Main(string[] args) { int n = 3; printFractions(n); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript program for the above approach // Function to print all proper functions const printFractions = (n) => { for (var i = 1; i < n; i++) { for (var j = i + 1; j <= n; j++) { // If the numerator and denominator are coprime if(__gcd(i, j) == 1){ let a = `${i}`; let b = `${j}`; document.write(`${a}/${b}, `) } } } } const __gcd = (a, b) => { if(b == 0){ return a; }else{ return __gcd(b, a % b); } } // Driver code let n = 3; printFractions(n); // This article is contributed by _saurabh_jaiswal </script>
Producción:
1/2, 1/3, 2/3,
Complejidad temporal: O(N 2 log N)
Espacio auxiliar: O(1)