연속된 수 덧셈 빨리하기..

다 아는것 같은데  그냥 한번 정리해 봅니다.

1. 1에서 100까지 더하기는?

  1.1 단순한 방법
   void __fastcall TForm1::Button3Click(TObject *Sender)
   {
       int sum=0;
       for(int i=1;i<=100;i++)
           sum+=i;
       ShowMessage(sum);
   }
   가장 단순한 방법은 위와같이 for문을 돌려서 구하면 되겠죠!

  1.2 빨리 더하기..
      간단하게 빨리하려면  다음과 같이 하면 됩니다.  
      sum=(100*101)/2 ;
     
     왜그럴까요?
     아래와같이 숫자를 나열해보면      
    
     -------------------------------
     1   +   2 +   3 + ... + 50 +
     100 +  99 +  98 + ... + 51
     -------------------------------
   = 101 + 101 + 101 + ... + 101

     101의 갯수가 50개가 되죠?
     즉 101*50이 됩니다.
    
     숫자 n에 대하여 서술하면
 
     sum = n * (n+1 ) / 2 가 됩니다.


2.  m 에서 n까지 더하기는?   ( 조건 m<n, m>1 )

    위에 1.2를 응용해서 아래와 같이 정리될것입니다.
   
        sum = n! - (m-1)!
        = n * (n+1 ) / 2     - m * (m-1 ) / 2 ;

       예) 11부터 100까지 덧샘은?
          sum = 100*101/2  -  10*11/2   ;

3. 그럼 1에서 n까지  m의 배수만 더하기(예 1~100까지 3의 배수만 더하기)는? 
    (조건 m < n )

    보통 아래와같이 계산하겠죠?
    int sum=0;
    for(int i=3;i<=100;i+=3)sum+=i;

    근데 이것도 1.2의 식을 응용해서 아래와 같이 정리할 수 있습니다.
    max = n - n % m ;  //m의 배수중 제일큰 수   
    sum =(max*(max+1)+max*(m-1))/(2*m);

    mas = 100 - 100 % 3 = 99 ;
    sum =(  99 * 100  +  99 * (3-1) ) /( 2 * 3 )      ;
    쪼금 식이 복잡한데 잘 풀어보면 금방 이해하실수 있을것 입니다.


   왠만한 경우에 그냥  for문 돌려도 별문제 없습니다.


그럼..