for循环的使用以及优化：解整数不定方程

定性分析

这个方程的整数解如何得到？

方程:文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

函数f1、f2以及f3：文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

f1以及f2的导数，也就是曲线f的斜率， 理论上f2的斜率是比f1愈来愈峻峭，f1以及f2只有有限的几个交点。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

方程的整数解是曲线f1以及f2的交点。 因为f1画图不利便, 可以从f2以及f3的形态推知f1以及f2只有有限的交点。由于f3只是f1的平移。 f2以及f3的图象示意如下， 显明只有有限个交点。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

ps: x是对称的，所以如果有整数解x则-x也是其解。下面讨论都是基于x为正整数。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

鼎力出奇迹

思路

无论三七二十一，x以及y都从0开始，依照自然数递增的方式去摸索。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

两层循环，外层是x， 内层是y。然后尝试计算f1以及f2， 如果f1 == f2 就打印结果，终止循环。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

无非这里可做一点点局部优化，就是x^2+615=2^y >=615 可以推出y>9。外层循环x 从0开始，内存循环可以从10开始。文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

代码

equation.cpp文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

include <cmath>
using namespace std;文章源自微观生活（93wg.com）微观生活-https://93wg.com/4397.html

int main
{
if return -1;
long n = atol;
long m = atol;
bool flag = false; //找到解的标志，找到为true未找到为false
for //x没到循环上限值且未找到解的就继续
{
for
{
long long f1 = 615 + pow;
long long f2 = pow;
if //找到，打印解
{
flag = true;
cout << &34; << &34; << &34; << endl;
cout << &34; << &34; << &34; << endl;//共轭解
break;
}
}
}
return 0;
}

复制代码

代码解读

n 以及 m是通过命令输入，来节制x以及y的上限的。

flag 为找到解的标志。

外层循环的终止前提是表示式 x < n && !flag 的值为false。

这个解法无比自然，基本属于鼎力出奇迹的规模。

执行结果

局部优化

思路

• 减少外层循环次数。
• 参考视频，推断x的情势为6k+1或6k-1 ，k为整数

代码

include <cmath>
using namespace std;

int main
{
if return -1;
long n = atol;
long m = atol;
bool flag = false;
for
{
for
{
long long f1 = 615 + pow;
long long f2 = pow;
if
{
flag = true;
cout << &34; << &34; << &34; << endl;
cout << &34; << &34; << &34;,&34;)&34;&34;:&34;&34;&34;:&34; << &34; << y << &34; << endl;
break;
}
}
}
return 0;
}
复制代码

代码解读

n 以及 m是通过命令输入，来节制x以及y的上限的。

flag 为找到解的标志。

外层循环的终止前提是表示式 k < n && !flag 的值为false。

这个解法跟鼎力出奇迹思路同样，只是先做了一点简单的推断，断定出x的情势，相譬如法一，可以少67%的循环次数。

执行结果

全局优化

思路

• 去掉一层循环。 咱们可以先计算2^y 的结果，依据方程去推出算出x的值: x = sqrt。 x取整后，在依据取整的结果去计算 [x]^2 + 615是不是跟2^y值相等。这里[x]表示对x取整。
• 去掉pow调用，只改用一次sqrt。计算2^y的时候， 可以依据外层循环的次数来累乘2得出。
• y确定大于9, 无须做无谓的计算，所以从10开始。

代码


include <cmath>
using namespace std;

int main
{
if return -1;
long n = atol;
long long p = 512; //2^9 == 512
for
{
p *= 2;
long x = sqrt;
if //判断x确切是整数且知足方程
{
cout << &34; << &34; << endl;
cout << &34; << &34; << endl;
}
break；
}

return 0;
}

执行结果

复制代码

代码解读

减少一层循环，在循环内只有一次sqrt调用。理论上，应当譬如法一以及办法二都要高效。

执行结果

总结

三个办法中，显然办法三是比较优的办法。

本案例晋升效力的办法：

• 局部优化，比方从数学角度先做优化
• 全局优化，不仅要从数学角度，而且逆向思惟，从y动身导出x，再从x去验算y。
• 防止都充循环
• 在循环中尽可能少用函数调用，可以多采取简答的加法以及乘法。

必果学院

腾讯课堂必果学院是一个致力于C/C++/Python全栈学习的平台。必果学院提供从MFC/QT的客户端到linux服务器，嵌入式到物联网，游戏开发到游戏破解等一站式教学。合适0基础的对编程感兴致初高中学生及以程序员为目标职业的在校大学生以及初入职场不就亟待晋升的初中级程序员。

以上就是微观生活（93wg.com）关于“for循环的使用以及优化：解整数不定方程”的详细内容，希望对大家有所帮助！