Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: jonyayala95 en 3 Febrero 2013, 23:50 pm


Título: Necesito una ayuda
Publicado por: jonyayala95 en 3 Febrero 2013, 23:50 pm
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:

Código
  1. #include<iostream.h>
  2. #include<math.h>
  3.  
  4. using namespace std;
  5.  
  6. main(){
  7. int N, M;
  8. cin>>N >>M;
  9.  
  10. int a=1,b=1;
  11. long int producto=1;
  12. int respuesta;
  13.  
  14.     for(a=1;a<N;a++){
  15.         for(b=1;b<M;b++){
  16.             producto=a*b;
  17.         }
  18.     }
  19.     double raizab=sqrt(producto);
  20.         if(raizab*raizab==producto){
  21.             respuesta++;
  22.         }
  23. cout<<"La cant de pares es " <<respuesta;
  24. }
  25.  
  26.  

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.

Título: Re: Necesito una ayuda
Publicado por: dooque en 4 Febrero 2013, 00:56 am
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)

Título: Re: Necesito una ayuda
Publicado por: avesudra en 4 Febrero 2013, 01:07 am
La parte matemática está mal. Esto sería lo que está bien:
Código:
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:
Código
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5. //Definición de funciones.
  6. bool esValido(int N, int M);
  7.  
  8. int main(int argc, char *argv[])
  9. {
  10.     //Declaración de variables.
  11.     int N = 0;
  12.     int M = 0;
  13.     int contadorN = 1;
  14.     int contadorM = 1;
  15.     //Entrada de datos.
  16.     cout << "Introduce N:" << endl;
  17.     cin >> N;
  18.     cout << endl << "Introduce M:" << endl;
  19.     cin >> M;
  20.     //Mientras contadorN no llege a N.
  21.     while(contadorN <= N)
  22.     {
  23.         //Comprobamos si la raiz de a más la raiz de b al cuadrado es un número entero.
  24.         if(esValido(contadorN,contadorM))
  25.         {
  26.             //Si es un número entero desplegamos a y b.
  27.             cout<<"N: "<< contadorN << endl;
  28.             cout<<"M: "<< contadorM << endl << endl;
  29.         }
  30.         //Si contadorM llega a M aumentamos contadorN para probar con otros valores de N y volvemos a poner contadorM a 1.
  31.         if(contadorM == M)
  32.         {
  33.             contadorN++;
  34.             contadorM = 1;
  35.         }
  36.         else
  37.         {
  38.             ++contadorM;
  39.         }
  40.     }
  41.     return   0;
  42. }
  43. bool esValido( int N,int M )
  44. {
  45.     float numero = powf(sqrt(N)+sqrt(M),2);
  46.     if(numero == (int)numero)
  47.         return true;
  48.     else
  49.         return false;
  50. }

Título: Re: Necesito una ayuda
Publicado por: jonyayala95 en 4 Febrero 2013, 01:17 am
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...

Título: Re: Necesito una ayuda
Publicado por: dooque en 4 Febrero 2013, 01:19 am
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!

Título: Re: Necesito una ayuda
Publicado por: avesudra en 4 Febrero 2013, 01:25 am
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!

Título: Re: Necesito una ayuda
Publicado por: jonyayala95 en 4 Febrero 2013, 01:41 am
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...

Título: Re: Necesito una ayuda
Publicado por: naderST en 4 Febrero 2013, 01:49 am
Si entendí bien, creo que lo siguiente debería funcionar:

Código
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. int main(int argc, char **argv) {
  5. 	unsigned int n, m, a, b, contador = 0;
  6.  
  7. 	printf("Introduzca el valor de n: ");
  8. 	scanf("%u", &n);
  9. 	printf("Introduzca el valor de m: ");
  10. 	scanf("%u", &m);
  11.  
  12. 	for (a = 1; a >= 1 && a <= n; ++a)
  13. 		for (b = 1; b >= 1 && b <= m; ++b)
  14. 			if (fmod(pow(sqrt(a * b), 2), 1) == 0)
  15. 				++contador;
  16.  
  17. 	printf("Número de pares ordenados: %u\n", contador);
  18.  
  19. 	return 0;
  20. }
  21.  

EDIT:

Código
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. int main(int argc, char **argv) {
  5. 	unsigned int n, m, a, b, contador = 0;
  6.  
  7. 	printf("Introduzca el valor de n: ");
  8. 	scanf("%u", &n);
  9. 	printf("Introduzca el valor de m: ");
  10. 	scanf("%u", &m);
  11.  
  12. 	for (a = 1; a <= n; ++a)
  13. 		for (b = 1; b <= m; ++b)
  14. 			if (fmod(pow(sqrt(a * b), 2), 1) == 0)
  15. 				++contador;
  16.  
  17. 	printf("Número de pares ordenados: %u\n", contador);
  18.  
  19. 	return 0;
  20. }
  21.  

Título: Re: Necesito una ayuda
Publicado por: jonyayala95 en 4 Febrero 2013, 03:02 am

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:

Código
  1. #include<iostream.h>
  2. #include<math.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. main(){
  8. int N=1, M=1,a=1,b=1,CantdePares=0;
  9.  
  10. cout<<"Ingresa N ";
  11. cin>>N;
  12.  
  13. cout<<"Ingresa M ";
  14. cin>>M;
  15.  
  16. for(a=1;a<=N;a++){
  17.     for(b=1;b<=M;b++){
  18.         if((sqrt(a*b)*sqrt(a*b)==a*b)){
  19.             CantdePares++;
  20.         }
  21.     }
  22. }
  23.  
  24. cout<<"La cantidad de pares es: " <<CantdePares;
  25. return 0;
  26. }
  27.  
  28.  

Muchas gracias por sus respuestas!

Título: Re: Necesito una ayuda
Publicado por: naderST en 4 Febrero 2013, 03:05 am
EDIT:

No me queda claro lo de la condición


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines