등차수열의 합을 C++ 프로그래밍 하는 3가지 방법

 

이번 글을 통해 배워갈 내용

1.  등차수열의 정의
2.  등차수열을 if문으로 프로그래밍
3.  등차수열을 재귀문으로 프로그래밍
4.  등차수열을 공식으로 프로그래밍

---

 

등차수열의 정의

 

연속하는 두 항의 차이가 모두 일정한 수열

 

---

 

이와 같이 두 항의 차이가 일정한 수열을 등차수열이라 하며

 

n번째 값을 공식으로

 

a(n) = a(1) + (n -1) * d

 

로 표현 할 수 있습니다.

 

a(n) : n번 째 a

a(1) : 첫번째 a

d : 각 수열의 차

n : 수의 갯수

 

그렇다면 n번째 값까지의 합은 어떻게 구할수 있을까요?

 

1부터 10 까지의 수를 모두 더할 경우 1+2+3+4+5+6+7+8+9+10 = 55입니다.

 

이를 구하는 방법을 설명하겠습니다.

 

자 그럼 이제 3가지 방법으로 프로그래밍 해보겠습니다.

 

입력은 모두 10을 넣어보겠습니다.

 

---

 등차수열을 for문으로 프로그래밍

 

int findArithmeticSum1(int n)
{
    int sum = 0;
    for(int i=0; i<=n; i++)
    {
        sum += i;
    }
    return sum;
}

 

 

결과값 : 55

복잡도는 O(n)인것을 확인 할수 있습니다.

 

---

 등차수열을 재귀문으로 프로그래밍

 

int findArithmeticSum2(int n)
{
    if(n == 0)
    {
        return 0;
    }
    
    return findArithmeticSum2(n-1)+n;
}

 

결과 : 55

복잡도는 O(n)인것을 확인 할수 있습니다.

 

---

 등차수열을 공식으로 프로그래밍

 

int findArithmeticSum3(int n)
{
    return (n*(n+1)/2);
}

 

결과 : 55

복잡도는 O(1)인것을 확인 할수 있습니다.

---

전체 코드

#include <iostream>

using namespace std;

int findArithmeticSum1(int n)
{
    int sum = 0;
    for(int i=0; i<=n; i++)
    {
        sum += i;
    }
    return sum;
}

int findArithmeticSum2(int n)
{
    if(n == 0)
    {
        return 0;
    }
    
    return findArithmeticSum2(n-1)+n;
}

int findArithmeticSum3(int n)
{
    return (n*(n+1)/2);
}


int main()
{
    cout<<findArithmeticSum1(10) << endl;
    cout<<findArithmeticSum2(10) << endl;
    cout<<findArithmeticSum3(10) << endl;
    return 0;
}

---

결론

공식이 있다면 공식을 이용하는게 제일 편하고

 

가독성은 제기준으로 재귀가 공식다음으로 편했습니다.

 

시간복잡도 외에 

공간복잡도를 생각해보면

for문이 재귀보다 편한것 같기도 합니다.

 

간단한 공식에도 여러 생각이 드네요 ㅎㅎ

 

이상입니다.

 

---

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

https://ko.wikipedia.org/wiki/%EB%93%B1%EC%B0%A8%EC%88%98%EC%97%B4

 

C++ Primer