C程序优化问题

wyj915752168

下面的问题虽然简单的程序可以写出，但是问题在于输入数据过大时需要很长时间（n=1000000需要几十分钟）
于是老师要求我们优化一下算法，请教大神提一点意见（只需要有什么思路即可，代码当然是自己写。。。）
题目
已知m，n 为大于0 的正整数: m, n 在1 到k 之间,且满足（m2-mn-n2）2=1。给定一个k 值，则求满足上述等式的m 和n，使得m2+n2 的值最大。
例如 k=4, 则有m=3，n=2 满足了等式(32-3×2-22)2=1，且小于4 的m2+n2=32+22=13
是最大的。
随着K 取值较大（例如可以使用一组数据进行测试，例如k=1000，10000，100000，……），你就会发现程序运行速度开始变慢，那么有什么方法可以提升程序的运行速度？请改写你的程序，验证你的方法，以提升程序运行速度
附上最白痴的算法代码，能力有限
ps据说可用时间复杂度。。。求大神解释

1. #include <stdio.h>
   
2. #include <math.h>
   
3. int main(void)
   
4. {
   
5.     int repeat, ri;
   
6.     int k,m,n,z;
   
7.     int m0,n0,z0;
   
8. 
   
9.     scanf("%d", &repeat);
   
10.     for(ri = 1; ri <= repeat; ri++){
    
11.         scanf("%d",&k);
    
12.         z0=m0=n0=0;
    
13.         for(m=1;m<=k;m++){
    
14.             for(n=1;n<=k;n++){
    
15.                 if(pow((m*m-m*n-n*n),2)==1){
    
16.                    z=m*m+n*n;
    
17.                    if(z>z0){
    
18.                    z0=z;
    
19.                    m0=m;
    
20.                    n0=n;
    
21.                    }
    
22.                 }
    
23.             }
    
24.         }
    
25.         printf("It has the biggest result of (m^2+n^2) which is %d, when m=%d, n=%d.\n",z0,m0,n0);
    
26.     }     
    
27. }
    

复制代码

loms126

记得以前看过一个分枝定界法解整数规划问题的，可惜太久了，记不清了。可以对条件加点数学处理简化中间的判断、缩减不必要的循环来改算法吗？

wyj915752168

loms126 发表于 2013-3-5 20:41
记得以前看过一个分枝定界法解整数规划问题的，可惜太久了，记不清了。可以对条件加点数学处理简化中间的判 ...

不知“时间复杂度”是什么，听说直接限制变量范围可以加快N百倍速度。。。我先自己查查吧

thelord

从算法上优化是最高效的，应该先进行数学推导，可以省去很多无效情况
条件：（m^2-mn-n^2）^2=1（1 < m, n < k）
目标：m^2+n^2 的值最大

条件等同于方程 m^2-mn-n^2=±1
显然，n^2 = m^2-mn ±1 ==> m^2+n^2 = m^2+m^2-mn ±1 = m(2m-n) ±1

所以，m=k-1，n=2时，可得最大值 2(k-1)(k-2)+1

呵呵，做个乘法就行。看看推导对不对，好久没做数学了

utraedit

不知你是不说的这个：http://hi.baidu.com/xun1573/item/31b4983c2358ab617d034b7f

可是我觉得整体看待能减少很多乘法运算次数，加快速度，即
吧a=m^2-1/2mn和b=n^2+1/2mn看成整体,  则题目变为
(a-b)^2=1求a+b

wyj915752168

utraedit 发表于 2013-3-5 21:08
不知你是不说的这个：http://hi.baidu.com/xun1573/item/31b4983c2358ab617d034b7f

可是我觉得整体 ...

问题是定义的a,b 不一定是整数，因为有1/2。。。所以变量范围扩大了，也不能最后再处理回整数m,n

数据流谷雨

说一下简单的思路，关键是这个等式（m2-mn-n2）2=1，当m确定时，要使等式成立，n的值最多有两种情况，所以当满足这两种情况时，for循环可以break或者continue
这只是初步是看法，我还没试验过

loms126

wyj915752168 发表于 2013-3-5 20:51
不知“时间复杂度”是什么，听说直接限制变量范围可以加快N百倍速度。。。我先自己查查吧

约束条件(m^2-n*m-n^2)^2=1可化为两个二次方程：m^2-n*m-n^2=1, m^2-n*m-n^2=-1。以n为常数，m为自变量，前者的两根为m=(n+sqrt(5*n^2+4))/2, m=(n-sqrt(5*n^2+4))/2,  后者的两根为m=(n+sqrt(5*n^2-4))/2, m=(n-sqrt(5*n^2-4))/2。 m必须为整数， sqrt(5*n^2+4)和sqrt(5*n^2-4)必为有理数，这两个限定可通过单独loop  n的值判断，与m无关。当n>1时，(n-sqrt(5*n^2+4))/2<0,  (n-sqrt(5*n^2-4))/2<1, 只剩下两个m的解。然后套用m的值得m^2+n^2的大小，循环n from 1 to k, 得到m^2+n^2极大值。
伪代码
n=1 时  m=2, m=1, 存到个temp变量里。(太伪了…)
for n=2 to k
        temp_a=(5*n^2+4)
        temp_b= (5*n^2-4)
        if sqrt(temp_a)==temp_a     ;;也可以用mod = 0写
                m=(n+sqrt(5*n^2+4))/2
                if m 是整数
                        取m^2+n^2的值
                endif
        endif
        if sqrt(temp_b)==temp_b     ;;也可以用mod = 0写
                m=(n+sqrt(5*n^2-4))/2
                if m 是整数
                        取m^2+n^2的值
                endif
        endif
endfor

thelord

wyj915752168 发表于 2013-3-5 20:51
不知“时间复杂度”是什么，听说直接限制变量范围可以加快N百倍速度。。。我先自己查查吧

4楼有推导，看看对不对

wyj915752168

thelord 发表于 2013-3-5 21:06
从算法上优化是最高效的，应该先进行数学推导，可以省去很多无效情况
条件：（m^2-mn-n^2）^2=1（1 < m, n ...

哎。。。可惜不对啊。。。因为 m^2-mn-n^2=±1条件约束。。。不过还是谢谢你