Hola amigos, necesito me ayuden con un problema que estoy tratando de resolver pero que no sale.
El problema dice: Se dan dos numeros enteros positivos N y M, el problema es hallar la cantidad de pares de numeros enteros (a,b) con 1<=a<=N y 1<=b<=M y tal que (sqrt(a)+sqrt(b))^2 sea un numero enteroentero. (sqrt(n) es la raiz cuadrada de n).
Por ejemplo si N=2 y M=2 la respuesta es 2 (a,b)=(1,1) y (2,2).
Se entiende no?
Pongo lo que hice yo:
Es claro que para que (a,b) cumpla las condiciones sqrt(a*b) tiene que ser entero. (DEMOSTRACION: (sqrt(a)+sqrt(b))^2=(a+2*sqrt(a*b)+b) entonces como a y b son enteros 2*sqrt(a*b) tiene que ser entero, pero a*b es producto de dos enteros entonces para que toda la expresion sea entera (a*b) tiene que ser un cuadrado perfecto que en consecuencia sqrt(a*b) sea entero ).
Entonces me armo algo que pruebe todas las multiplicaciones posibles que son en total (M*N) y se fije en cada caso si tiene raiz cuadrada exacta, si lo es que incremente en 1 la cantidad de pares.
Pongo mi code, pero no se que estoy haciendo mal:
#include<iostream.h>
#include<math.h>
using namespace std;
main(){
int N, M;
cin>>N >>M;
int a=1,b=1;
long int producto=1;
int respuesta;
for(a=1;a<N;a++){
for(b=1;b<M;b++){
producto=a*b;
}
}
double raizab=sqrt(producto);
if(raizab*raizab==producto){
respuesta++;
}
cout<<"La cant de pares es " <<respuesta;
}
Agradeceria que me ayuden..
Nota: N y M son a lo sumo 77777
EDIT: Agregué la demostracion de por que si sqrt(a*b) es entero implica que el par (a,b) cumple lo pedido.
Buenas!
Primero. No analice la parte matematica, i.e. No me que claro que sqrt(a*b) entero implique (sqrt(a)+sqrt(b))^2 entero.
Segundo. Asumiendo que lo de arriba es true, lo que tenes mal es que el codigo:
double raizab=sqrt(producto);
if(raizab*raizab==producto){
respuesta++;
}
Tiene que estar dentro del for().
Saludos.
(Disculpa la desproligidad, escribo desde un celular :p)
La parte matemática está mal. Esto sería lo que está bien:
sqrt(a) * sqrt (b) = sqrt(a * b)
sqrt(a) + sqrt(b) = sqrt(a) + sqrt(b)
(sqrt(a) +sqrt(b))² = a + b + 2*sqrt(a*b)
Esto último es el cuadrado de una suma: cuadrado del primero más el cuadrado del segundo mas el doble del producto del primero por el segundo...
Este código que acabo de hacer creo que cumple con eso:
#include <iostream>
#include <cmath>
using namespace std;
//Definición de funciones.
bool esValido(int N, int M);
int main(int argc, char *argv[])
{
//Declaración de variables.
int N = 0;
int M = 0;
int contadorN = 1;
int contadorM = 1;
//Entrada de datos.
cout << "Introduce N:" << endl;
cin >> N;
cout << endl << "Introduce M:" << endl;
cin >> M;
//Mientras contadorN no llege a N.
while(contadorN <= N)
{
//Comprobamos si la raiz de a más la raiz de b al cuadrado es un número entero.
if(esValido(contadorN,contadorM))
{
//Si es un número entero desplegamos a y b.
cout<<"N: "<< contadorN << endl;
cout<<"M: "<< contadorM << endl << endl;
}
//Si contadorM llega a M aumentamos contadorN para probar con otros valores de N y volvemos a poner contadorM a 1.
if(contadorM == M)
{
contadorN++;
contadorM = 1;
}
else
{
++contadorM;
}
}
return 0;
}
bool esValido( int N,int M )
{
float numero = powf(sqrt(N)+sqrt(M),2);
if(numero == (int)numero)
return true;
else
return false;
}
No pero fijate que alcanza con que a*b sea un cuadrado perfecto (porque a y b son enteros, no sucederia lo mismo si a y b fuesen racionales), lo explico en la demostracion...
Si, tenes razon, como a y b son enteros basta con que sqrt(a*b) sea entero, lo que tenes mas es el codigo afuera del for, tiene que estar adentro!
Si tienes razón es verdad, de todas maneras el código que he puesto en el post de arriba me parece que funciona.
¡Un saludo!
Gracias por sus respuestas, pero no sé que parte de tu code está mal porque al correr el programa me tira algunos pares donde A o B son 0. Probé inicializando las variables en 1 pero tampoco funciona :)
Estamos mas cerca de la solucion...
Si entendí bien, creo que lo siguiente debería funcionar:
#include <stdio.h>
#include <math.h>
int main(int argc, char **argv) {
unsigned int n, m, a, b, contador = 0;
printf("Introduzca el valor de n: ");
scanf("%u", &n);
printf("Introduzca el valor de m: ");
scanf("%u", &m);
for (a = 1; a >= 1 && a <= n; ++a)
for (b = 1; b >= 1 && b <= m; ++b)
if (fmod(pow(sqrt(a * b), 2), 1) == 0)
++contador;
printf("Número de pares ordenados: %u\n", contador);
return 0;
}
EDIT:
#include <stdio.h>
#include <math.h>
int main(int argc, char **argv) {
unsigned int n, m, a, b, contador = 0;
printf("Introduzca el valor de n: ");
scanf("%u", &n);
printf("Introduzca el valor de m: ");
scanf("%u", &m);
for (a = 1; a <= n; ++a)
for (b = 1; b <= m; ++b)
if (fmod(pow(sqrt(a * b), 2), 1) == 0)
++contador;
printf("Número de pares ordenados: %u\n", contador);
return 0;
}
Cita de: naderST en 4 Febrero 2013, 01:49 AM
Si entendí bien, creo que lo siguiente debería funcionar:
Algo está mal, porque no arroja bien el resultado.
Por fin me salió a mi, paso mi code por si alguien puede optimizarlo:
#include<iostream.h>
#include<math.h>
using namespace std;
main(){
int N=1, M=1,a=1,b=1,CantdePares=0;
cout<<"Ingresa N ";
cin>>N;
cout<<"Ingresa M ";
cin>>M;
for(a=1;a<=N;a++){
for(b=1;b<=M;b++){
if((sqrt(a*b)*sqrt(a*b)==a*b)){
CantdePares++;
}
}
}
cout<<"La cantidad de pares es: " <<CantdePares;
return 0;
}
Muchas gracias por sus respuestas!
EDIT:
No me queda claro lo de la condición