在涉及毕达哥拉斯三元组和集合的算法中找不到我的错误

Question

null

我用我在这里找到的公式来生成三元组，从而生成周长。我更喜欢用附加系数“k”的公式，因为文章说，

尽管产生了所有的原语三元组，欧几里德公式并不产生所有的三元组--例如，(9，12，15)不能使用整数m和n产生。这可以通过在公式中插入一个额外的参数k来弥补。

为了在合理的时间内解决这个问题，我需要对嵌套循环中的参数进行合理的限制。我设置了“k”和“m”的限制，您将在后面的完整代码中看到，这两个小函数的帮助是：

(defun m-limit (m)
  (if (> (make-peri m 1 1) 1500000)
      m
      (m-limit (1+ m))))

(defun k-limit (k)
  (if (> (make-peri 2 1 k) 1500000)
      k
      (k-limit (1+ k))))

b=2*k*m*n；

c=k*(m*m+n*n)；

k*(m^2-n^2+2mn+m^2+n^2)<=1500000

nLimit = 1500000 / (2 * k * m) - m;

package euler75v6;

import java.util.HashSet;

/**
 *
 * @author hoyortsetseg
 */
public class Euler75v6 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        HashSet<Long> peris = new HashSet<>();
        HashSet<Long> duplicatePeris = new HashSet<>();
        peris = periList(865,125000, duplicatePeris);
        System.out.println("Number of all perimeters: " + peris.size());
        System.out.println("Number of duplicate perimeters: " + duplicatePeris.size());
        System.out.println("Number of all perimeters minus number "
                + "of duplicate perimeters: " + (peris.size() - duplicatePeris.size()));
        peris.removeAll(duplicatePeris);
        System.out.println("Same difference, just to confirm. After 'removeAll': " + peris.size());
    }
    private static Long makePeri (long m, long n, long k){
        //Long a, b, c, res;
        //a = k * (m * m - n * n);
        //b = 2 * k * m * n;
        //c = k * (m * m + n * n);
        return 2 * k * (m * m  + m * n);
    }

    private static HashSet<Long> periList (long x, long z, HashSet<Long> dupList){
            HashSet<Long> res = new HashSet<>();
            Long temp, nLimit;
            Long limit = Long.valueOf("1500000");
            for (long k = 1; k <= z; k++){
                for (long m = 2; m <= x; m++){
                    nLimit = 1500000 / (2 * k * m) - m;
                    for (long n = 1; ((n <= nLimit) && (n < m)); n++){
                        temp = makePeri(m,n,k);
                        if (Long.compare(temp, limit) <= 0){ // Should be redundant but just in case.
                            if (res.contains(temp)){
                                dupList.add(temp);
                            }
                            else {
                                res.add(temp);
                            }
                        }
                    }
                }
            }
            return res;
        }    
}

通用Lisp代码：

(defun make-peri (m n k)
  (* 2 k (+ (* m m) (* m n))))

(defun peri-list (m n k all-peris dupl-peris)
  (let ((n-limit (- (/ 1500000 (* 2 k m)) m)))
    (cond ((> k 125000) (- (length all-peris)
               (length (remove-duplicates dupl-peris))))
      ((> m 865) (peri-list 2 1 (1+ k) all-peris dupl-peris))
      ((or (>= n m) (> n n-limit))
       (peri-list (1+ m) 1 k all-peris dupl-peris))
      (t (let ((peri (make-peri m n k)))
           (if (> peri 1500000) ;; Redundant with m n k limits but still.
           (peri-list (1+ m) 1 k all-peris dupl-peris)
           (if (member peri all-peris)
               (peri-list m (1+ n) k all-peris (cons peri dupl-peris))
               (peri-list m (1+ n) k (cons peri all-peris)
                  dupl-peris))))))))

(defun result () (peri-list 2 1 1 nil nil))

如果你能解释我哪里弄错了，我将不胜感激。但请不要给出正确答案或代码。

编辑：

(defun make-peri (m n k)
  (* 2 k (+ (* m m) (* m n))))

(defun peri-list* (m n k limit all-peris dupl-peris)
  (let* ((n-limit (- (/ limit (* 2 k m)) m))
    (k-upper-limit (1- (k-limit 1 limit)))
    (m-upper-limit (1- (m-limit 2 limit)))
    (dupl-peris* (remove-duplicates dupl-peris))
    (difference* (set-difference all-peris dupl-peris*)))
    (cond ((> k k-upper-limit) (list (sort all-peris #'<)
                     (sort dupl-peris* #'<)
                     (sort difference* #'<)))
                    ;; (length all-peris)
                    ;; (length dupl-peris*)
                    ;; (length difference*)))
      ((> m m-upper-limit) (peri-list* 2 1 (1+ k) limit all-peris dupl-peris))
      ((or (>= n m) (> n n-limit))
       (peri-list* (1+ m) 1 k limit all-peris dupl-peris))
      (t (let ((peri (make-peri m n k)))
           (if (member peri all-peris)
           (peri-list* m (1+ n) k limit all-peris (cons peri dupl-peris))
           (peri-list* m (1+ n) k limit (cons peri all-peris) dupl-peris))))))))
(defun m-limit (m limit)
  (if (> (make-peri m 1 1) limit)
      m
      (m-limit (1+ m) limit)))

(defun k-limit (k limit)
  (if (> (make-peri 2 1 k) limit)
      k
      (k-limit (1+ k) limit)))

CL-USER> (peri-list* 2 1 1 150 nil nil)
((12 24 30 36 40 48 56 60 70 72 80 84 90 96 108 112 120 126 132 140 144 150)
 (24 48 60 72 80 84 90 96 108 112 120 132 140 144) (12 30 36 40 56 70 126 150)
 13 9 8)
CL-USER> (- 22 14)
8
CL-USER> (peri-list* 2 1 1 100 nil nil)
((12 24 30 36 40 48 56 60 70 72 80 84 90 96) (24 48 60 72 80 84 90 96)
 (12 30 36 40 56 70) 11 5 6)
CL-USER> (- 14 8)
6

之后，我注释了(length...）部分，让程序只列出列表和Mapcared#'lengte到结果：

CL-USER> (mapcar #'length (peri-list* 2 1 1 100 nil nil))
(14 8 6)

这一次，前两个长度确实与实际计数相匹配。然而，差异仍然相同；意思是我还是得到了错误的答案。

CL-USER> (mapcar #'length (peri-list 2 1 1 nil nil))
(355571 247853)
CL-USER> (- 355571 247853)
107718

这让我质疑我的基本假设。以下是我的问题。

null

（let（（peri（make-peri m n k）））（if（member peri all-peris）（peri-list*m(1+n)k limit all-peris（cons peri dupl-peris））（peri-list*m(1+n)k limit（cons peri all-peris）dupl-peris））

是什么导致了length的神秘行为？

由于我在Java和Common Lisp中都得到了相同的结果，我认为这不是我犯的特定于语言的错误。为什么peris.removeAll（duplicatePeris）；的大小不能给出只有一个三角形的周长数？我在算法或集合及其子集的差异上犯了什么基本错误吗？

我希望这有助于“解开”我的问题。

编辑#2，Java版本的更新：

我尝试使用hashmap编写解决方案的Java版本，将周界作为键，周界的频率作为值。在这里：

public static void main(String[] args) {
    HashMap<Long, Long> perisMap = new HashMap<>();
    periMap(865, 125000, perisMap);
    System.out.println("Number of all perimeters (1 triangle, many triangles): " + perisMap.size());
    Long uniqueCounter = Long.valueOf("0");
    for (Map.Entry<Long, Long> entry : perisMap.entrySet()){
        Long freq = entry.getValue();
        if (freq == 1){
            uniqueCounter++;
        }
    }
    System.out.println("Number of all perimeters in the map which appear only once: " + uniqueCounter);
}
private static Long makePeri (long m, long n, long k){
    //Long a, b, c, res;
    //a = k * (m * m - n * n);
    //b = 2 * k * m * n;
    //c = k * (m * m + n * n);
    return 2 * k * (m * m  + m * n);
}
private static void periMap (long x, long z, HashMap<Long, Long> myMap){
        Long nLimit;
        Long limit = Long.valueOf("1500000");
        for (long k = 1; k <= z; k++){
            for (long m = 2; m <= x; m++){
                nLimit = limit / (2 * k * m) - m;
                for (long n = 1; ((n <= nLimit) && (n < m)); n++){
                    Long tempKey = makePeri(m,n,k);
                    Long tempVal = myMap.get(tempKey);
                    if (Long.compare(tempKey, limit) <= 0){
                        if (myMap.containsKey(tempKey)){
                            myMap.put(tempKey, tempVal + 1);
                        }
                        else {
                            myMap.put(tempKey, Long.valueOf("1"));
                        }
                    }
                }
            }
        }
    }

Number of all perimeters (1 triangle, many triangles): 355571
Number of all perimeters in the map which appear only once: 107718

Answer 1

要用欧拉公式来解决这个问题，你必须遵循所有的规则，保证每个三元组都能准确地生成一次。否则，您将多次生成相同的三元组，并且您将跳过有效长度，因为它们的计数过高。

这些规则包括只使用(m,n)对，这些对是共素数，其中m和n不都是奇数。

我认为如果你根据这些规则添加检查以避免无效对，你的算法就会正确。至少会近得多。

LISP

跟踪生成的每个长度的最简单的方法是使用一个小整数数组。Common Lisp中的概念如下：

(defun count-triangles (limit)
  (let ((counts (make-array (1+ limit)
                  :element-type 'unsigned-byte
                  :initial-element 0))
        (result 0))
    (loop for m from 2 to (ceiling (sqrt limit)) do
      (loop for n from 1 to (1- m)
        for k1-len = (* 2 m (+ m n)) then (+ k1-len (* 2 m))
        while (<= k1-len limit)
        when (and (oddp (+ m n)) (= (gcd m n) 1))
        do (loop for len = k1-len then (+ len k1-len)
             while (<= len limit)
             do (case (aref counts len)
                  (0 (incf result)
                     (incf (aref counts len)))
                  (1 (decf result)
                     (incf (aref counts len)))))))
    result))

在编译的CLisp中，这大约需要0.5秒。下面的Java版本在我的旧MacBook上运行时间为0.014秒。

static int count() {
  byte [] count = new byte[MAX + 1];
  int result = 0;
  for (int m = 2; m < SQRT_MAX; ++m) {
    for (int n = 1; n < m; ++n) {
      if (((m ^ n) & 1) == 0 || gcd(m, n) > 1) continue;
      int base_len = 2 * m * (n + m);
      if (base_len > MAX) break;
      for (int len = base_len ; len <= MAX; len += base_len) { 
        switch (count[len]) {
        case 0:
          ++result;
          count[len] = 1;
          break;
        case 1:
          --result;
          count[len] = 2;
          break;
        default:
          break;
        }
      }
    }
  }
  return result;
}