Problem 1 ver. 1: brute-force solution
Let us start with solutions to Project Euler problems. I will always start with brute-force solutions if those are possible and later on post optimized solutions. Every solution will be given in Scheme (R6RS) along with quick estimate of complexity. The reason for solving those problems is training myself in Scheme and, of course, fun.
Find the sum of all the multiples of 3 or 5 below 1000.
Solution:
-
#!r6rs
-
(import (rnrs))
-
-
(define n 1000)
-
-
(define (divides? n x) (= (mod n x) 0))
-
-
(define (divided-by-3-or-5? n) (or (divides? n 3) (divides? n 5)))
-
-
(define (add-dividends n sum) (if (< n 1) sum (add-dividends (- n 1) (if (divided-by-3-or-5? n) (+ sum n) sum))))
-
-
(display (add-dividends (- n 1) 0))
This is the simplest straightforward approach. Backward-recursion is used, with tail-recursion optimization, which is obligatory for all Scheme implementations, will be transformed into iteration. Backward direction is to simplify a function signature (otherwise an extra parameter is needed).
The complexity is O(n), assuming the (mod) operation is atomic. More strictly, the number of operations is 2*n. By the way, in R5RS (mod) is called (remainder).