TIL|アルゴリズムベース#2

13543 ワード
python アルゴリズム#アルゴリズム# TIL テキストリンク

さいきかんすう


-独自の関数を呼び出す
-basecaseとrecursive caseを分けて考えるべきだ!
# 예시 1
def countdown(n):
	if n > 0:
		print(n)
		countdown(n - 1)  # 여기서 재귀함수 걸리면서 n-1으로 반복하게 된다 
4
3
2
1
-basecaseとrecursive caseを分けて考えるべきだ!

工場の取得


<再帰>
#n = 0 인 경우 n! = 1                 base case -> 문제가 충분히 작아서 바로 풀수있는 경우
#n > 0 인 경우 n! =(n - 1)! * n       recursive case 

def factorial(n):
	if n == 0:
		return 1
	return factorial(n * 1) * n 

print(factorial(4))
24
<重複記事>
def factorial(n):
	result = 1
	for i in range(1, n + 1):
		result = result * i
	return result

再帰関数の欠点


-スタックオーバーフローエラー(コールバック関数の呼び出しが多すぎる場合)が発生し、スタックが多すぎてしきい値に到達する可能性があります.
-パイソンは最初に最大1000個のCall Stackを許可した
  • Call Stack?関数が完了すると、それがどこに入るかを知る必要があります.コンピュータは内部でその位置を記憶します.→Call Stackに保存します.→関数が完了したら、元の位置に戻り、記録
    • をクリアします.

    フィボナッチ数列を再帰的に求める

    # n번째 피보나치 수를 리턴
def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)
        

# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))

# 시간복잡도 O(2^n)
    →初めて試した再帰関数なので概念があまり良くないようですが、Google+ヒントを見ながら、じっくり考える練習

    自然数の1からnの和の値の関数を求めます

    # 1부터 n까지의 합을 리턴
def triangle_number(n):
    if n == 1:
        return 1
    return triangle_number(n-1) + n 

# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
    print(triangle_number(i))'

# 시간복잡도 
# 재귀문을 통해서 **triangle_number** 함수는 총 n번 호출되어, O(n)의 시간이 걸림
    →一度で完成!!!!!!!!!
    まずすぐに得られるbasecaseを考えて、次の値を順番に書いて、2~3番目の値の関係を定義します!

    パリンドロム(実習)


    『最初の答え』
    def is_palindrome(word):
    length_word = len(word)
    for i in range(length_word // 2):
        if word[i] == word[-i - 1]:
            return True  
        return False  

            
# 테스트
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))
    True
True  # 얘 답안이 틀림
True
True
False
    ->なぜ間違っているのかわからず、最初の文字→return for文だけをダラダラ比較してみましたが、条件の最初の文字を確認したら、本当に車に戻って捨てる→使い続けます!→グーグル→一番下の答えで修正成功~!!
    <修正された最終回答>
    def is_palindrome(word):
    length_word = len(word)
    for i in range(length_word // 2):
        if word[i] == word[-i - 1]:
            continue  #  조건을 만족하면 계속해서 조건확인
        return False  #  조건을 만족하지 않는다면 return False
    return True  # return으로 끝나지 않은 if 조건을 만족하는 것을 True return

            
# 테스트
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))
    True
False
True
True
False
    【java解惑】クラスとインスタンスの初期化サイクル問題
    4-1. アレイ(Collection-Array)