3

我需要编写一个函数头，它返回一个数字的表示数量作为 3 个正平方的总和。

例如，将 3 表示为 3 个平方和的唯一表示是 3 = 1+1+1，因此如果 number = 3，则函数应返回 1。如果 n 为 27，则函数应返回 2，因为 27 有两种表示 27 = 25 + 1 +1 或 9+9+9。

这是我尝试过的：

#include <iostream>
#include <cmath>
using namespace std;

int  numRep(int num);

int main()
{
   int count = numRep(27);
   cout << count;
   return 0;
}

int numRep(int num)
{
   int count = 0, sum = 0;
   int a =1, b=1, c=1;
   while(a*a <= num -2)
   {
     b = 1; 
     while(b*b <= num -2)
     {
       c =1;
       while(c*c <= num -2)
       {
         sum = a*a + b*b + c*c;
         if (sum == num) count++;
         c++;
       }
       b++;
     }
     a++;
   }
   return count/3;
}

但我没有得到正确的输出。需要一些指导...如果有更好的方法，请建议..

4

5 回答 5

7

这是一个很好的起点：

#include <cmath>
#include <iostream>

int count_sum_of_squares(int n)
{
  int count=0;

  // We only need to test numbers up to and including the square root of n.
  // Also, we want to impose an ordering on [a, b, c] to consider 
  // combinations and NOT permutations.
  for (int a=1; a<=int(sqrt(n)); ++a)
    for (int b=1; b<=a; ++b)
      for (int c=1; c<=b; ++c)
        if (a*a+b*b+c*c==n) // If the squares of {a, b, c} add up to n
          ++count;          // then this is a case that should be counted

  return count;
}

int main()
{
  std::cout << 3 << ': ' << count_sum_of_squares(3) << '\n';
  std::cout << 14 << ': ' << count_sum_of_squares(14) << '\n';
  std::cout << 27 << ': ' << count_sum_of_squares(27) << '\n';
  std::cout << 866 << ': ' << count_sum_of_squares(866) << '\n';
}
于 2013-08-06T18:09:20.900 回答
2

而不是从 1 到 num - 2 搜索，您应该只从上面的当前索引循环中搜索。这样，您就不会重复任何条款。

#include <iostream>
#include <cmath>
using namespace std;

int  numRep(int num);

int main()
{
   int count = numRep(27);
   cout << count << endl;
   return 0;
}

int numRep(int num)
{
   int count = 0, sum = 0;
   int a =1, b=1, c=1;
   while(a*a <= num -2)
   {
     b = a; 
     while(b*b <= num -2)
     {
       c =b;
       while(c*c <= num -2)
       {
         sum = a*a + b*b + c*c;
         if (sum == num) {
            count++;
         }
         c++;
       }
       b++;
     }
     a++;
   }
   return count;
}
于 2013-08-06T18:10:02.737 回答
1

你得到了所有的排列，你想要所有的组合。

示例：当我认为您希望它只有 1 时，numRep(14) 会给您 6。

a = 1, b = 2, c = 3
a = 1, b = 3, c = 2
a = 2, b = 1, c = 3
a = 2, b = 3, c = 1
a = 3, b = 1, c = 2
a = 3, b = 2, c = 1

您需要跟踪您的答案，最好按照 ac 从最低到最高排序，如果已经存在，请不要增加您的计数。

于 2013-08-06T18:07:50.880 回答
1

这对我有用：

 int numRep(int num){

   int count = 0;

   for(int a = 1; a * a <= num ; ++a)
        for(int b = a; b * b <= num ; ++b)
            for(int c = b; c * c <= num ; ++c)
                if (a*a + b*b + c*c == num) 
                    count++;

   return count;
}

b仅从 froma和cfrom开始，b因此您不会计算两次相同的解决方案。

O(N*sqrt(N))我认为这很复杂。

于 2013-08-06T18:09:05.193 回答
0

只需从a. 而且您根本不需要第三个循环。c = sqrt(num - a*a - b*b). 如果这个计算c的是一个整数，那么它会计数。

于 2013-08-07T05:40:20.893 回答