#lang racket ; Estes são alguns exemplos feitos em sala de aula. ; A maioria dos exemplos não faz tratamento de erro dos parâmetros, ; assim, fica mais claro a excência da função. (require rackunit) ; Funções para auxiliar nos testes (define => 'arrow) (define (fact result arrow expected) (unless (equal? arrow =>) (fail "O segundo deve ser =>")) (check-equal? result expected)) ; Cria um stream com os números no intervalo [i, f) (define (intervalo i f) (if (i . >= . f) empty-stream (stream-cons i (intervalo (add1 i) f)))) (fact (stream->list (intervalo 1 4)) => '(1 2 3)) ; Soma os elementos de um stream (define (stream-sum stream) (stream-fold + 0 stream)) (fact (stream-sum (intervalo 1 11)) => 55) ; Cria um stream com os números n, n+1, n+2, ... (define (inteiros-a-partir n) (stream-cons n (inteiros-a-partir (add1 n)))) ; Definição de um stream dos números naturais (define naturais (inteiros-a-partir 1)) ; Cria um stream que pega os n primeiros elementos de outro stream (define (stream-take stream n) (if (zero? n) empty-stream (stream-cons (stream-first stream) (stream-take (stream-rest stream) (sub1 n))))) (fact (stream->list (stream-take naturais 5)) => '(1 2 3 4 5)) ; Stream com os números de fibonacci (define (fibgen a b) (stream-cons a (fibgen b (+ a b)))) (fact (stream->list (stream-take (fibgen 0 1) 10)) => '(0 1 1 2 3 5 8 13 21 34)) ;; Definição implícita de streams ; Stream de uns (define uns (stream-cons 1 uns)) (fact (stream->list (stream-take uns 5)) => '(1 1 1 1 1)) ; Cria um stream somando os valores de dois outros streams (define (stream-add s1 s2) (if (or (stream-empty? s1) (stream-empty? s2)) empty-stream (stream-cons (+ (stream-first s1) (stream-first s2)) (stream-add (stream-rest s1) (stream-rest s2))))) ; Stream dos inteiros (define inteiros (stream-cons 0 (stream-add uns inteiros))) (fact (stream->list (stream-take inteiros 5)) => '(0 1 2 3 4)) ; Stream dos números de fibonacci (define fibs (stream-cons 0 (stream-cons 1 (stream-add fibs (stream-rest fibs))))) (fact (stream->list (stream-take fibs 10)) => '(0 1 1 2 3 5 8 13 21 34)) ; Problema 1 - Multiples of 3 and 5 - Project Euler (projecteuler.net) ; If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. ; Find the sum of all the multiples of 3 or 5 below 1000. ; Função que retorna uma função de um parâmetro n que testa se ; n é múltiplo de algum dos divisores (define (divide? d n) (zero? (remainder n d))) (define (multiplo-de-algum . divisores) (λ (n) (ormap (λ (d) (d . divide? . n)) divisores))) (fact ((multiplo-de-algum 3 5) 12) => #t) (fact ((multiplo-de-algum 3 5) 15) => #t) (fact ((multiplo-de-algum 3 5) 20) => #t) (fact ((multiplo-de-algum 3 5) 22) => #f) (define (problem1 n) (stream-sum (stream-filter (multiplo-de-algum 3 5) (intervalo 1 n)))) (fact (problem1 10) => 23) (printf "Resposta problema 1: ~a\n" (problem1 1000)) ; Problem 2 - Even Fibonacci numbers ; Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: ; 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... ; By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. (define (stream-take-while pred? stream) (if (or (stream-empty? stream) (not (pred? (stream-first stream)))) empty-stream (stream-cons (stream-first stream) (stream-take-while pred? (stream-rest stream))))) (define (problem2 limit) (stream-sum (stream-take-while (λ(n) (n . <= . limit)) (stream-filter even? fibs)))) (fact (problem2 40) => 44) (printf "Resposta problema 2: ~a\n" (problem2 4000000)) ; Observação: A estratégia de usar stream não é a mais adequada ; para todos os problemas do projecteuler, mas para alguns problemas ; ela é bastante adequada.