Alguna manera de saber si un numero es narcisista sin utilizar el pow?

[valrojo]

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.";
}

[K-YreX]

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 [Seleccionar] Expandir


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.

[Mecanma]

Upss.

Código (cpp) [Seleccionar] Expandir


int potencia(int base, int exponente){
long int producto = base;
for(int i = 1; i<exponente;i++){
producto *= base;
}
return producto;
}


PD: ¿Alguien me puede decir donde picar codigo?

[CalgaryCorpus]

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.

[K-YreX]

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.

[dijsktra]

Es un problema muy bonito.  

En pseudocódigo tu solución quedaría así:

Código [Seleccionar] Expandir


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 (cpp) [Seleccionar] Expandir


/*

 Title: Narcisist number (in  base 10)

 P : N == \sum i : 0 <= i <= log(N): a_i*10^i
 Q : N==\sum i : 0 <= i <= log(N): a_i^{log(N)+1}


3     2     1     0
+-----+-----+-----+
|  1  |  5  |   3 |  YES, since 153=1^3+5^3+3^3
+-----+-----+-----+



I ::= 0<=n<=log(N)+1 and Q[log(N)/n-1] and
     M=N/10^n and
     (n<=log(N) ->
     (\forall i : 0 <= i < 10 : pow[i]=i^n and frec[i]=FREC(i,N%10^n)))

!B ::= n==log (N)+1

B ::= n<log (N)+1  ; // i.e. M>0

Init:
-----
 n,pow[0..9],frec[0..9]=0,
 
 |- P -> I [n/0,M/N,pow[0..9]=[1]^10, frec[0..9]=[0]^10]


QUOTE(N,n) = log (N)+1 - n >= 0   (Cuota decreases)

Step:
-----

n = n + 1 ; // i.e. M = M/10 ;

*/

#include <iostream>
#include <cassert>

using namespace std;

int narcisist(const unsigned long long N)
{
 unsigned long long pow[10]={1,1,1,1,1,1,1,1,1,1} ; // [0-9]^0
 unsigned long long frec[10]={0,0,0,0,0,0,0,0,0,0} ;
 unsigned long long sum,M;
 assert(N);
 for (M=N ; M ;M/=10 )  // O(log(N)
   {
     frec[M%10]+=1;
     int d;
     for (sum=d=0 ; d<10 ;d++ )  // O(1)
{
 pow[d]*=d;
 sum+=pow[d]*frec[d];
}
   }
 //  cout <<"trace " << N << " " << sum << endl;
   
 return sum==N;

}

int main (int argc, char *args[])
{
 unsigned long long N;
 for( ; cin >> N ; )
   cout << narcisist(N) << endl;
 return 0;
}


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

Código [Seleccionar] Expandir

g++ narcisista.cc -o main && ./main
1634
1
153
1
154
0

[hacksilver]

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.