代码之家 › 专栏 › 技术社区 › Khaled Alshaya

Project Euler问题276-原始三角形

math algorithm performance c

Khaled Alshaya · 技术社区 · 15 年前

我试图解决 problem# 276 from Project Euler 但是到目前为止还没有成功。

考虑带整数的三角形 A、B和C边,A_B_C.AN 整型三角形(A,B,C)是如果gcd(a,b,c)=1,则称为原语。怎么用? 许多基本的整型三角形存在周长不超过 10 000?000?

我的代码中的瓶颈是 GCD 功能。我的样本输入几乎需要90%的执行时间。我很想听到提示,关于如何改进解决方案的评论…我的解决方案是用C编写的,但它很简单:

#include <stdio.h>
#include <math.h>

#define sides 3
// This is where my program spends most of its time
size_t bi_gcd (size_t a, size_t b);
size_t tri_gcd (size_t a, size_t b, size_t c);
size_t count_primitive_triangles (size_t maximum_perimeter);

int main()
{
 printf( "primitive_triangles = %lu \n",
            count_primitive_triangles(1000) );
}

size_t bi_gcd (size_t a, size_t b)
{
 size_t t;

 while(b != 0)
 {
  t = b;
  b = a % b;
  a = t;
 }

 return a;
}

size_t tri_gcd (size_t a, size_t b, size_t c)
{
 return bi_gcd(a, bi_gcd(b, c));
}

size_t count_primitive_triangles (size_t max_perimeter)
{
 size_t count = 0; // number of primitive triangles
 size_t a, b, c;   // sides of the triangle
 // the following are the bounds of each side
 size_t 
  // because b >= a && c >= b ==> max of a
  // is when a+b+c > 10,000,000
  // b == a (at least)
  // c == b (at least)
  // ==> a+b+c >= 10,000,000
  // ==> 3*a   >= 10,000,000
  // ==> a= 10,000,000/3
  a_limit = max_perimeter/sides,
  b_limit,
  c_limit;

 for (a = 1; a <= a_limit; ++a)
 {
  // because c >= b && a+b+c <= 10,000,000
  // ==> 2*b + a = 10,000,000
  // ==> 2*b = 10,000,000 - a
  // ==> b = (10,000,000 - a)/2
  for (b = a, b_limit = (max_perimeter-a)/2; b <= b_limit; ++b)
  {
   // The triangle inequality:
   // a+b > c (for a triangle to be valid!)
   // ==> c < a+b
   for (c = b, c_limit = a+b; c < c_limit; ++c)
   {
    if (tri_gcd(a, b, c) == 1)
     ++count;
   }
  }
 }

 return count;
}

5 回复 | 直到 10 年前

ShreevatsaR 15 年前

在优化之前进行分析是很好的,但是事实上 gcd 函数并不一定意味着您需要(或可以)使它更快,而是您太频繁地调用它。-) 这里有一个提示一个算法改进,它将按数量级改进运行时间,而不仅仅是改进实现。

你现在只计算基本三角形。相反,问问你自己:你能有效地数数吗? 全部的 周长为A+B+C=N的三角形(不一定是原始三角形)?(运行时间o(n)将执行“您当前的算法是”(n) ^三 )这样做之后,您对哪些三角形进行了过度计算?例如,有多少个三角形,用p来划分边?(提示:A+B+C=N<=>(A/P)+(B/P)+(C/P)=N/P.)和 so on .

编辑 :在解决了这个问题并检查了ProjectEuler上的线程之后,我发现对于这个问题还有其他一些不错的方法,但是上面的方法是最常见的,而且是有效的。在第一部分中,你可以直接计算它(有些人已经做了,这当然是可行的),或者你可以找到这个额外的提示/技巧有帮助:

假设1_A_B_C,A+B+C=N。设p=b+c-a=n-2a,q=c+a-b=n-2b,r=a+b-c=n-2c。然后是1_R_Q_P,P+Q+R=A+B+C=N。另外,P,Q,R都和N具有相同的奇偶性。
相反,对于任何1_R_Q_P,其中p+q+r=n,三者具有相同的奇偶性(与n相同)。设a=(q+r)/2,设b=(r+p)/2,c=(p+q)/2。然后1_A_B_C和A+B+C=N。此外,这些是整数,形成三角形(检查)。
所以整数三角形(a,b,c)的周长为n 正是将n划分成具有相同奇偶性的部分(p、q、r)的分区数。你可以发现这个更容易计算。

另外/或者,尝试直接将这个数字t(n)与较小的数字t(n-k)联系起来,得到一个递推关系。

(当然,如果你在谷歌上搜索的话,你也可以找到一些非常简单的公式,但是其中有什么有趣的呢?)

interjay 15 年前

您可以改进以下几点:

而不是计算 tri_gcd(a,b,c) 在内环中,计算 g1 = gcd(a,b) 在第二个循环中, g2 = gcd(g1, c) 在内环。
什么时候? gcd(a,b)==1 ,可以避免内部循环并将计数增加 max_c - min_c + 1 ,因为你知道GCD对于C的任何值都是1。
你的内环似乎计数太高了,因为它没有检查 a+b+c <= 10000000 .

不幸的是,即使有了这些变化和其他答案中提到的变化,这可能会太慢。我相信真正的解决方案不会列举所有可能的三角形,而是以某种方式将它们分组计算。

Nick Dandoulakis 15 年前

蛮力解决方案往往很慢:)

减少计算的提示:

预先计算中的所有素数范围2…10 ^七商店在查阅表格中。
在 bi_gcd(a, b) 检查是否 a 或 b 是素数返回 1 否则计算他们的GCD。
在 tri_gcd(a, b, c) .

编辑: 考虑到@interjay的评论:

例如,如果 一 我们还得检查一下 乙 是的倍数 一 ,
像这样的东西 (b % a == 0) . 在那种情况下 一 是GCD。

AakashM 15 年前

除了尼克·D的回答,这会让你不再费心计算 bi_gcd 当一个或两个输入都是主输入时,我发现自己想知道您必须打多少次电话 铋镉镉 具有 相同(复合)数字 . GCD(12,18)总是6,不管你计算了多少次。我怀疑,存储结果的机制可以改进事情。

kennytm 15 年前

作为一个小小的改进,您可以插入一些特殊的案例,例如

size_t bi_gcd (size_t a, size_t b) {
    if (a == 1 || b == 1) return 1;
    ...

size_t tri_gcd (size_t a, size_t b, size_t c) {
    if (a%2==0 && b%2==0 && c%2==0) return 2;
    // of course GCD(a,b,c) can be > 2,
    // but the exact GCD is not needed in this problem.
    ...

用这两个 if -s i可以将时间从1.2秒缩短到1.0秒(使用 gcc -O3 )