欧拉项目第28题.
https://projecteuler.net/problem=28
#lang racket
;give a n
;output the outermost diagonal numbers of the n x n spiral form
(define (outermost n)
(if (= n 1)
(list 1)
(build-list 4 (λ(x)
(+ (* (sub1 n)(add1 x))
(sqr(- n 2)))))))
(define (build-diagonal n)
(define (iter i r)
(if (> i n)
r
(iter (+ 2 i)
(append r (outermost i)))))
(iter 1 '()))
(display (apply + (build-diagonal 1001)))
欧拉项目第12题.
https://projecteuler.net/problem=12
计算一个自然数的因子个数,用到了这里
racket...
#lang racket
(define (triangle x)
(quotient (* x (add1 x)) 2))
(define (prime-factors n)
(let loop ([n n] [m 2] [factors (list)])
(cond [(= n 1) factors]
[(= 0 (modulo n m)) (loop (/ n m) 2 (cons m factors))]
[else (loop n (add1 m) factors)])))
;;cont n in l
(define (count-n l n)
(cons n (count (lambda (x) (= n x)) l)))
;;count all n in l
(define (count-all l)
(let loop ([l l] [visited '()] [r '()])
(cond
[(null? l) r]
[(member (car l) visited) (loop (cdr l) visited r)]
[else (loop (cdr l)
(cons (car l) visited)
(cons (count-n l (car l)) r))])))
;;count all divisors of a number
;more in http://bit.ly/WLfeZN
(define (count-factor n)
(let loop ([l (count-all(prime-factors n))] [r 1])
(cond
[(null? l) (cons r n)]
[else (loop (cdr l) (* r (add1(cdar l))))])))
(define (tri-count-factor n)
(count-factor (triangle n)))
(time(car(filter (lambda (x) (< 500 (car x)))
(map tri-count-factor (range 10000 20000)))))
欧拉项目第14题.
https://projecteuler.net/problem=14
racekt.. 大概9秒.
#lang racket
(require racket/trace)
(define (col x)
(cond
[(> 0 x)x]
[(even? x) (/ x 2)]
[else (add1(* 3 x))]))
(define (gene-col x ht)
(cond
[(number? (hash-ref ht x null)) (hash-ref ht x)]
[(= 1 x) (begin(hash-set! ht x 1)(hash-ref ht x))]
[else (begin(hash-set! ht x (add1 (gene-col (col x) ht)))
(hash-ref ht x))]))
;;alop is a list of pairs
(define (find-cdr alop h)
(if(= h (cdr(car alop)))
(car alop)
(find-cdr (cdr alop) h)))
(define ht (make-hash))
(define answers(map (lambda (x) (gene-col x ht))(build-list 1000000 (lambda (x) (add1 x)))))
(find-cdr (hash->list ht) (apply max answers))
尾递归改写为递归
做备忘用.
上代码
#lang racket
;;factorial
;;non-tail recursion
(define (fact1 n)
(if (= 0 n)
1
(* n (fact1 (- n 1)))))
;;factorial
;;tail recursion
(define (fact-aux n result)
(if (= 0 n)
result
(fact-aux (- n 1)(* n result))))
(define (fact2 n)
(fact-aux n 1))
(define (fact3 n)
(let fact-aux ([s n][result 1])
(if (= 0 s)
result
(fact-aux (- s 1)(* s result)))))
;;fibonacci
;;non-tail recursion
(define (fib1 n)
(if (< n 2)
n
(+ (fib1 (- n 1))(fib1 (- n 2)))))
;;fibonacci
;; tail recursion
(define (fib-aux n next result)
(if (= n 0)
result
(fib-aux (- n 1) (+ next result) next)))
(define (fib2 n)
(fib-aux n 1 0))
(define (fib3 n)
(define (fib-aux n next result)
(if (= 0 n)
result
(fib-aux (- n 1) (+ next result) next)))
(fib-aux n 1 0))
when converting recursive functions to tail recursive funcion.add a auxiliary parameter.
ps. python 没有尾递归优化.
lisp系有.解释器自动将尾递归转化为迭代.
参考:
http://www.csee.umbc.edu/~chang/cs202.f98/readings/recursion.html
