0

次のコードの場合：

 s = 0 ;  
 for(i=m ; i<=(2*n-1) ; i+=m)  {  
      if(i<=n+1){ 
        s+=(i-1)/2 ; 
      }  
      else{ 
        s+=(2*n-i+1)/2 ; 
      }    
 }

O(n) コードの複雑さをからに変更したいと思いO(1)ます。だから私はforループを排除したかった。ただし、合計には次のsような値が格納されるため、ループを削除するには、各または(i-1)/2の(2*n-i+1)/2フロア値を計算するのが面倒 です。フロアの合計で間違った式を導き出した可能性があるため、そうすることは非常に困難になりました。複雑さをからに変更するのを手伝ってくれませんか。または、このフロアの合計を手伝ってください。複雑さを軽減する他の方法はありますか？はいの場合...それではどのように？(i-1)/2(2*n-i+1)/2O(n)O(1)

4

2 に答える 2

2

mこれに対する私のアプローチは、最初にとのさまざまな値に対して生成された値をアサートする特性テストを作成しn、次にリファクタリングを開始することです。

メインループには、途中（if(i<=n+1)選択）に基づいてロジックが変更されているため、最初にそれに基づいて2つのループに分割します。

次に、結果として得られる各ループで、主にi偶数か奇数かによって計算が変化します。それぞれをさらに2つのループに分割すると、フロアの計算がわかりやすくなります。または、これらのループを別の方法で単純化できる繰り返し値のパターンが表示される場合があります。

結果として得られる各ループは、等差数列の合計に似ている可能性が高いため、ループをまったく必要としない閉じた形式の計算に置き換えることができる可能性があります。

このパスに沿って進むときに、計算の一部を関数に抽出するためにリファクタリングすることもできます。それらを抽出するときに、これらの特性テストを記述します。

続行しながらすべてのテストを実行し続けると、これを単純な計算の合計に減らすことができる可能性があります。これは、単純な古い算術によってさらに減らすことができます。

于 2012-05-05T16:19:15.943 に答える
2

ドン・ロベイが言ったように、あなたの問題には昔ながらの算術的解決策があります。iの最初の値に対してそれを行う方法を示しましょう。

*編集2：下部のコード*

    for(int i=m ; i<= n+1 ; i+=m)//old computation
          s+=(i-1)/2 ;


    int a = (n+1)/m; // maximum value of i
    int b = (a*(a+1))/2; //
    int v = 0;
    int p;
    if(m % 2 == 0){
        p = m/2;
        v = b*p-a; // this term is always here
    }
    else{
        p = (m - 1)/2;
        int sum1 = ((a/2)*(a/2 +1))/2; 
        int sum2 =  (((a-1)/2)*((a-1)/2 +1))/2;  

        v = b*p -a ;// this term is always here
        v+= sum1 + a/2; //sum( 1 <= j <= a )(j-1), j pair
        v+= sum2; //sum( 1 <= j <= a )(j-1), j impair
    }
    System.out.println( " Are both result equals ? "+ (s == v));

どうすれば思いつくことができますか？私は取る

 for(i=m ; i<= n+1 ; i+=m)
      s+=(i-1)/2 ;

変更します

 for(j=1 ; j*m <= n-1 ; j++)
     s+=(j*m-1)/2 ;

ポーズしa=Math.floor(n+1/m)ます。3つのケースがあります：

  1. mがペアの場合、ループの内部はですs+= p*j。結果は

     b(a*(a+1))/2 -a

  2. mは障害であり、イテレータjはペアです

  3. mが損なわれ、イテレータjが損なわれるmが損なわれると、次のように記述できm = 2p + 1、ループの内部は次のようになります。

     s+= p*j + (j-1)/2

p*jは以前と同じですが、jが常にペアであるか、jが常に損なわれていると仮定し、両方の値を合計することによって、除算を破る必要があります。

計算する必要がある次のループは

 for(int i=a+1 ; i<= (2*n-1) ; i+=m)// a is (n+1)/m
    s+=(2*n-i+1)/2;

これはと同じです

 for(int i=1 ; i<= (2*n-1)-a ; i+=m)
    s+= (2n-a)/2 - (i-1)/2;

このループは最初のループに似ているので、やるべきことはあまりありません...確かにこれは退屈です。

于 2012-05-05T18:29:30.687 に答える