Encuentre la fracción más cercana a la fracción dada que tenga una diferencia absoluta mínima

Dados tres enteros x , y y n , la tarea es encontrar tal par de enteros a, b (1 <= b <= n; 0 <= a) que el valor |x/y – a/b| es lo mínimo posible, donde |x| representa el valor absoluto de x.

Ejemplos:

Entrada: x = 3, y = 7, n = 6
Salida: 2/5
Explicación: a=2 y b=5 y b<=6 luego 3/7 – 2/5 = 1/35, que es la diferencia mínima posible

Entrada: x = 12, y = 37, n = 5
Salida: 1/3

Enfoque: Iterar sobre el denominador. Sea el denominador i . Entonces se requiere elegir un numerador d tal que |x/y – d/i| es mínimo d = (x*i)/y es una buena opción. También verifique d+1 . Mientras actualiza la respuesta de A/B a d/i, compruebe si x/y – d/i < x/y -A/B o (B*xy*A) * (i*y) > (i*xy* d) * (B*y). Siga los pasos a continuación para resolver el problema:

• Inicialice las variables A y B como -1 para almacenar las respuestas.
• Iterar sobre el rango [1, N] usando la variable i y realizar los siguientes pasos:
  • Inicialice la variable d como (i*x)/y como el numerador más cercano posible.
  • Si d es mayor que igual a 0 y A es igual a -1 o ABS(B * x – y * A) * ABS(i * y) es mayor que ABS(i * x – y * d) * ABS(B * y), luego establezca el valor de A como d y B como i.
  • Aumenta el valor de d en 1.
  • Si d es mayor que igual a 0 y A es igual a -1 o ABS(B * x – y * A) * ABS(i * y) es mayor que ABS(i * x – y * d) * ABS(B * y), luego establezca el valor de A como d y B como i.
• Después de realizar los pasos anteriores, imprima el valor de A/B como respuesta.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the absolute
// value of x
long long ABS(long long x) { return max(x, -x); }
 
// Function to find the fraction with
// minimum absolute difference
void findFraction(long long x, long long y, long long n)
{
 
    // Initialize the answer variables
    long long A = -1, B = -1;
 
    // Iterate over the range
    for (long long i = 1; i <= n; i++) {
 
        // Nearest fraction
        long long d = (i * x) / y;
 
        // x/y - d/i < x/y -A/B
        //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y)
        if (d >= 0
            && (A == -1
                || ABS(B * x - y * A) * ABS(i * y)
                       > ABS(i * x - y * d) * ABS(B * y)))
            A = d, B = i;
 
        // Check for d+1
        d++;
        if (d >= 0
            && (A == -1
                || ABS(B * x - y * A) * ABS(i * y)
                       > ABS(i * x - y * d) * ABS(B * y)))
            A = d, B = i;
    }
 
    // Print the answer
    cout << A << "/" << B << endl;
}
 
// Driver Code
int main()
{
 
    long long x = 3, y = 7, n = 6;
 
    findFraction(x, y, n);
 
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG
{
   
    // Function to find the absolute
    // value of x
    static long ABS(long x) { return Math.max(x, -x); }
 
    // Function to find the fraction with
    // minimum absolute difference
    static void findFraction(long x, long y, long n)
    {
 
        // Initialize the answer variables
        long A = -1, B = -1;
 
        // Iterate over the range
        for (long i = 1; i <= n; i++) {
 
            // Nearest fraction
            long d = (i * x) / y;
 
            // x/y - d/i < x/y -A/B
            //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y)
            if (d >= 0
                && (A == -1
                    || ABS(B * x - y * A) * ABS(i * y)
                           > ABS(i * x - y * d)
                                 * ABS(B * y)))
                A = d;
            B = i;
 
            // Check for d+1
            d++;
            if (d >= 0
                && (A == -1
                    || ABS(B * x - y * A) * ABS(i * y)
                           > ABS(i * x - y * d)
                                 * ABS(B * y)))
                A = d;
            B = i;
        }
        A--;
        B--;
       
        // Print the answer
        System.out.println(A + "/" + B);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        long x = 3;
        long y = 7;
        long n = 6;
 
        findFraction(x, y, n);
    }
}
 
// This code is contributed by lokeshpotta.

# Python3 program for the above approach
 
# Function to find the absolute
# value of x
def ABS(x):
     
    return max(x, -x)
 
# Function to find the fraction with
# minimum absolute difference
def findFraction(x, y, n):
 
    # Initialize the answer variables
    A = -1
    B = -1
 
    # Iterate over the range
    for i in range(1, n + 1):
 
        # Nearest fraction
        d = (i * x) // y
 
        # x/y - d/i < x/y -A/B
        # (B*x-y*A) * (i*y) > (i*x-y*d) * (B*y)
        if (d >= 0 and (A == -1 or
           ABS(B * x - y * A) * ABS(i * y) >
           ABS(i * x - y * d) * ABS(B * y))):
            A = d
            B = i
 
        # Check for d+1
        d += 1
        if (d >= 0 and (A == -1 or
           ABS(B * x - y * A) * ABS(i * y) >
           ABS(i * x - y * d) * ABS(B * y))):
            A = d
            B = i
 
    # Print the answer
    print(str(A) + "/" + str(B))
 
# Driver Code
if __name__ == '__main__':
 
    x = 3
    y = 7
    n = 6
 
    findFraction(x, y, n)
 
# This code is contributed by mohit kumar 29

// C# code for the above approach
using System;
 
public class GFG{
 
    // Function to find the absolute
    // value of x
    static long ABS(long x) { return Math.Max(x, -x); }
 
    // Function to find the fraction with
    // minimum absolute difference
    static void findFraction(long x, long y, long n)
    {
 
        // Initialize the answer variables
        long A = -1, B = -1;
 
        // Iterate over the range
        for (long i = 1; i <= n; i++) {
 
            // Nearest fraction
            long d = (i * x) / y;
 
            // x/y - d/i < x/y -A/B
            //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y)
            if (d >= 0
                && (A == -1
                    || ABS(B * x - y * A) * ABS(i * y)
                           > ABS(i * x - y * d)
                                 * ABS(B * y)))
                A = d;
            B = i;
 
            // Check for d+1
            d++;
            if (d >= 0
                && (A == -1
                    || ABS(B * x - y * A) * ABS(i * y)
                           > ABS(i * x - y * d)
                                 * ABS(B * y)))
                A = d;
            B = i;
        }
        A--;
        B--;
       
        // Print the answer
        Console.Write(A + "/" + B);
    }
 
    // Driver Code
    static public void Main (){
 
        long x = 3;
        long y = 7;
        long n = 6;
 
        findFraction(x, y, n);
    }
}
 
// This code is contributed by shubhamsingh10.

<script>
 
// JavaScript program for the above approach
 
// Function to find the absolute
// value of x
function ABS(x)
{
    return Math.max(x, -x);
}
 
// Function to find the fraction with
// minimum absolute difference
function findFraction(x, y, n)
{
     
    // Initialize the answer variables
    let A = -1, B = -1;
 
    // Iterate over the range
    for(let i = 1; i <= n; i++)
    {
         
        // Nearest fraction
        let d = Math.floor((i * x) / y);
 
        // x/y - d/i < x/y -A/B
        //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y)
        if (d >= 0 && (A == -1 || ABS(B * x - y * A) *
            ABS(i * y) > ABS(i * x - y * d) * ABS(B * y)))
            A = d;
             
        B = i;
 
        // Check for d+1
        d++;
        if (d >= 0 && (A == -1 || ABS(B * x - y * A) *
            ABS(i * y) > ABS(i * x - y * d) * ABS(B * y)))
            A = d;
             
        B = i;
    }
    A--;
    B--;
   
    // Print the answer
    document.write(A + "/" + B);
}
 
// Driver code
let x = 3;
let y = 7;
let n = 6;
 
findFraction(x, y, n);
 
// This code is contributed by sanjoy_62
 
</script>

2/5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)