曾经有4个流浪汉在全国各地旅行。在他们的
旅途中，他们的资金短缺，所以他们停在农场寻找一些工作。这位农夫说，接下来的几周内可能要完成200个小时的工作。农夫接着说
，他们如何划分工作取决于他们。食堂同意
从第二天开始。
第二天早上，其中一个食堂-明显比其他三个更聪明和更懒惰-说没有理由他们都要做相同的工作。该流浪汉继续建议以下方案：
流浪汉都会吸起稻草。
稻草会标有数字。
该数字将指示抽屉必须工作的天数以及每个工作日中的工作小时数。例如
，如果吸管上标有3，则吸取它的流浪汉将每天工作3个小时，共3天。
不用说懒惰流浪汉说服了其他人
同意这一计划，懒惰的流浪汉
抓住了最好的稻草。
根据前述方案进行工作。
基本上只涉及找到\ $ a，b，c，d \ $的所有可能解，使得\ $ a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2} = 200 \ $
for(int a = 1;a<=100; a++)
for(int b = 1; b<=100; b++)
for(int c = 1; c<=100; c++)
for(int d = 1; d<=100; d++){
++counter;
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
}
#1 楼
请注意，15或更大的数字的平方如何超过200？您所能做的就是设置从1到14的间隔。一次又一次地评估相同的组合没有优势。意识到最有效的方法是构造您的for循环，这样
$$ a \ leq b \ leq c \ leq d $$
迭代38,416次！
通过限制时间间隔，您仅迭代2380次！
您还可以做一件事：检查\ $ a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2}> 200 \ $
for(int a = 1; a<=14; a++)
for(int b = a; b<=14; b++)
for(int c = b; c<=14; c++)
for(int d = c; d<=14; d++){
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(a*a + b*b + c*c + d*d > 200)
break;
}
现在，您只需迭代1,214次！这样更有效。
评论
\ $ \ begingroup \ $
目前正在用我的手机在同一行上写一个答案....但是该死的慢了。不错的数字+1
\ $ \ endgroup \ $
–Vogel612♦
14-10-9在6:20
\ $ \ begingroup \ $
让我们假设a == 14将导致196 + b ^ 2 + c ^ 2 + d ^ 2 == 200这也不会发生。因此您可以将循环限制为13
\ $ \ endgroup \ $
– Heslacher
2014年10月9日下午6:26
\ $ \ begingroup \ $
如果可以的话，用一汤匙的焦油。提议的解决方案是\ $ O（n ^ 2）\ $（每个最多4个\ $ \ sqrt n \ $嵌套循环。当然我们可以做得更好。构建一个正方形表（\ $ O（\ sqrt n）\ $时间和空间）。建立成对的平方和表（\ $ O（n）\ $时间和空间），找到所有加在一起的目标对（\ $ O（n）\ $时间，\ $ O（1 ）\ $空间）。
\ $ \ endgroup \ $
–vnp
14-10-9在6:39
\ $ \ begingroup \ $
@vnp如何满足a <= b <= c <= d的条件。如果有一个\ $ O（n）\ $解决方案，它应该是自己的答案。
\ $ \ endgroup \ $
– abuzittin gillifirca
2014年10月9日下午6:55
\ $ \ begingroup \ $
@IvoBeckers检查我的解决方案是否有相似的想法。我使循环从大到小减小了比较所花费的时间，但从本质上讲，这是相同的想法。
\ $ \ endgroup \ $
– Tibos
2014年10月9日14:49
#2 楼
您应该注意的一件事是，第四次迭代是无用的。固定前三个变量后，您需要找到第四个变量的值等于200减去前三个变量的平方和。您不必遍历所有可能的数字来检查其中是否有一个squared等于N，您可以简单地取N的平方根，然后检查它是否为整数。要注意的另一件事是，您以相同的顺序多次获得相同的解。通过对变量进行排序，可以很容易地避免这种情况（并因此避免了很多迭代）。最后，如果早期失败，则可以减少迭代次数。一旦检查a = 15并看到平方大于200，就不再需要检查a的更高值。
聪明的事情是从可能仍会导致解决方案的最大数字。
解决方案： C年龄段。
输出：
int N = 200;
for (int a = (int) sqrt(N); a >= 0; a--) {
for (int b = min(a, (int) sqrt(N - a*a)); b >= 0; b--) {
for (int c = min(b, (int) sqrt(N - a*a - b*b)); c >= 0; c--) {
double remaining = sqrt(N - a*a - b*b - c*c);
int d = (int) remaining;
if ((d == remaining) && (d <= c)) {
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
}
}
}
}
评论
\ $ \ begingroup \ $
您会发现这不会产生与原始结果相同的结果。我知道您要去，但还需要为您添加解决方案的另一步骤。对于找到的每个解决方案，您还需要找到所有排列。
\ $ \ endgroup \ $
–马丁·约克
2014年10月10日，9：45
\ $ \ begingroup \ $
实际上，第三个循环也是多余的。根据勒让德的三个平方定理，除非整数m和n的形式为（8m + 7）4 ^ n，否则数字可以表示为三个平方的和。 200不是这种形式（200 = 8 * 5 * 5），因此必须存在a ^ 2 + b ^ 2 + c ^ 2 + 0 = 200形式的解决方案，您只需要循环计算a和b;懒散的流浪汉不起作用。 （或者，如果您是一个懒惰的程序员，您只需声明懒惰的流浪汉知道勒让德的三平方定理，就可以找到d = 0的解。）
\ $ \ endgroup \ $
– David Richerby
2014年10月10日10:28
\ $ \ begingroup \ $
@DavidRicherby它不能帮助您找到所有解决方案。
\ $ \ endgroup \ $
– Tibos
2014年10月10日10:58
\ $ \ begingroup \ $
@Tibos当然，如果您需要所有解决方案，Legendre并没有太大帮助。我没有注意到问题的这一部分，但我想我会保留相关的评论（而且，我认为很有趣）。
\ $ \ endgroup \ $
– David Richerby
2014年10月10日上午11:07
\ $ \ begingroup \ $
sqrt很贵。我将用零填充1..200数组，然后对于1..14将带有平方的插槽分配给值。得到200 -a ^ 2-b ^ 2-c ^ 2，如果输入非零，则为d，否则，a，b，c均无答案。
\ $ \ endgroup \ $
–Loren Pechtel
2014年10月13日，3：19
#3 楼
一些小事，但仍然值得一提：每当使用
std::endl时，缓冲区都会被刷新，这可以提高性能，尤其是多次执行时。为了获得没有添加刷新的换行符，请在输出语句中使用
"\n"：增强可读性：std::cout << "\n";
评论
\ $ \ begingroup \ $
使用了命名空间std ...通常不好，对吧？ ？
\ $ \ endgroup \ $
–Vogel612♦
2014年10月9日下午6:27
\ $ \ begingroup \ $
@ Vogel612：是的，但是我在这里没有提到它，因为这只是一个小问题。
\ $ \ endgroup \ $
– Jamal♦
2014年10月9日下午6:28
#4 楼
风格Vogel612在他的评论中提出了一个有趣的观点：
using namespace std;通常被认为是一种不好的做法。您可以只使用const int lim = 200;。它使事情更容易阅读/理解并且更容易维护：双赢！将自己限制为：$$ a \ leq b \ leq c \ leq d $$
这会导致得出有趣的结论：
$$ 4 * a ^ {2} \ leq a ^ {2} + b ^ {2} + c ^ {2} + d ^ {2} = 200 $$
因此$$ a ^ {2 } \ leq 50 $$
因此$$ a \ leq 7 $$
我们可以在代码中充分利用这一优势，方法是当我们知道没有希望找到更多的代码时就停止。 >
让我们忘掉数学，然后用简单的C ++编写这件事（将不同的计算值存储在变量中以供重用）：考虑
当
a，b和c固定时，寻找d可以进一步优化：我们要解决a ^ {2} + b ^ {2} + c ^ {2}）$$
您只需计算根，看看它是否对应于大于
c的整数。#5 楼
除了@EngieOP提供的出色信息外，您还可以考虑从内部循环中进行一些重复的计算，但每个“ for”循环需要额外的int成本。这些可以由编译器进行优化，但不应降低清晰度。for(int a = 1; a<=14; a++){
sum_a = a*a;
for(int b = a; b<=14; b++){
sum_b = sum_a + b*b;
for(int c = b; c<=14; c++){
sum_c = sum_b + c*c;
/*[... etc ...] */
它不会减少迭代次数，但可以减少循环数在内部循环中进行单个添加和比较（如果编译器尚未捕获优化并为您完成优化操作）
评论
\ $ \ begingroup \ $
通过向内部for循环中添加一个小的测试，我们可以扩展这种方法以减少迭代次数，即for（int c = 1; c <= 14 && sumB <200; c ++）和for（int d = 1； d <= 14 && sumC <200； d ++）。通过这种方式，搜索将产生17458次迭代而不是38416次重复的相同结果。
\ $ \ endgroup \ $
– Desty
2015年2月6日在11:34
#6 楼
要考虑的一件事，在循环内和/或循环声明内进行重复乘法可能会非常昂贵。考虑以下内容，它将所有正方形放入数组中，并且循环仅遍历数组。这消除了很多额外的计算。在我的测试中，即使增加了额外的循环成本，这也使速度提高了约30％。int squares[15];
const int limit = 200;
int it_limit = 15;
for (int i = 1; i < it_limit; i++)
squares[i] = i*i;
int temp = 0;
for (int a = 1; a < it_limit; a++)
{
temp = squares[a];
for (int b = a; b < it_limit; b++)
{
temp = squares[b] + squares[a];
if (temp > limit)
break;
for (int c = b; c < it_limit; c++)
{
temp = squares[c] + squares[b] + squares[a];
if (temp > limit)
break;
for (int d = c; d < it_limit; d++)
{
temp = squares[d] + squares[c] + squares[b] + squares[a];
if (temp > limit)
break;
if (temp == limit)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << "\n";
}
}
}
}
#7 楼
以较少的迭代次数找到所有解决方案：#include <iostream>
#include <sstream>
#include <map>
#include <vector>
typedef unsigned int T;
int main()
{
const T LIMIT = 2000000;
std::map< T,std::vector< std::pair< T,T > > > pairs_of_squares;
T a, b, c, d, sum_of_squares, remaining;
unsigned long increment = 0;
unsigned long num_results = 0;
unsigned long index;
std::vector< std::pair< T, T > > array_of_pairs;
std::stringstream out;
for ( a = 1; 2 * a * a <= LIMIT - 2; ++a )
{
for ( b = a; (sum_of_squares = a*a + b*b) <= LIMIT - 2; ++b )
{
remaining = LIMIT - sum_of_squares;
// Check if it is possible to get another pair (c,d) such that either
// a <= b <= c <= d or c <= d <= a <= b and, if not, ignore this pair.
if ( a * a * 2 < remaining && remaining < b * b * 2 )
{
++increment;
continue;
}
pairs_of_squares[sum_of_squares].push_back( std::pair<T,T>(a,b) );
if ( pairs_of_squares.count( remaining ) != 0 )
{
array_of_pairs = pairs_of_squares[ remaining ];
for ( index = 0; index < array_of_pairs.size(); ++index )
{
c = array_of_pairs[index].first;
d = array_of_pairs[index].second;
if ( b <= c )
{
out << a
<< ", " << b
<< ", " << c
<< ", " << d
<< '\n';
++num_results;
}
else if ( d <= a )
{
out << c
<< ", " << d
<< ", " << a
<< ", " << b
<< '\n';
++num_results;
}
++increment;
}
}
else
{
++increment;
}
}
}
std::cout << out.str()
<< num_results << " possibilities found in " << increment << " increments." << std::endl;
return 0;
}
输出：
对于200的限制： />
2, 4, 6, 12
6, 6, 8, 8
2 possibilities found in 75 increments.
real 0m0.005s
user 0m0.003s
sys 0m0.002s
[注意：这只需要75次迭代，而不是超过1000次才能找到所有可能的答案。]
限制为2,000,000：
...
104, 192, 984, 992
56, 112, 984, 1008
1221 possibilities found in 785771 increments.
real 0m0.890s
user 0m0.873s
sys 0m0.014s
解释：
不要单独处理所有4个数字-只能处理两对数字（低值对和高值对）。 br />
首先生成一对数字\ $（a，b）\ $，其中\ $ a \ leq b \ $和\ $ a ^ 2 + b ^ 2 \ leq LIMIT-2 \ $（注意：2是另一对数字的最小平方和）并将该对数字推入地图。
然后检查地图是否包含另一对\ $（c，d） \ $其中\ $ c \ leq d \ $和\ $ c ^ 2 + d ^ 2 = LIMIT-a ^ 2-b ^ 2 \ $使得\ $ a \ leq b \ leq c \ leq d \ $或\ $ c \ leq d \ leq a \ leq b \ $，在这种情况下，它是一个有效的答案并输出。 $。
#8 楼
在阅读了约翰的评论后，我认为我们可以做得比EngieOP的答案要好得多。如何加快这一步？减少计算量！
for(int a = 1; a<=14; a++)
for(int b = a; b<=14; b++)
for(int c = b; c<=14; c++)
for(int d = c; d<=14; d++){
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(a*a + b*b + c*c + d*d > 200)
break;
}
但是这样，我们仍然为每次迭代计算
a*a + b*b + c*c + d*d。因此，让我们像rolinger的答案已经显示的那样减少它们int resultToReach = 200;
int maxBorder = (int)sqrt(200);
for(int a = 1; a<=maxBorder ; a++)
for(int b = a; b<=maxBorder ; b++)
for(int c = b; c<=maxBorder ; c++)
for(int d = c; d<=maxBorder ; d++){
int tempResult = a*a + b*b + c*c + d*d;
if(tempResult == resultToReach)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(tempResult > resultToReach)
break;
}
如果现在反转循环并添加一些次要条件，我们将得到此
int resultToReach = 200;
int maxBorder = (int)sqrt(resultToReach);
for (int a = 1; a <= maxBorder; a++)
{
int firstResult = resultToReach - a * a;
for (int b = a; b <= maxBorder; b++)
{
int secondResult = firstResult - b * b;
for (int c = b; c <= maxBorder; c++)
{
int thirdResult = secondResult - c * c;
for (int d = c; d <= maxBorder; d++)
{
int tempResult = thirdResult - d * d;
if (tempResult == 0)
{
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
break;
}
else if (tempResult < 0)
{
break;
}
}
}
}
}
因为我没有手工C ++，所以我用C＃进行计时。这将在约19秒内为
resultToReach==2000000计算1221个唯一组合。 考虑到乔赛（Josay）的评论，就会产生此问题。
int resultToReach = 200;
int maxBorder = (int)sqrt(resultToReach);
for (int a = maxBorder; a >= 1; a--)
{
int firstResult = resultToReach - a * a;
if (firstResult >= 3)
{
for (int b = a; b >= 1; b--)
{
int secondResult = firstResult - b * b;
if (secondResult >= 2)
{
for (int c = b; c >= 1; c--)
{
int thirdResult = secondResult - c * c;
if (thirdResult >= 1)
{
for (int d = c; d >= 1; d--)
{
int tmpResult = thirdResult - d * d;
if (tmpResult == 0)
{
counter++;
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
break;
}
else if (tmpResult > 0)
{
break;
}
}
}
}
}
}
}
}
由于我没有手工的C ++，所以我在C＃中进行了计时。这将在约4.5秒内为
resultToReach==2000000计算1221个唯一组合。 #9 楼
实际上，我对hobo问题的答案是以迭代方式解决a*a+b*b+c*c+d*d = 200的假设并不满意。我认为这是一个平方根和舍入问题，可以使用贪婪算法解决。
工作量最高的人最多可以进行14.142天的
sqrt(200) = 14.142小时。四舍五入后，该值为14 * 14 = 196，其他3个仅剩下4个小时的工作。这不起作用。尝试13 ... 200-（13 * 13） = 31表示其他3个，然后递归检查下一个家伙，它给出以下代码： />
int find_worst_hours( int workleft, int numguys )
{
static int num_interations = 0;
int mine = (int)floor(sqrt((double)workleft));
TRACE( "Num iterations = %d\n", ++num_interations );
while( mine > 0 ) {
int leftover = workleft - mine*mine;
TRACE( "Guys Left %d:I would do %d, rest would do %d\n", numguys, mine, leftover );
if ( numguys == 1 ) {
// last guy
if ( leftover > 0 ) {
return -1; // bad solution, work left over.
} else {
// no work left, this is a good solution.
TRACE( "GOOD END, guy %d, work %d\n", numguys, mine );
return mine;
}
} else {
// check the rest of guys
if ( leftover == 0 ) {
return -1; // bad solution, the other guys need work
}
int next_guys_work = find_worst_hours( leftover, numguys-1 );
if ( next_guys_work > 0 ) {
// valid solution
TRACE( "GOOD PARTIAL, guy %d, work %d\n", numguys, mine );
return mine;
} else {
// couldn't find a solution... try less hours
mine--;
// continue while loop
}
}
}
return -1; // couldn't find solution
}
它应该输出：
Num iterations = 1
Guys Left 4:I would do 14, rest would do 4
Num iterations = 2
Guys Left 3:I would do 2, rest would do 0
Guys Left 4:I would do 13, rest would do 31
Num iterations = 3
Guys Left 3:I would do 5, rest would do 6
Num iterations = 4
Guys Left 2:I would do 2, rest would do 2
Num iterations = 5
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 1, rest would do 5
Num iterations = 6
Guys Left 1:I would do 2, rest would do 1
Guys Left 3:I would do 4, rest would do 15
Num iterations = 7
Guys Left 2:I would do 3, rest would do 6
Num iterations = 8
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 2, rest would do 11
Num iterations = 9
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 1, rest would do 14
Num iterations = 10
Guys Left 1:I would do 3, rest would do 5
Guys Left 3:I would do 3, rest would do 22
Num iterations = 11
Guys Left 2:I would do 4, rest would do 6
Num iterations = 12
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 3, rest would do 13
Num iterations = 13
Guys Left 1:I would do 3, rest would do 4
Guys Left 2:I would do 2, rest would do 18
Num iterations = 14
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 1, rest would do 21
Num iterations = 15
Guys Left 1:I would do 4, rest would do 5
Guys Left 3:I would do 2, rest would do 27
Num iterations = 16
Guys Left 2:I would do 5, rest would do 2
Num iterations = 17
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 4, rest would do 11
Num iterations = 18
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 3, rest would do 18
Num iterations = 19
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 2, rest would do 23
Num iterations = 20
Guys Left 1:I would do 4, rest would do 7
Guys Left 2:I would do 1, rest would do 26
Num iterations = 21
Guys Left 1:I would do 5, rest would do 1
Guys Left 3:I would do 1, rest would do 30
Num iterations = 22
Guys Left 2:I would do 5, rest would do 5
Num iterations = 23
Guys Left 1:I would do 2, rest would do 1
Guys Left 2:I would do 4, rest would do 14
Num iterations = 24
Guys Left 1:I would do 3, rest would do 5
Guys Left 2:I would do 3, rest would do 21
Num iterations = 25
Guys Left 1:I would do 4, rest would do 5
Guys Left 2:I would do 2, rest would do 26
Num iterations = 26
Guys Left 1:I would do 5, rest would do 1
Guys Left 2:I would do 1, rest would do 29
Num iterations = 27
Guys Left 1:I would do 5, rest would do 4
Guys Left 4:I would do 12, rest would do 56
Num iterations = 28
Guys Left 3:I would do 7, rest would do 7
Num iterations = 29
Guys Left 2:I would do 2, rest would do 3
Num iterations = 30
Guys Left 1:I would do 1, rest would do 2
Guys Left 2:I would do 1, rest would do 6
Num iterations = 31
Guys Left 1:I would do 2, rest would do 2
Guys Left 3:I would do 6, rest would do 20
Num iterations = 32
Guys Left 2:I would do 4, rest would do 4
Num iterations = 33
Guys Left 1:I would do 2, rest would do 0
GOOD END, guy 1, work 2
GOOD PARTIAL, guy 2, work 4
GOOD PARTIAL, guy 3, work 6
GOOD PARTIAL, guy 4, work 12
因此仅进行了33次迭代，我们找到了答案2,4,6,12。计算起来应该非常快。
评论
\ $ \ begingroup \ $
6 ^ 2 + 6 ^ 2 + 8 ^ 2 + 8 ^ 2又如何呢？
\ $ \ endgroup \ $
– Heslacher
2014年10月9日14:47
\ $ \ begingroup \ $
您可以更改算法以确定所有可能的解决方案吗？现在，它退出第一个解决方案，这不是OP要求的。
\ $ \ endgroup \ $
– Tibos
2014年10月9日14:57
\ $ \ begingroup \ $
Tibos-如果有时间，我会这样做，但是由于它是一个贪婪的算法，并且这个人是一个贪婪的流浪汉，所以第一个解决方案是他心中唯一的解决方案。
\ $ \ endgroup \ $
–新维卡因
2014年10月9日15:09
\ $ \ begingroup \ $
除非有明确说明，否则谜语是确定根据上述方案划分工作的可能方法。请注意，它说的是可能的方法，而不是最好的方法。
\ $ \ endgroup \ $
–tinstaafl
2014年10月9日15:42
\ $ \ begingroup \ $
@DavidRicherby-我的意思就是这一点。
\ $ \ endgroup \ $
–tinstaafl
2014年10月10日12:15
评论
柜台在做什么？我在计算迭代次数。
您在这里有1亿次通过循环。由于15 ^ 2已经超过200，因此您实际上只需要14 ^ 4 = 38,416通过。