jeudi 25 mars 2010

Project Euler #20

#load "nums.cma";;

open Big_int;;

let rec factorial n =
if eq_big_int n unit_big_int then
unit_big_int
else
mult_big_int n (factorial (pred_big_int n));;

let int_list_of_string s =
let len = String.length s in
let rec chars_of_string s n =
if n == 0 then
[int_of_char s.[0] - int_of_char '0']
else
(chars_of_string s (n - 1)) @ [(int_of_char s.[n]) - int_of_char '0']
in
chars_of_string s (len - 1);;

Printf.printf "%d\n"
(List.fold_left
(+)
0
(int_list_of_string
(string_of_big_int
(factorial
(big_int_of_int 100)))));;


mardi 23 mars 2010

Project Euler #6

#load "nums.cma"

open Big_int;;

let rec sum_of_squares n =
if eq_big_int n unit_big_int then
unit_big_int
else
add_big_int (square_big_int n) (sum_of_squares (pred_big_int n));;

let square_of_sum n =
let rec sum n =
if eq_big_int n unit_big_int then
unit_big_int
else
in
square_big_int (sum n);;

let s1 = sum_of_squares (big_int_of_int 100);;
let s2 = square_of_sum (big_int_of_int 100);;

let result = sub_big_int s2 s1;;

Printf.printf "%s\n" (string_of_big_int result);;


Сначала написал с использованием встроенных int, перепутал местами суммы при вычитании, получил отрицательный результат, подумал, что проблема с переполнением int, переписал при помощи Big_int, после чего и обнаружил, что перепутал суммы местами.

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)

Изначально пытался просто переделать двойной цикл с проверкой в рекурсию, в итоге оказалось проще перебрать числа в одной рекурсии.

lundi 1 mars 2010

Project Euler #3

#load "nums.cma"

open Big_int;;

let num = big_int_of_string "600851475143";;

let solution n =
let rec factorize m p =
if ge_big_int p m then
Printf.printf "%s\n" (string_of_big_int m)
else
if eq_big_int (mod_big_int m p) zero_big_int then
factorize (div_big_int m p) (big_int_of_int 2)
else
factorize m (succ_big_int p)
in
factorize n (big_int_of_int 2);;

solution num;;


Решение вида "а давайте-ка найдем все простые числа до sqrt(N), а потом найдем максимальное, которое разделит N без остатка", что прокатило для C++, в Ocaml оказалось неосуществимо в разумные сроки ;)

Project Euler #2

#load "nums.cma";;
open Big_int;;

let rec fib a b = function
| 0 -> a
| 1 -> b
| n when n > 1 -> fib b (add_big_int a b) (n - 1)
| _ -> raise (Invalid_argument "");;

let rec fib_range n =
let fn = fib zero_big_int unit_big_int n in
if lt_big_int fn (big_int_of_string "4000000") then
if eq_big_int
(mod_big_int fn (big_int_of_int 2))
zero_big_int then
fn :: (fib_range (n + 1))
else
zero_big_int :: fib_range (n + 1)
else
[];;

Printf.printf "%s\n" (string_of_big_int

let rec range n m = if n > m then [] else n :: range (n + 1) m;;