TIL #08 - 3.08



関数の再帰(Recursion):関数が自分の動作を繰り返すことを「再帰」または「ループ」と呼ぶ.
ハノイタワーや福祉問題でよく使われるタイプです.
#복리 구하는방법
def compoundinterest_(p,r,t):
    if t == 1:
        return p * (1+r)
    else:
        return compoundinterest_(p,r,t-1) * (1+r)
上記の関数のように定義し、return値でcompointerst関数を計算してelse文に入った後、呼び出し続けた再帰関数構造で福利厚生を計算します.
Import vs sys.stdin.readline()関数の比較
Input()関数:入力値を受け入れ、行ごとに読み取る->文字列に変換->strip()
また、input()関数は、入力値を受け取るたびにプロンプトウィンドウを開く処理を繰り返すため、実行時エラーが発生する可能性が高い.
sys.stdin.readline()関数:sysに属するメソッドはfileオブジェクトとみなされます.input()は内蔵関数と見なされます.したがって、ユーザの入力を受信し、そこでのみ動作するバッファを作成する必要があります.
質問する
地面にカタツムリがいます.このカタツムリはVメートルの棒に登る.カタツムリは昼にAメートルも上がる.でも、夜寝るとBメートル滑る.また、山頂に登ると滑ることはありません.
カタツムリはすべての棒に登るので、何日かプログラムを作ってください.
入力
1行目には3つの整数A,B,Vがあり、スペースで区切られています.(1 ≤ B < A ≤ V ≤ 1,000,000,000)
しゅつりょく
最初の行の出力カタツムリは木の棒を登って何日かかりますか.
A, B, V = map(int, sys.stdin.readline().split())
day = math.ceil(((V-B)) / ((A-B)))
print(day)
ドアの周りを回る方法もありますが、1~10000000を回る必要がある範囲ではruntimeerrorやアルゴリズムの無効性が必然的に現れます.だから数学.ceilを用いて迅速に解く方法を設計した.
もう一つの解法
import sys
daily_move = 0
A, B, V = map(int, sys.stdin.readline().split())
for i in range(1, (V//(A-B))+2):
    daily_move += A
    if daily_move >= V:
        print(i)
        break
    else:
        daily_move -= B 
import sys
import math
質問する
ACMホテルマネージャーの志宇さんはお客さんが着くと空き部屋を手配しています.お客様アンケートによると、ホテルの正門から最短距離の部屋まで歩くのが好きです.皆さんは智友を助けるプログラムを書きたいと思っています.つまり、アンケート調査の結果、ホテルの正門から徒歩距離が最も短い部屋への配布プログラムを作成します.
問題を簡略化するために、ホテルは矩形だと仮定します.各階にW部屋のH階建て(1≦H,W≦99)があると仮定する.次に、エレベータが一番左にあると仮定する(図1参照).こんな形のホテル.× W形態ホテルと呼ばれています.ホテルの正門は1階のエレベーターの正面にあり、正門からエレベーターまでの距離は無視されています.また、隣接するすべての2つの部屋の間の距離が同じ距離(距離1)であると仮定し、ホテルの正面にしか部屋がありません.
図1.H=6,W=12,H× Wホテルのサムネイル
部屋番号はYXXまたはYXX形式で、ここでYまたはYYはフロア数、XXはエレベーターから数えた番号を表します.すなわち、図1に斜線で示されている部屋は305号室である.
客はエレベーターで移動する距離を気にしない.歩く距離が同じだけで、階下の部屋のほうが好きです.例えば、102号室より301号室のほうが好きです.102号室は2キロ、301号室は1キロで行けますから.同じ理由で102番より2101番が好きです.
皆さんが作成するプログラムは、すべての部屋が空いていると仮定した場合、このポリシーに基づいてN番目のお客様に割り当てられた部屋番号を算出するプログラムです.1人目のお客様は101番、2人目のお客様は201番などを手配します.図1を例にとると、H=6で、10番目のお客様は402番に手配しなければならない.
入力
プログラムは標準入力から入力データを受信する.プログラムの入力はT個のテストデータからなり,Tは入力の第1行に与えられる.各テストデータは1行としてH、W、N、3つの整数を含み、それぞれホテルの階数、各階の部屋数、何人目の客(1≦H、W≦99、1≦N≦H)を表す.× W).
しゅつりょく
プログラムは標準出力に出力されます.各テストデータは、N番目のお客様に割り当てる部屋番号を正確に印刷します.
import math
import sys
test_data = int(sys.stdin.readline())
for data in test_data:
     H, W , N = list(map(int, sys.stdin.readline().split()))
     floor, number_ = N % H, N // H
     if floor == 0:
         print((H*100)+ number_)
     else:
         print((floor*100)+ number_+1)
質問する
MまたはN以上のすべての小数を出力するプログラムを作成してください.
入力
最初の行では、自然数MとNはスペースを隔てて与えられる.(1≦M≦N≦1000000)M以上N以下の小数は1つ以上の入力のみを与える.
しゅつりょく
1行1個、小数をインクリメント順に出力します.
import sys
m, n = map(int, sys.stdin.readline().split())

def prime_number(m, n):
    n+=1
    prime_list = [True] * n

    for i in range(2, int(n**0.5)+1):
        if prime_list[i] == True:
            for j in range(2*i, n, i):
                prime_list[j] == False

    for i in range(m,n):
        if i > 1 and prime_list[i] == True:
            print(prime_list[i])


prime_number(m,n)
アリストテレスのキューを利用して、探したい数字の平方根の倍数を全部消して、欲しい小数を見つけることができます.
たとえば、3以上20以下の小数を検索するには、20の最大平方根4の倍数が必要です.(2,3,4)事前にtrueをn個のリストに設定したprimeリストでは,倍数の値をFalseに戻し少数の値を探すだけでよい.