36 - 수열의 일반항과 점화식, 등차 수열, 피보나치 수열 - 추가 문제 풀기

#등차수열

공차가 !2*이고 첫째 항이 !a_0*인 등차수열 !a_n*의 일반항을 구하면

!a_n = d(n-1)+a_0*

 

따라서 !a = [1,2,3,5,7,9,...]*인 수열에서 일반항은

!an = 2n-1*

즉, !n*에 대한 일차함수로 나타낼 수 있다. 

 

!n=100* 일 때

n = 100
a_n = 2*n -1
print(a_n)
>>> 199

 

1부터 10까지의 항을 구하면 

for n in range (1, 10+1):
  a_n = 2*n -1
  print(a_n)
 >>> 
1
3
5
7
9
11
13
15
17
19

※ 주의! print가 for in 에 들어가 있어야 한다!

 

1번 째 ~ 10번 째 항이 들어가 있는 리스트를 구하면

a = []
for n in range (1, 10+1):
  a_n = 2*n -1
  a.append(a_n)
print(a)
>>> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 

그런데, 이렇게 되면 !a_1 = 1*이지만(1-index) a[0] = 1으로 맞지 않음. 그래서 [0]에 의미 없는 데이터를 넣어서 index를 맞춰주기도 한다.

a = ["None"]
for n in range (1, 10+1):
  a_n = 2*n -1
  a.append(a_n)
print(a)
>>> ['None', 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 

#점화식 

: 이전 항을 기반으로 다음 항을 만드는 방법

 

eg) !a_n = a_{n-1} + 2*

!a_1  = 1*일 때, 

a = [None]
for n in range (1, 10+1):
  if n == 1 :
    a_n = 1
  else :
    a_n = a[n-1] + 2
  a.append(a_n)
print(a)
>>> [None, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 

#특정 길이의 리스트 만들기

: 파이썬은 append 등을 이용해서 리스트의 크기를 늘리는 작업이 느려서 항이 많을 때, 위의 코드와 같이 짜는 것이 좋지 않음.

‣ 그래서 처음부터 리스트를 만들어 두고 시작함

n = 100
a = [None]*(n+1)
for n in range (1, n+1):
  if n == 1 :
    a[1] = 1
  else :
    a[n] = a[n-1] + 2
print(a)
>>> [None, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199]

※ 수학의 항의 위치와 개발의 인덱스를 일치시키기 위해 [0]에 None을 넣고 101개의 요소를 만듦.

 

#동적계획법

: 용어 기억해두기

: 반복문으로 이전 항의 값으로 다음 항의 값을 구해내는 방법 /  혹은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법

 

#피보나치 수열

!F_1 = F_2 = 1*

!F_n =* !F_{n-1} +* !F_{n-2}*

n = 10
a = [None]*(n+1)
for n in range (1, n+1):
  if n == 1 or n == 2:
    a[n] = 1
  else :
    a[n] = a[n-1] + a[n-2] 
print(a)
>>> [None, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

 

---

 

구글에 정수열 목록이라고 입력해서 나오는 수열을 코드로 만들어보는 연습을 해보자!

 

---

replit

https://replit.com/@wh3308/ilbanhang-jeomhwasig-deungcasuyeol-pibonacisuyeol#main.py