Фильтрованная-Накапливать


Поставлены следующие задачи:

Упражнения 1.33

Вы можете получить даже более общая версия накапливать (упражнение 1.32) путем введения понятие фильтр на условиях, которые будут в сочетании. То есть, объединить только те термины, производные от значений в диапазоне которые удовлетворяют заданному условию. Полученный отфильтрованный-накапливать абстракция принимает те же аргументы как накопить вместе с дополнительный предикат одного аргумента что указывает фильтра. Писать фильтрованная-накопить как процедура. Покажите, как выразить следующим используя фильтрованную-накапливаются:

а. сумма квадратов премьер чисел в интервале от A до B (при условии, что у вас Прайм? уже сказуемого написано)

б. произведение всех положительных числа меньше N, которые относительно простых с N (т. е. все положительных чисел я < N такое, что НОД(я,н) = 1).

Я написал этот код:

(Служебные функции)

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (square x) (* x x))
(define (divisible? b a) (= (remainder b a) 0))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (define (next x)
    (if (= x 2) 3 (+ x 2)))
  (cond ((> (square test-divisor) n) n)
        ((divisible? n test-divisor) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (prime? x) (= (smallest-divisor x) x))

(define (inc x) (+ x 1))
(define (identity x) x)

Рекурсивно:

(define (filtered-accumulate combiner filter null-value term a next b)
  (if (> a b)
      null-value
      (combiner (if (filter a) (term a) null-value)
                (filtered-accumulate combiner
                                     filter
                                     null-value 
                                     term 
                                     (next a) 
                                     next 
                                     b)   
                )))

Итерационный:

(define (i-filtered-accumulate combiner filter null-value term a next b)
  (define (iter a result)
    (if (> a b) 
        result
        (iter (next a) (combiner result (if (filter a) (term a) null-value)))))
  (iter a null-value))

Сумма простых чисел между А и Б:

(define (sum-of-primes-between a b) (filtered-accumulate + prime? 0 identity a inc b))

Продукт относительно простых чисел меньше, чем н:

(define (product-of-relative-primes-less-than n)
  (define (relprime-n i) (= (gcd i n) 1))
  (filtered-accumulate * relprime-n 1 identity 1 inc n))

Что вы думаете?



2028
1
задан 30 марта 2011 в 05:03 Источник Поделиться
Комментарии
3 ответа

Поскольку ты рекурсией только на себя и, возможно, в результате, вы можете использовать внутренние определения , что только изменения этих аргументов.

Когда элемент соответствует условию фильтра, вы можете игнорировать его рекурсией по остальным пунктам. Вам нужно не дать ему нулевое значение результата. Воедино эти идеи, мы получаем:

(define (filtered-accumulate combiner filter? null-value term a next b)
(define (rec a)
(cond
((> a b) null-value)
((filter? a) (combiner (term a) (rec (next a))))
(else (rec (next a)))))
(rec a))

(define (i-filtered-accumulate combiner filter? null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (if (filter? a) (combiner (term a) result) result))))
(iter a null-value))

Проблема запрашивает сумму квадратов простых чисел, так как (внимание, отрицается фильтр):

(define (sum-of-square-of-primes-between a b)
(i-filtered-accumulate + prime? 0 square a inc b))

Вы можете проверить для относительно простых чисел, начиная с 2:

(define (product-of-relative-primes-less-than n)
(define (relative-prime-n? i) (= (gcd i n) 1))
(i-filtered-accumulate * relative-prime-n? 1 identity 2 inc n))

1
ответ дан 31 марта 2011 в 07:03 Источник Поделиться

Есть несколько способов решения этой


  1. Написать фильтр-накапливать функция, как вы работаете

  2. Есть отдельный фильтр и накапливать функций и сочиняют их (фильтр первый)

  3. Просто используйте накапливать и работать фильтрацию в вашем совместить функции (лечить термин как элемент идентичности, когда условия не выполнены). Рассмотрим 'автоматизации' это функция, которая принимает фильтра и совмещать функции и ставит их вместе.

пример третий метод (в)

(accumulate (lambda (x y) (if (prime? b)
(a)
(+ a (square b))))
(range A B)
0)

1
ответ дан 1 апреля 2011 в 12:04 Источник Поделиться

'Накапливаются' обычно называют 'foldl'. Итак, ваша функция просто

foldl f v $ filter g xs

в Haskell. Кроме того, ваш алгоритм очень inefficent. Если бы я был, чтобы найти простые числа, я бы решето с простых делителей ниже квадратного корня из текущего числа. Вот пример:

primes = (2 :) $ flip filter [3..] $ \n -> flip all (flip takeWhile primes $ \i -> i * i <= n) $ \x -> n `mod` x /= 0

main = print $ take 10 $ primes

Результат:

[2,3,5,7,11,13,17,19,23,29]

-1
ответ дан 15 апреля 2011 в 04:04 Источник Поделиться