This article is Kencho-san's book, which contains many explanations of competitive programming, ** Train your problem-solving skills! Algorithms and data structures(けんちょんさん本)**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。
On this page, we will introduce the contents of Chapter 4! Please forgive me if there are any bugs.
See the following pages for links to other chapters. [Table of Contents Page] https://qiita.com/KevinST/items/002676619a583754bf76
Basic recursion.
code4-1.py
def func(N):
if N == 0:
return 0
return N + func(n-1)
Since only the function part is created, there is no input / output.
This is an example of using code4.1 (N = 5)
code4-2.py
#Recursion is limited in python (1000 times, etc., depending on the environment)
#Change this to a sufficiently large value (10 to the 9th power this time)
import sys
sys.setrecursionlimit(10**9)
def func(N):
#Report that you called a recursive function
print("func({})Called".format(N))
#Base case
if N == 0:
return 0
#If not the base case, recursively ask for an answer
result = N + func(N-1)
print("{}Sum up to= {}".format(N, result))
return result
func(5)
[Output example] Called func (5) Called func (4) Called func (3) Called func (2) Called func (1) Called func (0) Sum up to 1 = 1 Sum up to 2 = 3 Sum up to 3 = 6 Sum up to 4 = 10 Sum up to 5 = 15
As a method, the number of recursion upper limit is increased. In Python, the recursion upper limit is often set to about 1000 times by default, so I think it would be nice to change it when using recursion in competition pros. (Not necessary in this case, but just in case)
code4-3.py
#Danger! Please do it at your own risk
def func(N):
if N == 0:
return 0
return N + func(N+1)
There is no doubt about TLE.
It is the familiar Euclidean algorithm.
** Q: What is the greatest common divisor of 51 and 15? ** **
Let's write it as a recursive function.
code4-4.py
def GCD(m, n):
#Base case
if n == 0:
return m
#Recursive call
return GCD(n, m % n)
print(GCD(51, 15)) #3 is output
print(GCD(15, 51)) #3 is output
[Output example] 3 3
By the way, the amount of calculation is $ O (log (n)) $. GCD is fast! !! !! !!
This is also a familiar one. 1 1 2 3 5 8 13 21 34 ...
code4-5.py
def fibo(N):
#Base case
if N == 0:
return 0
elif N == 1:
return 1
#Recursive call
return fibo(N-1) + fibo(N-2)
print(fibo(5))
[Output example] 5
Although it is not in the original, I also added an output to check the operation. Let's check the detailed operation with the following code 4.6.
This is a concrete usage example of code4.5. An output is included so that you can check the internal status.
code4-6.py
def fibo(N):
#Report that you called a recursive function
print("fibo({})Called".format(N))
#Base case
if N == 0:
return 0
elif N == 1:
return 1
#Recursively ask for an answer and output
result = fibo(N-1) + fibo(N-2)
print("{}item= {}".format(N, result))
return result
fibo(6)
[Output example] Called fibo (6) Called fibo (5) Called fibo (4) Called fibo (3) Called fibo (2) Called fibo (1) Called fibo (0) 2 items = 1 Called fibo (1) 3 items = 2 Called fibo (2) Called fibo (1) Called fibo (0) 2 items = 1 4 items = 3 Called fibo (3) Called fibo (2) Called fibo (1) Called fibo (0) 2 items = 1 Called fibo (1) 3 items = 2 5 items = 5 Called fibo (4) Called fibo (3) Called fibo (2) Called fibo (1) Called fibo (0) 2 items = 1 Called fibo (1) 3 items = 2 Called fibo (2) Called fibo (1) Called fibo (0) 2 items = 1 4 items = 3 6 items = 8
Despite the relatively small number of N = 6, there are many function calls. The following code (code4.8) attempts to improve this.
It is an attempt to see what happens if we leave recursion once and implement it with a for statement and an array.
code4-7.py
F = [None] * 50
F[0], F[1] = 0, 1
for N in range(2, 50):
F[N] = F[N-1] + F[N-2]
print("{}item: {}".format(N, F[N]))
[Output example] 2 items: 1 3 items: 2 4 items: 3 5 items: 5 6 items: 8 7 items: 13 8 items: 21 9 items: 34 10 items: 55 11 items: 89 12 items: 144 13 items: 233 14 items: 377 15 items: 610 16 items: 987 17 items: 1597 18 items: 2584 19 items: 4181 20 items: 6765 21 items: 10946 22 items: 17711 23 items: 28657 24 items: 46368 25 items: 75025 26 items: 121393 27 items: 196418 28 items: 317811 29 items: 514229 30 items: 832040 31 items: 1346269 32 items: 2178309 33 items: 3524578 34 items: 5702887 35 items: 9227465 36 items: 14930352 37 items: 24157817 38 items: 39088169 39 items: 63245986 40 items: 102334155 41 items: 165580141 42 items: 267914296 43 items: 433494437 44 items: 701408733 45 items: 1134903170 46 items: 1836311903 47 items: 2971215073 48 items: 4807526976 49 items: 7778742049
It can be implemented with a computational complexity of $ O (N) $.
If you use arrays well, you can skip the same calculations and speed up your program. Let's incorporate this into recursion (= memoization).
code4-8.py
#fibo[N]An array to note the result of
memo = [-1] * 50
def fibo(N):
#Base case
if N == 0:
return 0
elif N == 1:
return 1
#Check notes
if memo[N] != -1:
return memo[N]
#Recursive call while making a note of the answer
memo[N] = fibo(N-1) + fibo(N-2)
return memo[N]
fibo(49)
for N in range(2, 50):
print("{}item: {}".format(N, memo[N]))
[Output example] 2 items: 1 3 items: 2 4 items: 3 5 items: 5 6 items: 8 7 items: 13 8 items: 21 9 items: 34 10 items: 55 11 items: 89 12 items: 144 13 items: 233 14 items: 377 15 items: 610 16 items: 987 17 items: 1597 18 items: 2584 19 items: 4181 20 items: 6765 21 items: 10946 22 items: 17711 23 items: 28657 24 items: 46368 25 items: 75025 26 items: 121393 27 items: 196418 28 items: 317811 29 items: 514229 30 items: 832040 31 items: 1346269 32 items: 2178309 33 items: 3524578 34 items: 5702887 35 items: 9227465 36 items: 14930352 37 items: 24157817 38 items: 39088169 39 items: 63245986 40 items: 102334155 41 items: 165580141 42 items: 267914296 43 items: 433494437 44 items: 701408733 45 items: 1134903170 46 items: 1836311903 47 items: 2971215073 48 items: 4807526976 49 items: 7778742049
This could also be implemented with a computational complexity of $ O (N) $.
Solve the same problem as code 3.6 in the previous chapter using a recursive function. Forget memoization once and implement it with simple recursion.
code4-9.py
def func(i, w, a):
#Base case
if i == 0:
if w == 0:
return True
else:
return False
#a[i-1]If you do not choose
if func(i-1, w, a):
return True
#a[i-1]When choosing
if func(i-1, w-a[i-1], a):
return True
#If both are False
return False
N, W = map(int, input().split())
a = list(map(int, input().split()))
if func(N, W, a):
print("Yes")
else:
print("No")
【Input example】 4 10 1 9 100 200 [Output example] Yes
This code is computationally expensive $ O (2 ^ N) $. (See Kenchon's book for details)
If you are interested, make a note of this too! (Chapter end problem 4.6)
Click here for Chapter 5 (Add as soon as it is completed)
Recommended Posts