项目欧拉问题#276 - 原始三角形

Question

我试图从Project Euler解决问题#276,但到目前为止还没有成功.

考虑具有整数边a,b和c的三角形,其中a≤b≤c.如果gcd(a,b,c)= 1,则整数边三角形(a,b,c)称为基元.存在多少个原始整数边三角形,周长不超过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;
}

Answer 1

在优化之前进行性能分析是件好事,但事实上,gcd函数中的大量时间并不一定意味着您需要(或可以)使其更快,而是您经常调用它.:-)这是一个提示 - 一种算法改进,可以将运行时间提高几个数量级,而不仅仅是实现方面的改进.

您目前只计算原始三角形.相反,问问自己:你能否有效地计算周长a + b + c = n的所有三角形(不一定是原始的)？(运行时间O(n)将执行 - 您当前的算法是Ω(n ³).)完成后,您过度计算了哪些三角形？例如,有多少个三角形用p分开边？(提示:a + b + c = n <=>(a/p)+(b/p)+(c/p)= n/p.)依此类推.

编辑:解决问题并检查Project Euler上的线程后,我发现还有其他一些很好的解决这个问题的方法,但上面的方法是最常见的,并且它可以工作.对于第一部分,您可以直接计算(有些人已经完成了;它当然可行),或者您可能会发现这个额外的提示/技巧很有用:

• 假设1≤a≤b≤c,并且a + b + c = n.令p = b + ca = n-2a,令q = c + ab = n-2b,并且令r = a + bc = 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.此外,这些是整数并形成三角形(检查).
• 因此,具有周长n的整数三角形(a,b,c)的数量正是相同奇偶校验的n个分区(p,q,r)的分区数.您可能会发现这更容易计算.

另外/或者,尝试直接将该数字T(n)与较小的数字T(nk)相关联,以获得递归关系.

(当然,如果你是Google,你也可以找到一些非常简单的公式,但有什么好玩的呢？)