Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Java » Aproximación diofántica

Java - Aproximación diofántica

Volver
Nuevo Tema
<<>>
 
Vista:
sin imagen de perfil

Aproximación diofántica

Publicado por anonymous (5 intervenciones) el 13/11/2021 19:03:26
Hola, necesito una pequeña ayudita con el siguiente método.
Tengo que estudiar la aproximación diofántica, un algoritmo para aproximar un número real con una fracción (un número racional).
He hecho todos los métodos de la clase, pero la implementación del algoritmo de aproximación diofántica en el método _approximate no sé cómo se haría. El método recibe como parámetro el número real que hay que aproximar y la tolerancia (épsilon) con el que hay que aproximarlo. Este método devuelve la fracción que aproxima al número real como un objeto RationalNumber.

Alguien se le ocurre una forma de resolverlo?
hhh
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Aproximación diofántica

Publicado por Tom (1831 intervenciones) el 13/11/2021 20:54:00
Yo no veo muy claro lo que tienes que hacer ... no entiendo si quieres hacer una búsqueda binaria de forma recursiva o iterativa ... vamos que no sabría resover tu TODO.

Pero este algoritmo, extraído de wikipedia, parece que podría funcionar (aunque yo me ahorro el epsilon, sería cuestión de meterlo en la comparación de igualdad):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Stern_Brocot {
	/* */
	public static void main(String args[]) {
		approximate(0.25, 0.01);
	}
	/* */
	public static Rational approximate(double v, double e) {
		Rational res;
		Rational L = new Rational(0, 1); // Lower
		Rational H = new Rational(1, 0); // Higher
 
		while(true) {
			Rational M = mediant(L, H); // Middle point
			if(M.value() < v) {
				L = M;
			} else if(M.value() > v) {
				H = M;
			} else {
				// Found
				res = M;
				break;
			}
		}
 
		System.out.printf("Found %d / %d (%f)\n", res.a, res.b, res.value());
		return res;
	}
	/* */
	public static Rational mediant(Rational l, Rational r) {
		return new Rational(l.a + r.a, l.b + r.b);
	}
	/* */
	public static record Rational(int a, int b) {
		/* */
		double value() {
			return (double)a / b;
		}
	}
}

El record Rational debería ser equivalente a tu clase RationalNumber, supongo.

Ah! Y resulta que en wikipedia hay un enlace a una implementación del mismo algoritno, bastante mejor que la mía:

https://introcs.cs.princeton.edu/java/92symbolic/RationalApprox.java.html
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
sin imagen de perfil

Aproximación diofántica

Publicado por anonymous (5 intervenciones) el 13/11/2021 21:33:23
Es decir, lo que tengo que hacer, es encontrar la aproximación diofántica haciendo una búsqueda binaria en el intervalo unitario:

1- Sea L = 0/1 (es decir, 0) y sea R = 1/1 (es decir, 1).

2- Elegir algún número racional M entre L y R.

3- Si |x − M| < ε, devuelva M y termine. 4 De lo contrario, actualice L (si M < x) o R (si M > x) y regrese a 2.

(
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Aproximación diofántica

Publicado por Tom (1831 intervenciones) el 13/11/2021 21:47:20
Bueno ... y ¿ no eres capaz de hacerlo con lo que he pegado ?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
sin imagen de perfil

Aproximación diofántica

Publicado por anonymous (5 intervenciones) el 13/11/2021 21:52:10
No....Porque no tengo de cambiar nada de lo que he pasado, es decir, solo tengo que rellenar donde pone TODO, sin cambiar nada de lo otro. no sé si me explico
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Aproximación diofántica

Publicado por Tom (1831 intervenciones) el 13/11/2021 22:08:45
Joé, pero cúrratelo un poquito. Copio y pego del enlace (que te puse) de la wikipedia que sí comprueba el epsilon:

double error = Math.abs(mediant.toDouble() - x);

Lo que en mi código podría ser:

1
2
3
4
5
6
7
8
9
10
11
12
while(true) {
			Rational M = mediant(L, H);
			if(Math.abs(M.value() - v) < e) {
				// Found
				res = M;
				break;
			} else if(M.value() < v) {
				L = M;
			} else if(M.value() > v) {
				H = M;
			}
		}

Y, no entiendo porqué quieres usar R (1,1) ... lo suyo es usar R (1,0) o sea infinito, en todo caso, cambia
Rational H = new Rational(1, 0); // Higher
por
Rational R = one;

Y no sé si tienes que implementar getMiddlePoint, pero resulta evidente que es la misma que mediant(). Me da la impresión de que no tienes nada claro el algoritmo que debes implementar ...
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar