lundi 22 mars 2010

Project Euler #4

(* Checks if int is palindrome *)
let is_palindrome n = 
  let str = string_of_int n in
  let len = String.length str in
  let rec check_char s n =
    if n == len - 1 then
      (String.get s n == String.get s 0)
    else
      (String.get s n == String.get s (len - 1 - n)) && (check_char s (n + 1))
  in
  check_char str 0;;

(* check if n is a product of two 3-digit numbers *)
let is_product n = 
  let rec check_numbers i j n =
    let rest = n mod i in
    let modulo = n / i in
    let mod_length = String.length (string_of_int modulo) in
    if i = j then
      false
    else if (rest == 0) && (mod_length == 3) then 
      begin
        Printf.printf "%d %d\n" i modulo;
        true
      end
    else
      check_numbers (i+1) j n
  in
  check_numbers 100 999 n;;

(* looks for palindromes which a products of two 3-digit numbers*)
let rec check_range n m =
  if n == m then
    -1
  else if (is_palindrome n) && (is_product n) then
    n
  else
    check_range (n-1) m;;

Printf.printf "%d\n" (check_range 998001 10000)
Изначально пытался просто переделать двойной цикл с проверкой в рекурсию, в итоге оказалось проще перебрать числа в одной рекурсии.

Aucun commentaire:

Publier un commentaire