Найти всех различных троек меньше, чем N, что сумма с


Упражнения 2.41. Написать процедуру для найти всех упорядоченных троек различных положительные числа i, j и K меньше чем или равный до заданного целого числа n что сумма данного числа s.

(define (enumerate-integers i j)
  (if (= i j)
      (list j)
      (cons i (enumerate-integers (+ i 1) j))))

(define (filter f seq)
  (if (null? seq)
      null
      (if (f (car seq)) 
          (cons (car seq) (filter f (cdr seq)))
          (filter f (cdr seq)))))

(define (remove x seq)
  (filter (if (pair? x) 
              (lambda (y) (not (member y x)))
              (lambda (y) (not (= x y)))) seq))

(define (unique-triples-less-than n)
  (let ((the-number-list (enumerate-integers 1 (- n 1))))
    (flatmap (lambda (i)
               (flatmap (lambda (j)
                          (map (lambda (k) (list i j k)) 
                               (remove (list i j) the-number-list))) 
                        (remove i the-number-list)))
             (enumerate-integers 1 (- n 1)))))

(define (flatmap f seq)
  (accumulate append null (map f seq)))

(define (accumulate op initial seq)
  (if (null? seq)
      initial
      (op (car seq) 
          (accumulate op initial (cdr seq)))))

(define (s-sum-triples-below-n n s)
  (filter (lambda (y) (= (accumulate + 0 y) s))
          (unique-triples-less-than n)))

Может ли этот код быть улучшено в любом случае?



973
8
задан 13 апреля 2011 в 07:04 Источник Поделиться
Комментарии
3 ответа

Ваш уникальный-тройки-меньше-чем-н является излишне сложным, потому что вы можете сделать это рекурсивно. Ответ С. Кучеренко пытается добиться этого, но тоже чрезвычайно сложные.
Простой рекурсивной формулировкой здесь, но это предполагает, что перечислять-целых чисел возвращает пустой список, если позвонил со значениями от>.

 (define (unique-tuples m from to)
(if (= n 0) '(())) ; one empty tuple
(flatmap (lambda (n)
(map (lambda (t) (cons n t))
(unique-tuples (- m 1) (+ n 1) to)))
(enumerate-integers from to))))

Это разворачивается как рекурсивных вызовов, например, такой:

 (u-t 3 1 4) = (flatmap ... '(1 2 3 4))
= (flatten '(,(map (lambda (t) (cons 1 t))
(u-t 2 2 4))
,(map (lambda (t) (cons 2 t)) ;; X
(u-t 2 3 4))
,(map (lambda (t) (cons 2 t))
(u-t 2 4 4))
,(map (lambda (t) (cons 2 t))
(u-t 2 5 4))))

и например, если вы посмотрите на линии, отмеченные х, это нужно рекурсивно (уникальные кортежи 2 3 4), т. е. 2-кортежей, чье число находится между 3 и 4, поэтому список '((3 4)), а потом для каждого элемента этого списка, добавим 2 в начале, так и карту возвращает '((2 3 4)).

Тогда просто

(define (unique-triples n) (unique-tuples 3 1 n))

Результаты должны быть отфильтрованы на сумму.

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

Этот вариант подходит?

#lang racket
(define (filtered-by-sum-triples s n)
(filter (sum-equal? s)
(unique-triples n)))

(define (unique-triples n)
(unique-sequences n 3))

(define (unique-sequences n arity)
(define (rec num arity tail)
(if (= arity 1)
(map (lambda (x) (cons x tail))
(enumerate-interval 1 num))
(flatmap (lambda (x) (rec (sub1 x) (sub1 arity) (cons x tail)))
(enumerate-interval 1 num))))
(rec n arity null))

(define (sum-equal? s)
(lambda (sequence)
(= (foldr + 0 sequence) s)))

(define (flatmap proc sequence) (foldr append null (map proc sequence)))

(define (enumerate-interval low high)
(if (> low high)
null
(cons low (enumerate-interval (add1 low) high))))

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

Как я понимаю, упражнение попросил заказать троек, что означает:

(i, j, k) foreach 0 < i <= j <= k <= n

Таким образом, вы можете использовать уникальный пар процедуры,определенные в предыдущем упражнении, чтобы придумать что-то простое, вроде этого:

(flatmap
(lambda (a)
(map (lambda (b) (cons a b))
(unique-pairs (- a 1))))
(enumerate-interval 1 n))

Если вы не хотите изменить ваш код, вы всегда можете фильтр результатов, которые не заказывали, но это просто трата процессорных циклов.

Кроме этого, такие процедуры, как фильтр или удалить несколько встроенных процедур в схеме переводчик я использую (МИТ/ГНУ схема). Я не знаю, если они являются частью стандарта, но в любом случае я не чувствую, что вы должны пересмотреть их всякий раз, когда вы размещаете решение упражнений :)

1
ответ дан 12 мая 2012 в 10:05 Источник Поделиться