수열

알고리즘 : 어떤 문제를 해결하는 논리적인 방법 

순서도(플로우차트) : 알고리즘을 순서대로 처리할 수 있도록 기호를 이용해 그림으로 표현한것 

 

머릿속으로 잘안그려지는 것만 순서도로 작성해보자..  

1번문제)

1+2+3+ .... + 100 까지의 합계를 구하는 순서도와 코드작성 

 

1.변수 두개 필요 : 1씩증가되는 변수(i),누적값이 저장되는 변수(sum) 1

2.i가 100되면 총합계를 출력함 

1 2 3 4 5 6

int i=0,sum=0;                 do{             i++;             sum += i;         }while(i<100);                 System.out.println(sum);

cs

2번문제)

1+3+5+...+99 합계 구하기 

 

1.변수 i = -1 , sum = 0 선언 

2.홀수니까 2씩증가 i = i + 2(i += 2) 

3.i는 99까지 증가 

 

1 2 3 4 5

int sum = 0;                 for(int i=1;i<100;i+=2) {             System.out.println(i);             sum += i;         }

cs

3번문제)

1-2+3-4+...-100 까지의 합계 구하기 

 

SW(스위칭 변수사용 - 두가지 작업을 한번씩 번갈아 가면서 사용할때씀) 

1. SW - 0일경우 + ,1일경우 - 

1 2 3 4 5 6 7 8 9 10 11 12 13

int i=0,sum=0,sw=0;                  do {             i++;             if(sw == 0) {                 sum += i;                 sw = 1;             }else {                 sum -= i;                 sw = 0;             }                      }while(i<100);

cs

2.스위칭(SW)변수 미사용시 

방법1)

- 2로 나눈 나머지가 1일경우는 홀수 + , 나머지 0 짝수 - 

1 2 3 4 5 6 7 8 9 10 11

int j=0;         int i=0;           do {             i++;             if(i % 2 == 1) {                  j += i;             }else {                 j -= i;              }         }while(i<100);

cs

방법2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int sum=0;             int i=0;         while(true) {             i++;             sum += i;             if(i>=99) {                 System.out.println("총합"+sum);                 break;             }else {                 i++;                 sum -= i;             }         }

cs

4번문제)

-(1/2)+(2/3)-(3/4)+...-(99/100) 까지의 총합을 구해라 

 

1.분자(i)만 99까지 1씩계속 증가시킴

2.분자가 짝수일때 + 홀수일때 -

3. 분자 / 분자 + 1  -> i / i+1 (수열의 각행)  

 

1 2 3 4 5 6 7 8 9 10

float i = 0;         float sum = 0;         do {             i++;             if(i % 2 == 0) {                 sum += (i/(i+1));             }else {                 sum -= (i/(i+1));             }         }while(i<99);

cs

5번문제)

1+2+4+7+11+16+.. 순서로 나열되는 N번째의 항까지의 합계를 구하라 

 

1.3개의 변수 필요(n번째 까지 증가될 변수(i), 1247씩 증가되는 변수(j), 누적합 변수 - sum) 
2.초기값선언  i=0,j=1,sum=1

 

방법1) 첫번째 항부터 구함 sum = 0 초기화하고 i를 20까지 증가시킴 

1 2 3 4 5 6 7

int i=0,j=1,sum=0;                  do {             i++;             j = j + i -1;             sum += j;         }while(i<20);

cs

방법2) 첫번째 항을 미리 구했기 때문에 sum =1 초기화하고 i를 19까지 증가시킴 

1 2 3 4 5 6 7

int i=0,j=1,sum=1;                  do {             i++;             j = j + i;             sum += j;         }while(i<19);

cs

6번문제)

-1+2-4+7-11+..순서로 나열되는 N번째의 항까지의 합계를 구하라 

 

1.5번문제에서 1247씩 증가하면서 부호도 바뀜 sw 변수 추가

방법1)

1 2 3 4 5 6 7 8

int i=0,j=1,sum=-1,sw=-1;              do {             i++;             j += i;             sw = sw * -1;             sum = sum + (j * sw);         }while(i<19);

cs

방법2) .. 방법1이 더 효율적인 코드 

1 2 3 4 5 6 7 8 9

int i=0,j=1,sum=-1,sw=1;              do {             i++;             j += i;                         sum = sum + (j * sw);             if(sw == 1) sw = -1;             else sw = 1;         }while(i<19);

cs

7번문제)

1!+2!+3!+..+10! 순서로 나열되는 10번째 항까지의 합구하기 

 

1.3개의 변수 필요(1씩증가하는 변수(i),각팩토리얼의 항(j),각팩토리얼을 더한 총합(sum) )

1 2 3 4 5 6 7

int i=0,j=1,sum=0;                  do {             i++;             j = j * i;             sum += j;         }while(i<10);

cs

!(팩토리얼 함수) 

예시) N개의 책을 순서대로 나열하는 방식 

A,B,C 총 3개의 책을 나열하는 방식의 총 가짓수는? 

-> 첫번째 위치에 책을 배열하는 방법 N(3)가지 (A,B,C)

-> 두번째 위치에 책을 배열하는 방법 N-1(2)가지 (A-B와C B-A와C C-A와B)

-> 세번째 마지막 위치에 책을 배열하는 방법 N-2(1)가지 (A or B or C) 

-> 3 * 2 * 1 = 6가지  N(N-1)(N-2) 마지막으로 한가지가 남을때까지 계속함 

참고사이트 : ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/the-factorial-function

 

8번문제) 

** 피보나치 수열 **

피보나치 수열 : 첫번째항과 두번째항을 더해서 세번째항을 만들고 두번째항과 세번째항을 더해서 네번째항을 만드는 방법으로 계속해서 다음항을 만들어 나가는 방법 

1+1+2+3+5+8+13+... 순서로 나열되는 n번째의 항까지의 합을 구하라 

 

1. A,B(수열의 각항을 계산하기위한변수) ,C(수열의 각항) , cnt(항의개수) , sum(합계)
2. A=1,B=1 로 수열의 첫항과 두번째항을 나타냄 sum=2 로 첫항+두번째항 
3. 첫번째항과 두번째항을 더해서 C(세번째항)만듬 
4. 과거까지의 총합계를 계산 
5. A -> B(두번째항을 넣음) , B -> C(세번째항을넣음) 

6. 항의개수 1증가 
7. 3번으로 돌아가서 두번째항(A)와 세번째항(B)을 더해 네번째항(C) 계산  

 

방법1) 

1 2 3 4 5 6 7 8 9

int a=1,b=1,c=0;         int sum=2,cnt=0;                 do {             c = a + b;             sum += c;             a = b;             b = c;             cnt++;         }while(cnt < 18);

cs

방법2) (cnt < 18) 0부터 17번째까지니까 총 18번째항 + 기존항2개  -> 20번째까지 항을 구할수있음 

1 2 3 4 5 6 7 8 9

int a=1,b=1,c=0;         int sum=2;                          for(int cnt=0;cnt<18;cnt++) {             c = a + b;             sum += c;             a = b;             b = c;         }

cs