APCS 前置作業- zerojudge 基礎題庫 by python

zerojudge 為高師附中江其勳老師開發的程式寫作 Online Judge 網站：
https://zerojudge.tw/

進入網站後到 分類題庫>基礎題庫 有一些基礎練習連結如下：
https://zerojudge.tw/Problems?tabid=BASIC#tab00


今天要幫大家介紹如何搭配 python 做幾個基礎的練習：

話說python本身在做標準輸入時不像 c++ 一樣可以直接偵測EOF

例如：

int n;
while(scanf("%d",&n) != EOF)

{

    //...主程式...

}

上例c++程式中會不斷讀入整數給變數n直到讀到EOF為止

為了讓 python程式可以在 zerojude上順利執行，我們導入了 try....except的概念
(try的用法可參考：http://www.runoob.com/python/python-exceptions.html)

讓讀到 EOF 當作例外來觸發，觸發之後可視程式的需求進一步動作，或終止程式。

例外處理與程式除錯是另外一門藝術，讀者可以藉由下列實例體會在程式中使用try來跳過例外狀況的方便之處，並慢慢學習真正需要做程式除錯時，程式中如何妥善傳遞例外狀況。


題目1. a001: 哈囉
https://zerojudge.tw/ShowProblem?problemid=a001

while True:
    try:a=input()
    except:break #過濾掉 EOFError，讀到EOF後直接跳出迴圈
    if not a:break #輸入空字串時跳出迴圈
    print('hello,',a)

題目2. a002: 簡易加法
https://zerojudge.tw/ShowProblem?problemid=a002

while True:
    try:
        #用字串內建的 split() 函式
        #將字串做分割並將結果回傳給 a,b 
        a,b=input().split()
    except: break
    if not a:break    
    print(int(a)+int(b))

題目3. a003: 兩光法師占卜術
https://zerojudge.tw/ShowProblem?problemid=a003

R=['普通','吉','大吉']
while True:
    try:
        M,D=input().split()
    except: break
    S=(int(M)*2+int(D))%3
    print(R[S])

題目4. a004: 文文的求婚
https://zerojudge.tw/ShowProblem?problemid=a004

#西元年被4整除且不被100整除，或被400整除者即為閏年
while True:
    try:
        Y=int(input())
    except: break
    
    if (Y%4==0 and Y%100!=0)or Y%400==0 :
        print('閏年')
    else :
        print('平年')

題目5. a005: Eva 的回家作業
https://zerojudge.tw/ShowProblem?problemid=a005

n=int(input())
for i in range(n):
    L=input().split()
    #A=[int(L[0]),int(L[1]),int(L[2]),int(L[3])]
    A= list(map(int,L))#一個將 L 串列中的元素取int的簡潔方法
    
    if A[1]-A[0] == A[2]-A[1] : #等差
        A.append(A[3]+A[2]-A[1])
    else: #等比
        A.append(A[3]*int(A[2]/A[1]))
    #把 A 串列中的元素塞到空字串R裡面，並用空白字元隔開
    R=""
    for a in A:
        r=str(a) #別忘了 A中的元素已被轉換成int了，要做字串運算的話要再轉換回來
        R=R+r+" " 
    print(R.strip())#用字串內建strip函式將頭尾多餘的空白字元刪除

以上五題供大家參考，初學者有空可繼續把全部基本題都做完

APCS 解答：

https://drive.google.com/drive/folders/1lKZdeN4ChRgkfe-aVDJf_I81hF2KVDAO?usp=sharing

APCS 考古題 Tree Analysis

APCS.2017.10.28考古題下載

※簡單方法(效能稍差)：

※其它方法(效能較佳)：(時間複雜度較小)

想法：
Step1.將樹葉節點納入待拜訪的佇列 (queue)

Step2.逐一由佇列中取出節點並拜訪各自的父節點並更新該父節點高度值

Step3.一旦被處理的父節點之子節點皆被拜訪過後，將該父節點也塞入待拜訪佇列的尾端

Step4.重複 Step2~3 直到拜訪到根節點為止

import queue
In = input().strip()
while In!="":# while not In    
    n= int(In)
    p=[-1]*(n+1)  #p[i]=j，表示i的雙親為j    
    d=[0]*(n+1)   #紀錄節點深度
    num=[0]*(n+1) #紀錄節點的子節點個數，子節點計算過後就減1
    t =queue.Queue()  #儲存待走訪之節點
    for i in range(1,n+1): #為方便觀察從索引 1 開始放置元素
        #line = list(map(int,f.readline().split()) )
        line = list(map(int,input().split()) ) #讀入一行後轉換為 int
        k = line[0]
        num[i] = k #節點 i 的子節點個數
        if k == 0:
            t.put(i) #葉節點先納入待走訪的節點
        else:
            for j in line[1:]:
                p[j] = i   #使用陣列p紀錄 j 的parent為i
    i = 0
    node = 0
    while True:
        node = t.get() #取出待走訪之節點
        if p[node] == -1:break #沒有父節點代表它是根節點==>結束迴圈
        d[p[node]]=max(d[p[node]],d[node]+1) #葉節點深度+1 和 已記錄之深度取大者作為本節點深度
        num[p[node]]=num[p[node]]-1 #父節點底下未走謗過的子節點數目減1 
        if num[p[node]] == 0: #當所有子節點都走訪過時，將該父節點納入待走訪之節點
            t.put(p[node])
        
    print(node)#最後一個從t取出的就是根節點
    print(sum(d))#最後一個從t取出的就是根節點
    try:In = input().strip()
    except EOFError:break