[Kenchon book to Python]-Chapter 4-"Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!

Introduction

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

code4.1 Recursive function to calculate the sum from 1 to N

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.

code4.2 Recursive function to calculate the sum from 1 to N

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)

• If it is not necessary after that, it will be omitted.

code4.3 Recursive function that does not stop recursive call

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.

code4.4 Find the greatest common divisor by Euclidean algorithm

It is the familiar Euclidean algorithm.

** Q: What is the greatest common divisor of 51 and 15? ** **

1. 51 ÷ 15 = 3 too much 6
2. 15 ÷ 6 = 2 too much 3 3.6 ÷ 3 = 2 not much 0 A: ３！！ That's the one.

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! !! !! !!

code4.5 Recursive function to find the Fibonacci sequence

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.

code4.6 Full search method using bits for the partial sum problem

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.

code4.7 Find the Fibonacci sequence by iterating with a for statement

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) $.

code4.8 Memoize the recursive function for finding the Fibonacci sequence

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) $.

code4.9 Solve the partial sum problem with a full search using a recursive function

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)