确定算法的执行次数

debugcn 发表于 Dev

帕特里克（Patryk Wojcieszak）

我有这样的算法。

for(int i=1; i<=n; i++){
  for(int j=1; j<=2*n; j=j+2)
  {
     for(int k=i; k<=j; k++)
     {
        instr;
     }                                  
  }
}

我需要找到一个确定“ instr”指令将执行多少次的公式。

我写的。但是我的价值观不正确。例如对于n = 4，“ instr”将被执行43次，但是我从总和中得到40。

我哪里搞砸了？

梦境崩溃

我哪里搞砸了？

您应用总和的方式。您的公式是正确的。编码：

for(int i=1; i<=n; i++){
  for(int j=1; j<=2*n; j=j+2)
  {
     for(int k=i; k<=j; k++)
     {
        instr;
     }                                  
  }
}

在语义上与：

for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++)
    {
        for(int k=i; k<=2*j - 1; k++)
        {
           count++;
        }
    }
}

实际运行类似：

public class Main {
    public static void first_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=2*n; j=j+2)
            {
                for(int k=i; k<=j; k++)
                {
                    count++;
                }
            }
        }
        System.out.println("First loop "+count);
    }

    public static void second_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
            {
                for(int k=i; k<=2*j - 1; k++)
                {
                    count++;
                }
            }
        }
        System.out.println("Second loop "+count);
    }


    public static void main(String[] args)
    {
       for(int n = 1; n < 10; n++){
           System.out.println("FOR N="+n);
           first_loop(n);
           second_loop(n);
       }
    }
}

会告诉您该公式是正确的：

输出：

FOR N=1
First loop 1
Second loop 1
FOR N=2
First loop 6
Second loop 6
FOR N=3
First loop 19
Second loop 19
FOR N=4
First loop 43
Second loop 43
FOR N=5
First loop 82
Second loop 82
FOR N=6
First loop 139
Second loop 139
FOR N=7
First loop 218
Second loop 218
FOR N=8
First loop 322
Second loop 322
FOR N=9
First loop 455
Second loop 455

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。