Exponenciacion binaria y modular

Hola, estuve haciendo un par de cosas y tuve que usar un algoritmo de exponenciacion binaria y modular pero no queria que fuera recursivo asi que luego de algunos intentos, esto fue lo que consegui, espero les pueda servir de ayuda, tanto como a mi(aunque esta en java se entiende si manejas otro lenguaje :P) :

public static int expomod(int a, long b,int mod){
    int res = 1;
    while(b>0){
        if((b&1)==1)
            res=(a*res)%mod;
    b>>=1;
    a=((a%mod)*(a%mod))%mod;
    }
return res;
}

y el algoritmo en python es:

def ex(a, b,m):
     r = 1
     while(b):
             if(b&1):
                     r = (r*a)%m
             b>>=1
             a = ((a%m)*(a%m))%m
     return r

La verdad luego de ver el algoritmo recursivo, se entiende este. Lo que se hace es cambiar la recursividad a las variables, por decirlo de alguna forma. Saludos y espero sus comentarios!

Un buen tutorial donde se tratan a fondo otros algoritmos relacionados es este de topcoder.

Nota: un problema en donde se puede aplicar este algoritmo es este.

Generar particiones de un numero

Hola, a veces necesitamos generar las particiones de un numero, una partición es una forma de escribir un numero entero positivo como la suma de otros numeros enteros positivos. Por ejemplo:

Para 3, las particiones serian:
1+1+1, 2+1, 3

Ahora, podemos necesitar los numeros que conforman las particiones o simplemente cuantas particiones tiene. Para este caso, explicare como obtener el numero de particiones con programacion dinamica y modificando este algoritmo se puede obtener que numeros conforman cada una de las particiones.

La pregunta es como llegamos a que las particiones de 3, en este caso, son esas. Bien, luego de ver varios ejemplos(el 4 y el 5) si ordenamos las particiones nos daremos cuenta de algo:

Particiones hasta 5:
N. 1:
1

N. 2:
11
2

N. 3:
1 11
1 2
3

N. 4:
1 111
2 11
2 2
3 1
4

N. 5:
1 1111
2 111
2 21
3 11
3 2
4 1
5

Si nos damos cuenta, las particiones del 3 tienen a las del 2. Las del 4 tienen las del 3 y las del 2 y asi sucesivamente.

En otras palabras, podemos formar un numero de la siguiente forma(para el 4 por ejemplo):

1 + alguna forma de escribir el tres (4-1)
2 + alguna forma de escribir el dos (4-2)
3 + alguna forma de escribir el uno (4-3)
4 (solo hay una forma de escribir el numero con el mismo)

Entonces si quisieramos hacerlo para un numero y obtener todas las particiones hariamos algo como:

1+p(numero-1)
2+p(numero-2)
...
(n-1)+p(numero-(n-1)) es decir p(3) para el caso de las particiones de 4
n
p(numero) serian las particiones o el numero de particiones del numero
Y estas serian todas las particiones de n

El algoritmo para hacer esto en python seria:

numero = 5
particiones = [1] + [0] *numero
for i in xrange(1,numero+1):
    for j in xrange(i, numero+1):
        particiones[j] +=particiones[j-i]
    #print(particiones)
print(particiones[numero])

La ejecucion de este programa daria lo siguiente:
[1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 3, 3]
[1, 1, 2, 3, 4, 5]
[1, 1, 2, 3, 5, 6]
[1, 1, 2, 3, 5, 7]

y en cada iteracion sucede, tomamos un valor y anadimos las particiones del valor que falta para completar el numero.

particiones[j] = particiones que lleve + formas de hacer el valor que falta (j-i)

Podriamos modificar este algoritmo y en vez de solo sumar, agregar cada una de las particiones y asi obtendriamos los valores que conforman estas particiones

Tambien hay una formula recursiva dada por Euler para obtener las particiones de un numero.

Nota: este problema esta relacionado con un problema muy conocido que consiste en saber de cuantas formas diferentes se puede devolver una cantidad de dinero usando solo las denominaciones dadas.

Nota2: una pregunta interesante es como hacer para que en las particiones un valor no aparezca mas de una vez, sin necesidad de validar luego de haber obtenido las particiones.

Espero les sirva!