실습_2. 수열_수학적 귀납법
Updated:
실습
등차수열
각 항마다 일정한 간격으로 더해지는 수열을 등차수열이라고 부릅니다. 등차수열의 첫번째 항을 초항이라고 부르며 일정하게 더해지는 값은 공차라고 부릅니다.
등차수열의 초항과 공차가 주어졌을 때, 이 등차수열의 n번째 항을 구하는 함수를 작성해 봅시다.
- 입력
a: 정수
d: 정수
n: 자연수
- 출력
a를 초항, d를 공차로 가지는 등차수열의 n번째 항
- 실행 결과
>> arithSeq(1, 2, 3)
5
>> arithSeq(9, -3, 2)
6
>> arithSeq(-5, 1, 4)
-2
def arithSeq(a, d, n):
# 등차수열의 초항 a와 공차 d가 주어졌을 때
# 이 등차수열의 n번째 항을 구하는 함수를 작성하고, 이를 반환해봅시다.
return a + (n-1) * d
print(arithSeq(1, 2, 3))
등비수열
매 항마다 일정한 값이 곱해지는 수열을 등비수열이라고 부릅니다. 등비수열의 첫항을 초항이라부르고 곱해지는 일정한 값을 공비라고 부릅니다.
등비수열의 초항과 공비가 주어졌을 때, 이 등비수열의 n번째 항을 구하는 함수를 작성해 봅시다.
- 입력
a: 정수
r: 0이 아닌 실수
n: 자연수
- 출력
a를 초항, r를 공비로 가지는 등비수열의 n번째 항
- 실행 결과
>> geoSeq(1, 2, 3)
4
>> geoSeq(3, 3, 4)
81
>> geoSeq(32, 0.5, 3)
8.0
def geoSeq(a, r, n):
# 등비수열의 초항 a와 공비 r가 주어졌을 때
# 이 등비수열의 n번째 항을 구하는 함수를 작성하고, 이를 반환해봅시다.
return a * r**(n-1)
print(geoSeq(1, 2, 3))
계차수열
수열 a(n)이 있을때 매 항마다 더해지는 값들이 어떤 수열을 이루는 경우 더해지는 수열 b(n)을 계차수열이라고 부릅니다.
a_n=a+b_1+b_2+…+b_{n-1}
수열 a(n)이 초항이 a이고 b(n)을 계차수열로 가지는 수열이라 할 때, 수열 a(n)의n번째 항을 구하는 함수를 작성해 봅시다.
- 입력
a: 정수
b: 정수 리스트
n: b의 길이보다 작거나 같은 자연수
- 출력
a를 초항, b를 계차수열로 가지는 수열의 n번째 항
- 출력 결과
>> seqDiff(1, [1, 2, 3, 4, 5], 3)
4
>> seqDiff(0, [2, 4, 6, 8, 10], 5)
20
>> seqDiff(8, [1, -2, 4, -8, 16], 4)
11
def seqDiff(a, b, n):
# 초항 a와 계차수열 b로 이루어진 수열 An이 주어졌을 때
# 수열 An의 n번째 항을 구하는 함수를 작성하고, 이를 반환해봅시다.
return a + sum(b[:n-1])
print(seqDiff(1, [1, 2, 3, 4, 5], 3))
급수
수열 a(n)의 n항까지의 합을 주로 S(n)과 같이 표기합니다.
주어진 수열의 n항 까지의 합 S(n)을 구하는 함수를 작성해봅시다.
- 입력
a: 정수 리스트
n: a의 길이보다 작거나 같은 자연수
- 출력
수열 a의 n항 까지의 합
- 출력 결과
>> series([1, 2, 3, 4, 5], 5)
15
>> series([2, 4, 6, 8, 10], 4)
20
>> series([-1, 2, -4, 8, -16], 4)
5
def series(a, n):
# 수열 a의 n번째 항까지의 합을 구하는 함수를 작성하고, 이를 반환해봅시다.
return sum(a[:n])
print(series([1, 2, 3, 4, 5], 5))
점화식
n에 의존하지 않고 항들 간의 관계로 수열을 나타내는 식을 점화식이라고 부릅니다.
초항 a와 상수 p, q가 주어졌을 때 다음의 점화식을 만족하는 수열의 n번째 항을 구하는 함수를 작성해 봅시다.
- 입력
a: 정수
p: 정수
q: 정수
n: 자연수
- 출력
위 점화식을 만족하는 수열의 n번째 항
- 실행 결과
>> recurrSeq(1, 2, 3, 5)
61
>> recurrSeq(5, 3, 1, 4)
148
>> recurrSeq(-5, -1, 2, 5)
-5
def recurrSeq(a, p, q, n):
# 주어진 점화식(p*a + q)을 만족하는 수열의 n번째 항을 구하고, 이를 반환해봅시다.
for i in range(n-1):
a = p*a+q
return a
print(recurrSeq(1, 2, 3, 5))
분할정복
분할정복법은 바로 해결하기 어려운 하나의 큰 문제를 비교적 해결하기 쉬운 여러 개의 문제로 쪼개어 해결하는 문제입니다. 재귀함수를 이용하여 쉽게 해결할 수 있을 때까지 문제를 쪼개게 됩니다.
분할정복법을 사용하여 리스트를 오름차순으로 정렬하는 알고리즘을 완성해 봅시다.
- 입력
a: 중복 되지 않는 정수 리스트
- 출력
오름차순으로 정렬된 리스트
- 실행 결과
>> divSort([2, 3, 1])
[1, 2, 3]
>> divSort([2,4,3,5,6,1])
[1,2,3,4,5,6]
>> divSort([40, 20, 50, 10, 30])
[10, 20, 30, 40, 50]
-
이렇게 해보세요!
-
To-do을 채워서 정렬함수를 완성해보세요.
-
a의 길이가 2일 때는 부등호를 이용해서 정렬해보세요.
-
a의 길이가 길때는 원소 하나 m를 기준으로 m보다 작은 원소의 리스트 d1과 m보다 큰 리스트 d2로 분리해보세요.
-
-
Tip
- 이러한 방법을 퀵 정렬(quick sort)라고 합니다.
def divSort(a):
# 리스트의 길이가 1보다 작거나 같은 경우
if len(a) <= 1:
return a
# 리스트의 길이가 2인 경우
elif len(a) == 2:
if a[0] > a[1]:
a[0],a[1] = a[1],a[0]
return a
# 리스트의 길이가 2보다 큰 경우
else:
l = len(a)
# 기준이 되는 요소를 하나 정한다
m = a[l//2]
d1 = []
d2 = []
for i in a:
if i<m:
d1.append(i)
if i>m:
d2.append(i)
# To-do: m을 기준으로 2개의 리스트를 나눈다
pass
s1 = divSort(d1)
s2 = divSort(d2)
return s1 + [m] + s2
print(divSort([2, 3, 1]))
미션
이자 계산
수열 문제 중에서 실생활과 가장 연관이 있는 예 중 하나는 이자 계산입니다. 이자가 붙는 방식에는 단리와 복리가 있는데, 이 중 복리는 이자 계산 시 (원금+이자)에 이자가 붙게 되어 이자가 빠른 속도로 늘어납니다.
가령 원금이 100만원이고 연 이자율이 1%라면 1년 후에는 원금 100만원에 이자 1만원, 2년 후에는 101만원에 이자가 1.01만원이 붙어 총 이자는 1 + 1.01 = 2.01만원이 됩니다.
원금 a와 연 이자율 r이 주어졌을 때, n년 후의 총 이자 금액을 계산하는 함수를 작성해 봅시다.
- 입력
a: 자연수
r: 0이 아닌 실수
n: 자연수
- 출력
원금 a원, 연 이자율 r일 때 n년후 총 이자의 금액.
- 실행 결과
>> interest(1000000, 0.01, 2)
20100
>> interest(1000000, 0.01, 4)
40604.01
>> interest(10000, 0.5, 3)
23750
def interest(a, r, n):
# 등비수열을 통해 n년 후의 금액이 어떻게 되는지 계산해봅시다.(원금 * (1+ 연이자율)^n)
# 총 금액에서 원금을 뺀 금액(이자)을 계산한 후, 이를 반환해보세요.
return a * (1+r)**n - a
print(interest(1000000, 0.01, 2))
재귀함수
수열에서의 점화식은 프로그래밍에 있어 재귀함수를 작성하는 것과 비슷합니다. 함수 안에서 또 다시 함수를 부르는 모양이 마치 이전 항을 사용하여 다음 항을 구하는 것과 같습니다.
점화식 문제를 for문을 사용하지 않고 재귀함수를 사용하여 풀어 봅시다.
a(1) = a a(n+1) = pa(n) + q
- 입력
a: 정수
p: 정수
q: 정수
n: 자연수
- 출력
위 점화식을 만족하는 수열의 n번째 항
- 실행 결과
>> recurrSeq2(1, 2, 3, 5)
61
>> recurrSeq2(5, 3, 1, 4)
148
>> recurrSeq2(-5, -1, 2, 5)
-5
def recurrSeq2(a, p, q, n):
# [실습5]와 달리 반복문을 사용하지 않고 재귀함수를 사용하여
# 점화식을 구현하는 코드를 작성해보세요!
x = 0
if n == 1:
return a
else:
x = recurrSeq2(a*p+q,p,q,n-1)
return x
print(recurrSeq2(1, 2, 3, 5))
세제곱의 합
다음과 같이 정의된 수열 a(n)의 n항까지의 합 S(n)을 구하는 함수를 작성해 봅시다.
a(n)=1,8,27,64,…,k^3,…
- 입력
n: 자연수
- 출력
수열 a(n)의 n항까지의 합
- 실행 결과
>> cubeSum(3)
36
>> cubeSum(5)
225
>> cubeSum(10)
3025
def cubeSum(n):
# 1부터 n까지의 세제곱을 모두 합하는 함수를 작성하고, 이를 반환해보세요.
Sum = 0
for i in range(1,n+1):
Sum+=i**3
return Sum
print(cubeSum(3))
피보나치 수
피보나치 수는 앞의 두 항을 더하여 새로운 항을 만드는 수열입니다.
a_{n}=1,1,2,3,5,8,13,21,… a n =1,1,2,3,5,8,13,21,…
점화식으로 다음과 같이 나타낼 수 있습니다.
a(1)=1
a(2)=1
a(n+2)=a(n+1)+a(n)
피보나치 수열의 n번째 항을 구하는 함수를 작성해 봅시다.
- 입력
n: 자연수
- 출력
피보나치 수열의 n번째 항
- 실행 결과
>> fibonacci(1)
1
>> fibonacci(3)
2
>> fibonacci(5)
5
def fibonacci(n):
# 문제의 요구사항에 맞추어 1번과 조건문(if)과 3번 반복문(for)을 사용해서
# 피보나치 수를 구하고, 이를 반환해보세요.
if n == 1:
return 1
if n == 2:
return 1
a = 1
b = 1
for i in range(n-2):
tmp = a
a = b
b = tmp + a
return b
print(fibonacci(5))
피보나치 수 2
피보나치 수는 앞의 두 항을 더하여 새로운 항을 만드는 수열입니다.
a(n)=1,1,2,3,5,8,13,21,…
어떤 수 n이 주어졌을 때 n을 넘는 가장 작은 피보나치 수열은 몇 번째 항인지 구하는 함수를 작성해 봅시다.
- 입력
n: 자연수
- 출력
n을 넘는 가장 작은 피보나치 수열의 항 번호
- 실행 결과
>> fibonacci2(2)
4
>> fibonacci2(4)
5
>> fibonacci2(10)
7
def fibonacci2(n):
# [미션4]에서 작성한 함수를 활용해서 n을 넘는 가장 작은 피보나치 수열의 항 번호를 찾아 반환해보세요.
a = 1
b = 1
cnt = 2
while True:
tmp = a
a = b
b = tmp+a
cnt+=1
if b > n:
return cnt
print(fibonacci2(4))
Leave a comment