如何在计划中找到友好的配对？
如何在计划中找到友好的配对？
提问于 2014-05-17 09:33:39
我是新计划的。如何找到“和睦相处”？
(define (SumCD n)
(define s 1 )
(set! m (quotient n 2))
(while (<= i m)
(if (=(modulo n i) 0)
(set! s (+ s i)))
(set! i (+ i 1))
)
)在主程序中，我想检查(if (m=SumCD n)和(n=SumCD m))，那么m和n是友好的对。我该怎么做？
回答 3
Stack Overflow用户
回答已采纳
发布于 2014-05-17 12:14:03
过度使用set!意味着一种命令式的编程风格，通常在Scheme中是不允许的。下面是一个与sum-of-divisors相关的实现，它根本不使用set!。
(define (sum-of-divisors n)
(define-values (q r) (integer-sqrt/remainder n))
(for/fold ((sum (if (and (zero? r) (> q 1)) (add1 q) 1)))
((i (in-range 2 q))
#:when (zero? (modulo n i)))
(+ sum i (quotient n i))))标准R6RS/R7RS方案中的等效版本，如果您不使用Racket：
(define (sum-of-divisors n)
(define-values (q r) (exact-integer-sqrt n))
(let loop ((sum (if (and (zero? r) (> q 1)) (+ q 1) 1))
(i 2))
(cond ((>= i q) sum)
((zero? (modulo n i))
(loop (+ sum i (quotient n i)) (+ i 1)))
(else (loop sum (+ i 1))))))请注意，这与您所拥有的set!-based版本并不等同。这段代码实际上所做的是创建一个内部函数loop，它每次使用新的参数进行尾调用。
现在，我们可以相应地定义amicable?和perfect?：
(define (amicable? n)
(define sum (sum-of-divisors n))
(and (not (= n sum))
(= n (sum-of-divisors sum))))
(define (perfect? n)
(= n (sum-of-divisors n)))如果你真的想测试两个数字，看看它们是否是友好的一对，你可以这样做：
(define (amicable-pair? a b)
(and (not (= a b))
(= a (sum-of-divisors b))
(= b (sum-of-divisors a))))更新OP关于如何使用它在m和n之间找到友好对的新问题。首先，让我们定义一个amicable?的变体，它返回一个数字的友好的“对等点”：
(define (amicable-peer n)
(define sum (sum-of-divisors n))
(and (not (= n sum))
(= n (sum-of-divisors sum))
sum))如果你用的是球拍，用这个：
(define (amicable-pairs-between m n)
(for*/list ((i (in-range m (add1 n)))
(peer (in-value (amicable-peer i)))
#:when (and peer (<= m peer n) (< i peer)))
(cons i peer)))如果你不使用球拍，用这个：
(define (amicable-pairs-between m n)
(let loop ((result '())
(i n))
(if (< i m)
result
(let ((peer (amicable-peer i)))
(if (and peer (<= m peer n) (< i peer))
(loop (cons (cons i peer) result) (- i 1))
(loop result (- i 1)))))))因为列表是从右到左构建的，所以我决定从n向下数到m，只保留一个友好的对等点，以及对等点在范围内的数字。(< i peer)检查是为了确保友好对只出现在结果中一次。
示例：
> (amicable-pairs-between 0 10000)
((220 . 284) (1184 . 1210) (2620 . 2924) (5020 . 5564) (6232 . 6368))更多的OP更新(他问递归版本和累积版本之间的区别是什么)。我上面写的amicable-pairs-between版本是累积的。递归版本如下所示：
(define (amicable-pairs-between m n)
(let recur ((i m))
(if (> i n)
'()
(let ((peer (amicable-peer i)))
(if (and peer (<= m peer n) (< i peer))
(cons (cons i peer) (recur (+ i 1)))
(recur (+ i 1)))))))注意，这次没有result累加器。然而，它不再是尾递归了。
Stack Overflow用户
发布于 2014-05-18 22:37:28
你的程序不工作:我从来没有初始化。而且它的风格很差；适当的Scheme程序很少使用while或set!。让我们回到起点。
一个完全数等于它的适当除数之和；例如，28的除数是1，2，4，7和14，1+2+4+7+ 14 = 28，所以28是一个完全数。如果m的除数之和等于n，n的除数之和等于m；例如，220有除数1，2，4，5，10，11，20，22，44，55,110，等于284,284有除数1，2，4，71,142，因此，220和284是友好的一对。
计算数字n的除数的一种简单方法是尝试从1到⌊n/2⌋的每一个整数，看看它是否除以n。
(define (divisors n)
(let loop ((i 1) (ds (list)))
(cond ((< n (+ i i)) (reverse ds))
((zero? (modulo n i))
(loop (+ i 1) (cons i ds)))
(else (loop (+ i 1) ds)))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)请注意，我们将n排除在n的除数列表之外；这是我们在计算友好对时所希望的，但在某些情况下，您可能希望将n添加到n的除数列表中。与其列出除数列表，我们还可以计算它们的和：
(define (sum-div n)
(let loop ((i 1) (s 0))
(cond ((< n (+ i i)) s)
((zero? (modulo n i))
(loop (+ i 1) (+ s i)))
(else (loop (+ i 1) s)))))
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55与其数到⌊n/2⌋，更快的是注意到除数是成对出现的，所以只需要数到n的平方根；当n是一个完美的正方形时，要在和中精确地包含平方根的一个实例时要小心：
(define (divisors n)
(let loop ((i 2) (ds (list 1)))
(cond ((<= n (* i i))
(sort < (if (= n (* i i)) (cons i ds) ds)))
((zero? (modulo n i))
(loop (+ i 1) (cons i (cons (/ n i) ds))))
(else (loop (+ i 1) ds)))))
(define (sum-div n)
(let loop ((i 2) (s 1))
(cond ((<= n (* i i))
(if (= n (* i i)) (+ i s) s))
((zero? (modulo n i))
(loop (+ i 1) (+ s i (/ n i))))
(else (loop (+ i 1) s)))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55如果您知道n的素因式分解，那么很容易找到n的除数:只需取n因子的powerset成员的乘积，就可以消除重复。
(define (but-last xs)
(if (null? xs) (error 'but-last "empty list")
(reverse (cdr (reverse xs)))))
(define (unique eql? xs)
(cond ((null? xs) '())
((null? (cdr xs)) xs)
((eql? (car xs) (cadr xs)) (unique eql? (cdr xs)))
(else (cons (car xs) (unique eql? (cdr xs))))))
(define (power-set xs)
(if (null? xs) (list (list))
(let ((rest (power-set (cdr xs))))
(append (map (lambda (x) (cons (car xs) x)) rest) rest))))
(define (divisors n)
(but-last (unique = (sort <
(map (lambda (xs) (apply * xs))
(power-set (factors n)))))))
> (divisors 220)
(1 2 4 5 10 11 20 22 44 55 110)
> (divisors 284)
(1 2 4 71 142)
> (divisors 36)
(1 2 3 4 6 9 12 18)如果你知道n的素因式分解，通过考察n的因子的多重性，就更容易找到n的除数之和。
(define (sum-div n)
(define (div f x) (/ (- (expt f (+ x 1)) 1) (- f 1)))
(let ((fs (factors n)))
(let loop ((f (car fs)) (fs (cdr fs)) (x 1) (s 1))
(cond ((null? fs) (- (* s (div f x)) n))
((= (car fs) f) (loop f (cdr fs) (+ x 1) s))
(else (loop (car fs) (cdr fs) 1 (* s (div f x))))))))
> (sum-div 220)
284
> (sum-div 284)
220
> (sum-div 36)
55一个简单的方法来找出一个数n的因子使用素数轮；如果n是一个大素数或半素数，这是缓慢的，但在其他情况下是合理的：
(define (factors n)
(define (last-pair xs) (if (null? (cdr xs)) xs (last-pair (cdr xs))))
(define (cycle . xs) (set-cdr! (last-pair xs) xs) xs)
(let ((wheel (cons 1 (cons 2 (cons 2 (cycle 4 2 4 2 4 6 2 6))))))
(let loop ((n (abs n)) (f 2) (wheel wheel) (fs (list)))
(cond ((< n (* f f)) (if (= n 1) fs (reverse (cons n fs))))
((zero? (modulo n f)) (loop (/ n f) f wheel (cons f fs)))
(else (loop n (+ f (car wheel)) (cdr wheel) fs))))))在所有这些情况下，很容易确定一个数字n是否是完美的，或者它是否是友好对的一部分：
(define (perfect? n)
(= n (sum-div n)))
(define (amicable? n)
(let ((s (sum-div n)))
(and (< 1 s) (= (sum-div s) n))))
> (perfect? 6)
#t
> (perfect? 28)
#t
> (amicable? 220)
#t
> (amicable? 284)
#t也很容易找到完美的数字和友好的对小于某些限制：
(define (perfect limit)
(let loop ((n 2) (ps (list)))
(cond ((< limit n) (reverse ps))
((= n (sum-div n))
(loop (+ n 1) (cons n ps)))
(else (loop (+ n 1) ps)))))
(define (amicable limit)
(let loop ((n 2) (as (list)))
(if (< limit n) (reverse as)
(let ((s (sum-div n)))
(if (and (< n s) (= n (sum-div s)))
(loop (+ n 1) (cons (list n s) as))
(loop (+ n 1) as))))))
> (perfect 10000)
(6 28 496 8128)
> (amicable 10000)
((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368))与其将每个数分解到一个极限，更快的方法是通过筛选，找到所有数的除数之和，从1到极限，每一项初始化为1。然后，对于每个i从2到1，将i添加到i的每个倍数中。
(define (make-sum-divs n)
(let ((s (make-vector (+ n 1) 0)))
(do ((i 1 (+ i 1))) ((< n i) s)
(do ((j (+ i i) (+ j i))) ((< n j))
(vector-set! s j (+ i (vector-ref s j)))))))
(define max-sum-div 1000)
(define sum-divs (make-sum-divs max-sum-div))给定筛子，很容易找到完美的数字和友好的配对：
(define (perfect limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (ps (list)))
(cond ((< limit n) (reverse ps))
((= n (vector-ref sum-divs n))
(loop (+ n 1) (cons n ps)))
(else (loop (+ n 1) ps)))))
(define (pairs limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (as (list)))
(if (< limit n) (reverse as)
(let ((s (vector-ref sum-divs n)))
(if (and (< s max-sum-div) (< n s)
(= n (vector-ref sum-divs s)))
(loop (+ n 1) (cons (list n s) as))
(loop (+ n 1) as))))))
> (perfect 1000000)
(6 28 496 8128)
> (pairs 1000000)
((220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368)
(10744 10856) (12285 14595) (17296 18416) (63020 76084)
(66928 66992) (67095 71145) (69615 87633) (79750 88730)
(100485 124155) (122265 139815) (122368 123152)
(141664 153176) (142310 168730) (171856 176336)
(176272 180848) (185368 203432) (196724 202444)
(280540 365084) (308620 389924) (319550 430402)
(356408 399592) (437456 455344) (469028 486178)
(503056 514736) (522405 525915) (600392 669688)
(609928 686072) (624184 691256) (635624 712216)
(643336 652664) (667964 783556) (726104 796696)
(802725 863835) (879712 901424) (898216 980984))筛分法比其他两种方法都快得多。在我的电脑上，用试除法来计算不到一百万的友好对需要十二秒，而保理法的计算时间也差不多，但是只需要大约一秒半的时间把除数筛成一百万，再用半秒来找到友好的对，总共要两秒。
除了友好的一对，还有友好的链条，在两个以上的项目后，循环回到开始。例如，数字12496、14288、15472、14536和14264形成了长度为5的友好链，因为sum-div( 12496 ) = 14288，sum-div(14288) = 15472，sum-div(15472) = 14536，sum-div(14536) = 14264，sum-div(14264) =12496。寻找友好链的程序是该程序的一个变体，用于寻找友好的配对：
(define (chain n limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((s (vector-ref sum-divs n)) (cs (list n)))
(cond ((= s n) (reverse cs))
((not (< n s limit)) (list))
((member s cs) (list))
(else (loop (vector-ref sum-divs s) (cons s cs))))))
(define (chains limit)
(when (< max-sum-div limit)
(set! max-sum-div limit)
(set! sum-divs (make-sum-divs max-sum-div)))
(let loop ((n 2) (cs (list)))
(if (< limit n) (reverse cs)
(let ((c (chain n limit)))
(if (null? c) (loop (+ n 1) cs)
(loop (+ n 1) (cons c cs)))))))
> (sort (lambda (a b) (< (length a) (length b))) (chains 1000000))
((6) (28) (496) (8128) (220 284) (1184 1210) (2620 2924)
(5020 5564) (6232 6368) (10744 10856) (12285 14595)
(17296 18416) (63020 76084) (66928 66992) (67095 71145)
(69615 87633) (79750 88730) (100485 124155) (122265 139815)
(122368 123152) (141664 153176) (142310 168730)
(171856 176336) (176272 180848) (185368 203432)
(196724 202444) (280540 365084) (308620 389924)
(319550 430402) (356408 399592) (437456 455344)
(469028 486178) (503056 514736) (522405 525915)
(600392 669688) (609928 686072) (624184 691256)
(635624 712216) (643336 652664) (667964 783556)
(726104 796696) (802725 863835) (879712 901424)
(898216 980984) (12496 14288 15472 14536 14264)
(14316 19116 31704 47616 83328 177792 295488 629072 589786
294896 358336 418904 366556 274924 275444 243760 376736
381028 285778 152990 122410 97946 48976 45946 22976 22744
19916 17716))四个十全十美的数字构成了长度1的友好链，有40对友好对，上面有一条长度为5的友好链，并注意到从14316开始的壮观的长度为28的友好链。
Stack Overflow用户
发布于 2014-05-18 07:36:32
我只是想在M和N之间找到友好的配对
(define (find-amicable-pairs M N)
(< M N)
(define i M)
(define a 0)
(do ()
[(= i N)]
(set! a (sum-of-divisors i))
(if (and(= i (sum-of-divisors a)) (< i a))
(and (display i)
(display " and ")
(display a)
(newline))
#f)
(set! i (+ i 1))))谢谢你在这方面的想法！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23709772
复制相关文章
相似问题
腾讯云开发者
