C程序优化问题

thelord

wyj915752168 发表于 2013-3-5 21:22
哎。。。可惜不对啊。。。因为 m^2-mn-n^2=±1条件约束。。。不过还是谢谢你

看来数学真的生疏了
不过我看着是恒等式推导啊，条件约束用了的，哪里的问题？

wyj915752168

thelord 发表于 2013-3-5 21:37
看来数学真的生疏了
不过我看着是恒等式推导啊，条件约束用了的，哪里的问题？

m和n的取值是受限于约束方程的 m^2-mn-n^2=±1，后面那个等式是没错，但是m，n的取值还要结合 m^2-mn-n^2=±1这个式子

utraedit

wyj915752168 发表于 2013-3-5 21:13
问题是定义的a,b 不一定是整数，因为有1/2。。。所以变量范围扩大了，也不能最后再处理回整数m,n

这个问题其实好说，可以让两边同时乘以2就OK啦，
不过貌似1<m,n<k这个条件不好整，我刚在codeblocks试了下，还是比较慢

哎，我也学的不咋的，

ELOHIM

main函数为整型，没有return 可以吗？

loms126

ELOHIM 发表于 2013-3-5 22:17
main函数为整型，没有return 可以吗？

貌似较新版本的编译器会自动为main补return。可以写个简单的程序反编译一下，看忽略return是否有区别。

ELOHIM

loms126 发表于 2013-3-5 22:29
貌似较新版本的编译器会自动为main补return。可以写个简单的程序反编译一下，看忽略return是否有区别。

看电视看晕了，
怎么可以返回啊，一返回就退出程序了。。

thelord

wyj915752168 发表于 2013-3-5 21:44
m和n的取值是受限于约束方程的 m^2-mn-n^2=±1，后面那个等式是没错，但是m，n的取值还要结合 m^2-mn-n^2 ...

多谢提醒，

继续，m(m-n)-n^2=±1，若 n>m，等式不成立，所以 n<=m（仅当 n=m=1 时等号成立）
这个约束可能有点用

loms126

时间复杂度的问题：
如果直接两层循环套嵌的话，时间复杂度为O(n*n)。n=k,习惯用n表示。
我8楼写的那个，一个循环套两个分支判断，时间复杂度为O(n)。
要降低时间复杂度，比较有效的方法是加限定条件减少不必要的循环。减少循环可能就是老师出题的初衷。

wyj915752168

loms126 发表于 2013-3-6 08:24
时间复杂度的问题：
如果直接两层循环套嵌的话，时间复杂度为O(n*n)。n=k,习惯用n表示。
我8楼写的那个， ...

感谢一大早来解答   确实是这样   我去学习一下

peng85344558

前排没了，那我就得高调点的说下减少循环的方法咯，估计这方法会让楼上N层都汗颜的
1.按照条件，m^2-mn-n^2=1 or -1 ,得到的结果肯定是0.5*m<=n<=m，第一层循环用m，这个可以减少了n的循环,m取值从k到K/2就够了，多了误时，计算出的结果很小。
2.第一层m取双数时，n不能为双数才满足结果是单数，所以m、n都为双数时，跳过计算
3.需求是使得m^2+n^2最大，很明显在满足了m^2-mn-n^2=1 or -1的(m,n)集合，m,n越靠近k就越大，那么m,n循环中都从k逐一减少，得到满足条码的第一个（m，n）值就行了，再循环下去也不会比前面的大，第一个绝对就是最大值，不信你自己算看结果
PS:我就随便想想而已，只是用CPC的思路+数学的简单证明去看这个问题，另外写代码的时候不要光用顺势思维（i不一定要从1开始，i+1啊），也不要老想着从式子出发去优化。。。哈哈
PS2:吃了饭没事，用matlab试了下，K是用了40,000吧，计算也不用2分钟，楼主好好努力了，只要理解不要错，逻辑代码不会错，那就没问题了。。。
PS3：要注意数据太大溢出的问题，99,999*99,999结果都多少位了，你得定义多长了，我用matlab最大支持2^32，所以只用了40,000