9 de noviembre de 2013

Largest palindrome product - Project Euler, problema 4

El problema es el siguiente:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers. 

Para saltar a lo interesante, programemos primero la función esP(n) que nos dirá si el n es palíndromo (capicúa).

function r=reverse(n)
 r=0;
 while n>1
  r=10*r+mod(n,10);
  n=floor(n/10);
 end
end
function t=esP(n)
 t= (n==reverse(n));
end

Sean $a,b \in  [100,999]$ enteros, hay que encontrar el producto a*b máximo que sea capicúa. Lo conveniente es "recorrer" los valores de a y b empezando con los valores mas altos por obvias razones.

pal=0;
a=999;
m=1;
while a>=100
 b=999;
 while b>a
  if pal>= a*b
   break;
  end
  if esP(a*b)
   pal=a*b;
  end
  b-=1;
 end
 a-=1;
end
pal


Nota:
  if pal>= a*b
   break;
  end


Es para evitar operaciones, ya que si a*b es menor que el último capicúa calculado, también lo serán los siguientes ya que en cada ciclo se reduce b.