elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Guía rápida para descarga de herramientas gratuitas de seguridad y desinfección


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Alguna manera de saber si un numero es narcisista sin utilizar el pow?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Alguna manera de saber si un numero es narcisista sin utilizar el pow?  (Leído 1,403 veces)
valrojo

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« en: 1 Noviembre 2019, 20:08 pm »

Había pensado utilizar Res = Exponencial(potencia*ln(base)), pero nos piden que lo calculemos utilizando bucles.

He hecho esto
#include <iostream>
using namespace std;

int main()
{
    int cifras = 1, y, z, x, suma = 0;
   
    cout << "Dame numero: ";
    cin >> x;
   
    y = x;

    while (x > 9)
    {
        x = x / 10;
        cifras++;
    }
   
    for (int i = 0; i <= cifras; i++)
    {
        z = y % 10;
        suma = suma + //// Aqui pondria el pow :(
        y = y / 10;
    }
   
    if (suma == 0)
        cout <<"El numero es narcisista.";
       
    else
        cout << "El numero no es narcisista.";
}


En línea

K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 916



Ver Perfil
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #1 en: 1 Noviembre 2019, 21:03 pm »

Antes de nada, los códigos entre etiquetas de Código GeSHi.
Lo único que tienes que hacer es usar un bucle para "simular" la función <pow()>. Como la función <pow()> lo que hace es elevar la base a una potencia y las potencias no son otra cosa que sucesivos productos, lo que al final te piden es que calcules la potencia de un número usando un bucle que multiplique ese número x veces.
En pseudocódigo tu solución quedaría así:
Código:
INICIO
    PEDIR numero
    digitos[LONGITUD_MAXIMA] // array de longitud igual al maximo numero de digitos que puede tener el numero
    numeroDigitos := calcularDigitos(numero, digitos)

    sumaTotal := 0
    PARA i := 0 HASTA numeroDigitos-1 HACER
        resultadoPotencia := 1
        PARA j := 0 HASTA numeroDigitos-1 HACER // Este es el bucle que simula la potencia
            resultadoPotencia := resultadoPotencia * digitos[i]
        FIN PARA
        sumaTotal := sumaTotal + resultadoPotencia
    FIN PARA

    SI sumaTotal == numero ENTONCES
        MOSTRAR "El numero es narcisista"
    SINO ENTONCES
        MOSTRAR "El numero no es narcisista"
    FIN SI
FIN
Ahora te queda a ti ver cómo sería la función <calcularDigitos()> ya que no existe de manera predefinida y cómo traducir este pseudocódigo a C++. Bueno... Y lo más importante: entender el procedimiento.


En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
Mecanma

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #2 en: 12 Noviembre 2019, 03:01 am »

Upss.
Código
  1. int potencia(int base, int exponente){
  2. long int producto = base;
  3. for(int i = 1; i<exponente;i++){
  4. producto *= base;
  5. }
  6. return producto;
  7. }
  8.  

PD: ¿Alguien me puede decir donde picar codigo?
En línea

CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #3 en: 12 Noviembre 2019, 15:38 pm »

Hay que tener cuidado con exponente 0 o negativo.

Se puede iterar menos veces si en vez de multiplicar siempre por la base, se eleva al cuadrado y se divide el exponente por la mitad, multiplicando ese valor por el resultado final cuando el valor del exponente es impar.
En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 916



Ver Perfil
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #4 en: 12 Noviembre 2019, 18:10 pm »

En este caso se trata del cálculo de números narcisistas por lo que el número tendrá mínimo 1 dígito. Entonces la "potencia" siempre sería de exponente 1 como mínimo por lo que no hay que tener en cuenta exponentes negativos o 0.
En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 103


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #5 en: 19 Noviembre 2019, 14:14 pm »

Es un problema muy bonito.  :D

En pseudocódigo tu solución quedaría así:
Código:
INICIO
    PEDIR numero
    digitos[LONGITUD_MAXIMA] // array de longitud igual al maximo numero de digitos que puede tener el numero
    numeroDigitos := calcularDigitos(numero, digitos)
...
FIN

La solución por YreX-DwX parece correcta, pero un poco ineficaz, ya qu está en complejidad O(log^2(N)). A grandes rasgos, esto quiere decir que para un número de 10 cifras, hace 10*10 veces la operación más intern, para uno de 1000, hace 1000*1000 veces...


Yo propongo una solucion en O(log(N)), es decir , para un numero de 10 cifras, hace 10*10 veces la operación  . Para uno de 1000, hace 1000*10 veces la operación interna...., Para uno de 4000 cifras, hace 4000*10 veces la operación interna...  Y en espacio es O(10)=O(1), y que solo hay 10 digtos posibles...

Código
  1. /*
  2.  
  3.   Title: Narcisist number (in  base 10)
  4.  
  5.   P : N == \sum i : 0 <= i <= log(N): a_i*10^i
  6.   Q : N==\sum i : 0 <= i <= log(N): a_i^{log(N)+1}
  7.  
  8.  
  9. 3     2     1     0
  10. +-----+-----+-----+
  11. |  1  |  5  |   3 |  YES, since 153=1^3+5^3+3^3
  12. +-----+-----+-----+
  13.  
  14.  
  15.  
  16. I ::= 0<=n<=log(N)+1 and Q[log(N)/n-1] and
  17.       M=N/10^n and
  18.       (n<=log(N) ->
  19.       (\forall i : 0 <= i < 10 : pow[i]=i^n and frec[i]=FREC(i,N%10^n)))
  20.  
  21. !B ::= n==log (N)+1
  22.  
  23. B ::= n<log (N)+1  ; // i.e. M>0
  24.  
  25. Init:
  26. -----
  27.   n,pow[0..9],frec[0..9]=0,
  28.  
  29.   |- P -> I [n/0,M/N,pow[0..9]=[1]^10, frec[0..9]=[0]^10]
  30.  
  31.  
  32. QUOTE(N,n) = log (N)+1 - n >= 0   (Cuota decreases)
  33.  
  34. Step:
  35. -----
  36.  
  37.  n = n + 1 ; // i.e. M = M/10 ;
  38.  
  39. */
  40.  
  41. #include <iostream>
  42. #include <cassert>
  43.  
  44. using namespace std;
  45.  
  46. int narcisist(const unsigned long long N)
  47. {
  48.  unsigned long long pow[10]={1,1,1,1,1,1,1,1,1,1} ; // [0-9]^0
  49.  unsigned long long frec[10]={0,0,0,0,0,0,0,0,0,0} ;
  50.  unsigned long long sum,M;
  51.  assert(N);
  52.  for (M=N ; M ;M/=10 )  // O(log(N)
  53.    {
  54.      frec[M%10]+=1;
  55.      int d;
  56.      for (sum=d=0 ; d<10 ;d++ )  // O(1)
  57. {
  58.  pow[d]*=d;
  59.  sum+=pow[d]*frec[d];
  60. }
  61.    }
  62.  //  cout <<"trace " << N << " " << sum << endl;
  63.  
  64.  return sum==N;
  65.  
  66. }
  67.  
  68. int main (int argc, char *args[])
  69. {
  70.  unsigned long long N;
  71.  for( ; cin >> N ; )
  72.    cout << narcisist(N) << endl;
  73.  return 0;
  74. }
  75.  

Solo me se 153 y 1634 como numero narcisistas en base 10... SI alguien sabe otros, puede comprobar...

Código:
g++ narcisista.cc -o main && ./main
1634
1
153
1
154
0
« Última modificación: 19 Noviembre 2019, 14:16 pm por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
hacksilver

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Re: Alguna manera de saber si un numero es narcisista sin utilizar el pow?
« Respuesta #6 en: 2 Diciembre 2019, 10:08 am »

Aunque el código de dijsktra haya alcanzado la complejidad requerida, lo veo aún algo ineficiente por el bucle de las líneas 56 a 60. Este blucle sobreescribe el valor de suma en cada iteración, sobreviviendo solamente el último calculado. Para mejorarlo, propongo eliminar la línea 59 y hacer el cálculo de suma en la línea 63, es decir, copiar las líneas 55, 56 y 59 al hueco de la 63. No debería variar la complejidad computacional pero sí mejorar la eficiencia.

Otra idea sería calcular las potencias de los dígitos no por multiplicación reiterada, alcanzando O(log N), sino por cuadrados sucesivos (cf. Exponentiation by squaring), lo que nos debería llevar a O(log log N), aunque quizás con datos int no podamos llegar a observar la diferencia.

EDIT: La complejidad O(log log N) se alcanzaría sólo para las potencias de los dígitos calculadas después de su frecuencia. El cálculo de estas frecuencias sigue siendo O(log N) y seguiría dominando la complejidad, aunque con este método reduciríamos el código a ejecutar O(log N) veces.
« Última modificación: 2 Diciembre 2019, 11:03 am por hacksilver » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
hay alguna manera de saber si una foto a sido trucada
Diseño Gráfico
‭lipman 3 1,915 Último mensaje 20 Septiembre 2006, 17:57 pm
por pisagatos
Alguna manera de saber quien subió archivos a mi server
PHP
NetStorm 4 3,546 Último mensaje 10 Junio 2011, 23:42 pm
por NetStorm
¿Alguna manera de saber si el chip de video se arruinó?
Hardware
ignorantev1.1 1 1,032 Último mensaje 5 Enero 2014, 18:24 pm
por joanj94
Numero narcisista
Programación C/C++
DamnSystem 1 3,479 Último mensaje 11 Noviembre 2017, 21:59 pm
por DamnSystem
¿hay alguna manera de saber en que plataforma fue desarrollada esta web? « 1 2 3 »
Desarrollo Web
chupachota 28 4,257 Último mensaje 16 Julio 2021, 22:48 pm
por chupachota
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines