1、申 请 I D ：罂粟滥情
2、个人邮箱：15525140561@163.com
3、原创技术文章：从一个简单问题看代码和算法优化
一个代码的好坏是从这样几个方面来评价的，运算出结果所用的时间（如果像百度，google啊这些几秒不出结果就会让人等不的）,即时间复杂度，运行时所占的内存，即空间复杂度，最后代码尽可能的短，这个是我自己写的一个解题报告，其中五次优化的过程，第六以后的优化用的东西很复杂，不放出来了。
题目选择：不定方程的非负整数解解。
问题描述：问方程x+2y+5z=n,对于特定输入的n（n<=1000000），输出其大于的整数解的个数。其时间限制是为：1000ms。
选择原因：选择此题主要是由于自己实际作此题过程中，遇到了很多问题，这篇报告主要是来写我对于这些问题的解决，与对代码的不断优化。
解题过程：
这个问题非常简单，是的，非常简单，只要一个枚举就能解决，而我为啥还要选择这个问题来写报告了，因为当我改了多次代码系统才通过我写的代码，由于我下了狠心，一定要尽自己最大的努力把它写的最好，写的运行速度最快，甚至举一反三的将这个问题扩散到更广。
我拿到这个问题，想都没想就写了如下的代码：
#include <stdio.h>
void jieshu(int n)
{
int i,j,k,g;
for(i=0;i<=n;i++)
for(j=0;j<=n/2;j++)
for(k=0;k<=n/5;k++)
{
if(i+2*j+5*k==n)
g++;
}
printf("%d",g);
}
int main()
{
int t,n;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d",&n)
jieshu(n);
}
}
return 0;
}
复制代码
这就是一个暴力枚举法，的确对于很小的n，结果完全没有问题，完全没有任何技术含量，这样的代码是个非常差劲的代码，可想而知系统必然不会通过（因为超时了），简单的分析一下,假设计算机的基本单位运算时间是t，这个t是纳秒级的(即10的负九次方秒)，题目所要求的时间是1000ms即1s,大约是10的9次方个t,对于这三个循环所用的时间是n*(n/2)*(n/5)*t,对于很小的n，这个时间必然不大，但是题中n的上限是一百万，即10的6次方，三个10的6次方级的数相乘得出的时间大约是10的18次方个t，也大概是10的9次方秒（一年大概只有10的8次方秒的数量级，想得出结果的话得等上几年吧，你没想到一个这么简单的程序就让你的计算机跑上几年吧），所以这个算法的时间复杂度是o(n^3),永远不要怪数字太大，只能怪自己的算法不好，总没有人嫌自己的钱多吧，况且一百万不多，不然为何中国有那么多百万富翁，之所以认为一百万很多，是因为你总是在拿第一种算法来计算，所以你就算穷尽毕生也很难得到计算结果。
而且算法还有几个很细微的地方带来了额外的开支。第一，对于i=0,j=0，时，k需要枚举到n/5，而对于i=0,j=1,k只需要枚举到(n-2)/5,综上第二层循环实际只需枚举到(n-i)/2,第三层循环只需枚举到(n-i-2*j)/5即可，所以实际进行了过多不必要的枚举带来额外的开支。第二，开始写的这个算法，我犯了一个大忌，即将长循环写在了最外层（for(i=0;i<=n;i++)要循环n次），将最短的循环写在了最内层（for(k=0;k<=n/5;k++)只要循环n/5次），这样增加了cpu循环切换的次数,（学过汇编的大致可以想出原因）增加了时间开支，一个好的代码对于需要多层循环是应该尽可能把最短的循环写在最外层，最长的写在最内层，以增加cpu使用的效率（开始改进时我还是没有将短循环写在外层，导致代码还是通不过）。
综上所述，第一种算法的时间开支实在太高，算法实在太差劲了，如果这题一百分的话，这样的代码最多能得30分。
第一次改进思路：对于经过两次对x,y循环的循环枚举后，实际要使得x+2y+5z=n有正整数解，只要有n-x-2y是5的倍数即可，即不需要再进行第三次循环，就可以通过x,y唯一确定z,通过改进减少循环的总数，减少时间开支，根据这样的思路，我进行了如下的改进,jieshu函数变为了：
void jieshu(int n)
{
int i,j,k,g;
for(i=0;i<=n;i++)
for(j=0;j<=(n-i)/2;j++)
{
if((n-i-2*j)%5==0)
g++;
}
printf("%d",g);
}
复制代码
循环次数大大缩减，时间复杂度变为o(n^2)，但是这个代码必然还是很悲哀的通不过的，因为对于一百万的平方，也有10的12次方之多，换算成秒，所要的时间变成1000秒的数量级左右，虽然还是很悲催的通不过，但是对比第一种算出结果要花几年，第二种只需花不到一个小时就可以算出来了，这个速度是火箭般的飞跃。嗯，虽然还是不及格，对于第一种算法应该有20分的提升吧，这个可以打50分。这个时候，我才想到要把短循环放外层，于是有第二次改进。
第二次改进，是把短循环放外层：
void jieshu(int n)
{
int i,j;
long long g=0; //这时才想到对于百万时，解的数目应该超出了int的范围所以改成long long 型数据
for(i=0;i<=n/5;i++)
{
g+=（n-5*i）/2+1;
}
printf("%lld\n",g);
}
注：对于for(i=0;i<=n/5;i++)
for(j=0;j<=(n-5*i)/2;j++)
g++;
复制代码
可以直接把第二次循环g加的个数求出来，就是(n-5*i)/2+1,所以就写成了g+=(n-5*i)/2+1，再次省去一层循环。这时算法的时间复杂度就变成了o(n),当然这个时候算一百万所要的时间也就1ms左右了，又是一次火箭般的飞跃，当然这个时候系统也终于通过了，可以及格了，这时的算法可以得60分了，及格万岁！一般做到这里通过了就可以满足了，毕竟及格万岁，但是对于被这样简单的题拖累了这么长时间的我不太甘心，毕竟对于一个时间复杂度为o(n)的算法，当输入的大小为100亿时又有等待了，一百亿大吗？看看比尔盖茨的资产去吧。
第三次改进，
注意到第二次改进后的算法：
for(i=0;i<=n/5;i++)
g+=(n-5*i)/2+1;
实际上是一个这样的数列的和：n/2+(n-5)/2+(n-10)/2+…+(n%5)/2,然后加上n/5,对于一个数列求和实际是可以手工求出其通项的表达的，这样就可以省去最后一层循环，使得时间更短且与输入数的大小几乎无关。虽然对于这样的数列的求和，不管是高中还是大学，都没有学过怎么解，慢慢来分情况讨论吧，先根据n%5分为5种不同情况，即：
Switch(n%5)
Case 0:
Case 1:
Case 2:
Case 3:
Case 4:
我们先看看case 0的这组(n-5*i)数列是这样的。
0,5,10,15,20,25,30,35,40,45,50,55,60,65，…… 记为数列1。
输入的n对应的为它的第x项，得x=n/5+1。让它的每个数做/2运算得到另外一组数列,有（n-5*i）/2的数列：
0,2,5,7,10,12,15,17,20,22,25,27,30,32，…… 记为数列2。
这组数列即我们要求和的数列，对数列2的前x项求和，然后再加上n/5即可得到对于任意n该不定方程解的个数。注意到数列2的个位数是每4个数一循环（0,2,5，7,0,2,5,7……），每4个数进10，将0,2,5,7相加为0+2+5+7=14，可以先把x之前刚好被4整除的项相加，剩下的x%4项另作讨论，这样有：(x/4)*14+(0+1+2+…+(x-1)/4)*40加上剩下的x%4项就可以了，这样再加个判断：
Swich(x%4)
Case 0: break;//因为这是整除的情况，不加任何数之间跳出就行了。
Case 1: …+(x/4)*10+0;
Case 2: …+(x/4)*20+0+2;
Case 3: …+(x/4)*30+0+2+5;
这样对于case 0的情况就可以谈论完全了。
接着对于case 1的情况进行讨论有, n-5*i的数列为：
1,6,11,16,21,26,31,36,31,36,41,46,51,56,61，…… 记为数列3
所以（n-5*i）/2数列为：
1,3,5,8,11,13,15,18,…… 记为数列4
同样个位也是每四个一循环，每四个一进位。1+3+5+8=16,有x/4)*16+(0+1+2+…+(x-1)/4)*40。
Swich(x%4)
Case 0: break;//因为这是整除的情况，不加任何数之间跳出就行了。
Case 1: …+(x/4)*10+1;
Case 2: …+(x/4)*20+1+3;
Case 3: …+(x/4)*30+1+3+5;
对于case 1的情况的讨论就完了。
同样对于case 2,case 3,case 4都可以完整的谈论。
于是写出代码有：
void jieshu(int n)
{
long long x=n/5+1;
long long g=0;
g+=(x/4-1)*(x/4)*20; //这里表示(0+1+2+…+(x-1)/4)*40的和
g+=x;
switch(n%5)
{
case 0:
{
g+=(x/4)*14;
switch(x%4)
{
case 0:
break;
case 1:
g+=(x/4)*10;
break;
case 2:
g+=(x/4)*20+2;
break;
case 3:
g+=(x/4)*30+7;
break;
}
}
break;
case 1:
{
g+=(x/4)*16;
switch(x%4)
{
case 0:
break;
case 1:
g+=(x/4)*10;
break;
case 2:
g+=(x/4)*20+3;
break;
case 3:
g+=(x/4)*30+8;
break;
}
}
break;
case 2:
{
g+=(x/4)*18;
switch(x%4)
{
case 0:
break;
case 1:
g+=(x/4)*10+1;
break;
case 2:
g+=(x/4)*20+4;
break;
case 3:
g+=(x/4)*30+9;
break;
}
}
break;
case 3:
{
g+=(x/4)*20;
switch(x%4)
{
case 0:
break;
case 1:
g+=(x/4)*10+1;
break;
case 2:
g+=(x/4)*20+5;
break;
case 3:
g+=(x/4)*30+11;
break;
}
}
break;
case 4:
{
g+=(x/4)*22;
switch(x%4)
{
case 0:
break;
case 1:
g+=(x/4)*10+2;
break;
case 2:
g+=(x/4)*20+6;
break;
case 3:
g+=(x/4)*30+13;
break;
}
}
break;
default:
break;
}
printf("%lld\n",g);
}
复制代码
虽然很长，但是求解过程只有几次运算，加几次判断，求解速度又完成了一次飞跃，从前面的与n大小相关到与n无关，运算速度直接降到10~100ns,缺陷就是代码太长，太繁琐，是不是可以继续改进，这样会被很多人骂作多余其事。
第四次优化，注意第三次优化的代码中，注意到：
Case 0: g+=（x/4）*14……
Case 1: g+= (x/4) *16……
Case 2: g+= (x/4) *18……
Case 3: g+= (x/4) *20……
Case 4: g+= (x/4) *22……
可以用一个表达式来说明这个判断即： g+= (x/4) *(14+2*(n%5)).
然后对于其后的x%4判断，可以用一个必小于4次的for循环来替代，
有：for(i=0;i<x%4;i++)
g+=(n%5+5*i)/2;
可以将整个代码缩减。
第四次优化代码如下:
void jieshu(int n)
{
long long x=n/5+1;
long long g;
g+=(x/4-1)*(x/4)*20+(x+(x/4)*(14+(n%5)*2)+(x/4)*(x%4)*10);
for(i=0;i<x%4;i++) //由于x%4永远小于等于4，循环最多四次
g+=(n%5+5*i)/2;
printf("%lld\n",g);
}
复制代码
现在精简了很多，而且省去了几次判断，不仅运算速度比第三次优化后的代码更短了，而且代码的长度甚至比最开始还短得多，然而
g+=(x/4-1)*(x/4)*20+(x+(x/4)*(14+(n%5)*2)+(x/4)*(x%4)*10);
这个表达式是不是太长了，而且其中重复算了几次x/4,n%5等运算。
于是第五次优化，给这些要重复计算的表达式单独开辟空间，用空间换取简略，换取计算时间更改如下:
void jieshu(int n)
{
long long g,x,y,z,r;
x=n/5+1;
y=x%4;
z=n%5;
r=x/4;
g+=(r-1)*r*20+(x+r*(14+z*2)+r*y*10);
for(i=0;i<y;i++)
g+=(z+5*i)/2;
printf("%lld\n",g);
}
复制代码
这样修改后，对于x/4,n/5+1,n%5,x%4,均只需要计算一次，以后的计算只需要从储存空间中调取即可，继续增进计算速度。
于是，优化到这步好像没有什么要优化了，运算速度基本已经达到最快了，但是一个好的代码不只是能解决一个问题，而是要能解决一类问题，并举一反三解决最多的问题才能算一个好代码。
总结：对于求一个多元一次不定方程的正整数解的个数求法，可以首先尝试使用暴力枚举法来进行枚举即可求得枚举出其所有的，第一步优化可以采取将某个系数单位化的策略进行减去一层循环的操作，第二步根据可以根据前面的枚举又省去一层循环，将其改成一个判断，加快计算速度，第三步，可以通过第二步的表达求出之前运算的数学表达式，求出通项即可使算法最优。 |
吾爱游客
发表于 2017-10-2 09:03
发表于 2017-10-2 11:33
吾爱游客
发表于 2017-10-7 10:42
