Tenemos un número N. Encuentre la fracción propia más grande a/b tal que a + b = N. Las siguientes son restricciones para la fracción.
- a/b es una fracción propia si a<b y ayb son coprimos, es decir, no hay factor común de ayb.
- Puede haber múltiples fracciones propias con suma de numerador y denominador igual a un número dado. La tarea principal es encontrar la fracción que tiene el valor máximo de coma flotante.
Ejemplos:
Input : N = 3
Output : 1 2
Input : N = 12
Output : 5 7
Explanation: In the second example N = 12
Possible a and b's are: 1 11
5 7
But clearly 5/7 (=0.71..) is greater than
1/11 (=0.09..). Hence answer for N = 12
is 5 7.
La solución a este problema es más intuitiva que algorítmica.
Considere cuidadosamente los siguientes puntos para comprender la fórmula presentada más adelante:
- Una fracción tiene valor máximo si el numerador es lo más grande posible y el denominador es lo más pequeño posible.
- Aquí las restricciones son los hechos de que el numerador no puede ser mayor que el denominador y su suma debe sumar N.
Teniendo en cuenta estos dos puntos, podemos llegar al hecho de que la respuesta a este problema será ceil(n/2)-1 y floor(n/2)+1.
Ahora bien, esta solución siempre funcionará para N impares y todos aquellos N pares cuyo (N/2) sea par. Esto se debe a que estos dos casos siempre generarán coprimos con la fórmula anterior.
Ahora considere el siguiente ejemplo:
N = 10
ceil(10/2)-1 = 4
floor(10/2)+1 = 6
Claramente 4 y 6 son las respuestas incorrectas ya que no son coprimos. La respuesta correcta es 3 y 7.
Por lo tanto, para N par con impar (N/2), la fórmula se convierte en ceil(n/2)-2 y floor(n/2)+2.
C++
// CPP program to find the largest fraction
// a/b such that a+b is equal to given number
// and a < b.
#include <iostream>
#include <cmath>
using namespace std;
void solve(int n)
{
// Calculate N/2;
float a = (float)n / 2;
// Check if N is odd or even
if (n % 2 != 0)
// If N is odd answer will be
// ceil(n/2)-1 and floor(n/2)+1
cout << ceil(a) - 1 << " "
<< floor(a) + 1 << endl;
else {
// If N is even check if N/2 i.e a
// is even or odd
if ((int)a % 2 == 0) {
// If N/2 is even apply the
// previous formula
cout << ceil(a) - 1 << " "
<< floor(a) + 1 << endl;
}
else {
// If N/2 is odd answer will be
// ceil(N/2)-2 and floor(N/2)+2
cout << ceil(a) - 2 << " "
<< floor(a) + 2 << endl;
}
}
}
// driver function
int main()
{
int n = 34;
solve(n);
return 0;
}
Java
// Java program to find the
// largest fraction a/b
// such that a+b is equal
// to given number and a < b.
class GFG
{
public static void solve(int n)
{
// Calculate N/2;
double a = n / 2;
// Check if N is
// odd or even
if (n % 2 != 0)
{
// If N is odd answer
// will be ceil(n/2)-1
// and floor(n/2)+1
System.out.println((Math.ceil(a) - 1) +
" " + (Math.floor(a) + 1));
}
else
{
// If N is even check
// if N/2 i.e a
// is even or odd
if ((int)(a) % 2 == 0)
{
// If N/2 is even apply
// the previous formula
System.out.println((Math.ceil(a) - 1) +
" " + (Math.floor(a) + 1));
}
else
{
// If N/2 is odd answer
// will be ceil(N/2)-2
// and floor(N/2)+2
System.out.println((Math.ceil(a) - 2) +
" " + (Math.floor(a) + 2));
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 34;
solve(n);
}
}
// This code is contributed
// by mits
Python3
# Python3 program to find # the largest fraction a/b # such that a+b is equal to # given number and a < b. import math def solve(n): # Calculate N/2; a = float(n / 2); # Check if N is odd or even if (n % 2 != 0): # If N is odd answer # will be ceil(n/2)-1 # and floor(n/2)+1 print((math.ceil(a) - 1), (math.floor(a) + 1)); else: # If N is even check if N/2 # i.e a is even or odd if (a % 2 == 0): # If N/2 is even apply # the previous formula print((math.ceil(a) - 1), (math.floor(a) + 1)); else: # If N/2 is odd answer # will be ceil(N/2)-2 # and floor(N/2)+2 print((math.ceil(a) - 2), (math.floor(a) + 2)); # Driver Code n = 34; solve(n); # This code is contributed by mits
C#
// C# program to find the
// largest fraction a/b
// such that a+b is equal
// to given number and a < b.
using System;
class GFG
{
public static void solve(int n)
{
// Calculate N/2;
double a = n / 2;
// Check if N is
// odd or even
if (n % 2 != 0)
{
// If N is odd answer
// will be ceil(n/2)-1
// and floor(n/2)+1
Console.WriteLine((Math.Ceiling(a) - 1) +
" " + (Math.Floor(a) + 1));
}
else
{
// If N is even check
// if N/2 i.e a
// is even or odd
if ((int)(a) % 2 == 0)
{
// If N/2 is even apply
// the previous formula
Console.WriteLine((Math.Ceiling(a) - 1) +
" " + (Math.Floor(a) + 1));
}
else
{
// If N/2 is odd answer
// will be ceil(N/2)-2
// and floor(N/2)+2
Console.WriteLine((Math.Ceiling(a) - 2) +
" " + (Math.Floor(a) + 2));
}
}
}
// Driver code
public static void Main()
{
int n = 34;
solve(n);
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find the largest
// fraction a/b such that a+b is
// equal to given number and a < b.
function solve($n)
{
// Calculate N/2;
$a = (float)$n / 2;
// Check if N is odd or even
if ($n % 2 != 0)
// If N is odd answer will
// be ceil(n/2)-1 and
// floor(n/2)+1
echo ceil($a) - 1, " ",
floor($a) + 1, "\n";
else {
// If N is even check if N/2
// i.e a is even or odd
if ($a % 2 == 0) {
// If N/2 is even apply
// the previous formula
echo ceil($a) - 1, " ",
floor($a) + 1, "\n";
}
else {
// If N/2 is odd answer
// will be ceil(N/2)-2
// and floor(N/2)+2
echo ceil($a) - 2, " ",
floor($a) + 2, "\n";
}
}
}
// driver function
$n = 34;
solve($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the
// largest fraction a/b
// such that a+b is equal
// to given number and a < b.
function solve(n)
{
// Calculate N/2;
let a = n / 2;
// Check if N is
// odd or even
if (n % 2 != 0)
{
// If N is odd answer
// will be ceil(n/2)-1
// and floor(n/2)+1
document.write((Math.ceil(a) - 1) +
" " + (Math.floor(a) + 1));
}
else
{
// If N is even check
// if N/2 i.e a
// is even or odd
if (parseInt(a, 10) % 2 == 0)
{
// If N/2 is even apply
// the previous formula
document.write((Math.ceil(a) - 1) +
" " + (Math.floor(a) + 1));
}
else
{
// If N/2 is odd answer
// will be ceil(N/2)-2
// and floor(N/2)+2
document.write((Math.ceil(a) - 2) +
" " + (Math.floor(a) + 2));
}
}
}
let n = 34;
solve(n);
</script>
Producción:
15 19
Complejidad de tiempo: O(1), el código se ejecutará en tiempo O(1).
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Este artículo es una contribución de Vineet Joshi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA