Imprime todas las fracciones propias con denominadores menores que iguales a N

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/3

Entrada: 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)
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *