Resolución de ecuaciones diofánticas lineales

Jorge Castillo Mateo

/* Programa que resuelve ecuaciones diofánticas del tipo ax + by = c
dando todas las posibles x e y soluciones enteras */

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

int mcd (int a, int b); //prototipo de la función del mcd

int main()
{
//——————————————-Introducción de datos de la ecuación
int a, b, c;

cout << “\n Sea ax + by = c una ecuacion diofantica, escriba los valores enteros de a, b, c: \n”;
cin >> a >> b >> c;
cout << endl << endl;
//——————————————-Calculamos mcd de a, b
int d;

d = mcd (a, b);

//——————————————-si mcd no divide a c no existe solución y finaliza programa
if (c % d != 0){
cout << “Esta ecuacion diofantica no tiene soluciones enteras. \n\n”;
fflush(stdin);
getchar();
return 0;
}

//——————————————-Teorema de Euclides
int dm = 100, n = 1;
int q[dm], r[dm];

r[0] = a;
r[1] = b;

while (r[n] > 0){
n = n++;
q[n] = trunc(r[n – 2] / r[n – 1]);
r[n] = r[n – 2] % r[n – 1];
}

//——————————————-Identidad de Bezout dice d = au + bv
int u_, v_;
int u[n], v[n];

u[0] = 1; v[0] = 0;
u[1] = 0; v[1] = 1;

for (int i=2;i<=n;i++){
u[i] = u[i – 2] + (-q[i]) * u[i – 1];
v[i] = v[i – 2] + (-q[i]) * v[i – 1];
}

u_ = u[n-1];
v_ = v[n-1];

//——————————————-Primeros resultados enteros de la ecuación xo, yo
int xo, yo;

xo = c * u_ / d;
yo = c * v_ / d;

//——————————————-Escribimos todas las posibles soluciones
cout << “\n Todas las soluciones enteras de la ecuacion (” << a << “)x + (” << b << “)y = ” << c << ” son:\n”;
cout << “x = ” << xo << ” + t * ” << b/d << endl;
cout << “y = ” << yo << ” – t * ” << a/d << ” con t perteneciente a los numeros enteros.” << endl << endl;

return 0;
}

// Función que nos calcula el Máximo común divisor de 2 números (enteros)
int mcd (int a, int b)
{
int t;
a = abs(a);
b = abs(b);
while (a > 0){
t = a;
a = b % a;
b = t;
}
return b;
}

Anuncios
Esta entrada fue publicada en Informática e Internet. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s