生成整数的三元组

Question

我们有3个正整数a，b和c，其中a + b + c = k，其中k是任何正整数。

是否有一个最佳的方式来遍历这三个整数的可能配置？

任何伪代码或Java代码将不胜感激。

Answer 1

没有选择，你必须通过两个嵌套循环运行：

假设0<=a,b,c和（2,1,1）是相同的三重为（1,1,2）（有permutationally当量） ，你可以添加约束a<=b<=c

for(int a=0; a<=k/3; a++) { // a <= b <= c -> 3a <= k 
    for(int b=a; b<=(k-a)/2; b++) { // b <= c -> 2b <= k-a 
     c = k-a-b; 
     //Do your thing 
    } 
} 

Answer 2

对于a和b，可以使用两个循环，但是您不需要重复计算c。另外，如果订单无关紧要，您可以假设a >= b >= c这将进一步减少您需要探索的组合。

注意：这些问题大多数是数学问题，而不是编程挑战。编码之前，你需要考虑一个优雅的数学解决方案。

Answer 3

这是我出于好奇而得到的解决方案。针对您发布的问题获取此解决方案非常有趣。你错过了重要的标准，即三个数字必须是不同的，并且没有对所述三个整数的具有共同的因子大于1

public static int gcd(int a, int b) { 
    if (b == 0) { 
     return a; 
    } else { 
     return gcd(b, a % b); 
    } 
} 

public static int pairwisePrimes(int k) { 
    int numWays = 0; 
    for (int a = 1; a < k; a++) { 
     for (int b = a + 1; b < k; b++) { 
      for (int c = b + 1; c < k; c++) { 
       if ((a + b + c == k) && gcd(a, b) == 1 && gcd(a, c) == 1 && gcd(b, c) == 1) { 
        System.out.println("" + a + "+" + b + "+" + c); 
        numWays++; 
       } 
      } 
     } 
    } 
    return numWays; 
} 

Answer 4

该组三胞胎(a,b,c)，使得a+b+c=k定义3D平面空间，即2D实体。对于一个给定的k，正确的整数正好有(k+1)(k+2)/2解决方案。这个表达式是O(k^2)，表明双循环将会执行。

for a= 0 to k 
    for b= 0 to k-a 
    c= k-a-b 
    ... 

这种解决方案假定

• 0被允许;
• 订单事宜，f.i. （1，2，3）和（2，1，3）是两个不同的解决方案。

Answer 5

在我看来，由于只有40个值需要支持，TopCoder问题的最佳解决方案是在预先计算的向量中查找。没有什么能击败（它既是超快和超小型）：

int Table[41]= { 0, 0, 0, 0, 0, 0, 1, 0, 2, 1, 3, 1, 6, 1, 7, 3, 7, 3, 14, 3, 15, 6, 14, 6, 25, 6, 22, 10, 25, 9, 42, 8, 34, 15, 37, 15, 53, 13, 48, 22, 53 }; 

return Table[Num]; 

表可以被计算为根据需要（I中使用的简单的Python脚本）低效。

import fractions 

for k in range(40 + 1): 
    T= 0 
    for a in range(1, k + 1): 
     for b in range(1, k + 1): 
      for c in range(1, k + 1): 
       if a < b and b < c and a + b + c == k and fractions.gcd(a, b) == 1 and fractions.gcd(b, c) == 1 and fractions.gcd(c, a) == 1: 
        T+= 1 
    print T