105學年度彰雲嘉區資訊能力競賽複賽程式設計題Q3(字串反轉)

字串反轉

給定多個由數字或者英文字母構成之字串，你的任務是寫一程式將這些字串依照同樣的順序輸出，但差別是，如果該字串是由純大寫英文字母構成的，那麼你要將這串字母反轉後輸出。

輸入說明 ：

輸入多個由數字或者英文字母構成之字串，頭尾會有一對大括號，大括號內的字串會用半形逗號隔開。

輸出說明 ：

將字串依照同樣的順序輸出，但如果裡面的成員是由純大寫英文字母構成的，則要將這串字母反轉後輸出。

範例1輸入 ：

{WE,342,LOVE,RSKHT,911700,MADNUU}

範例1輸出 ：

{EW,342,EVOL,THKSR,911700,UUNDAM}

Python code：
s=input().split(",") #輸入字串，以逗點分開
#題目規定要有大括號，所以要刪掉第一個的{字元
s[0]=s[0].lstrip('{') 
#題目規定要有大括號，所以要刪掉最後一個的}字元
s[len(s)-1]=s[len(s)-1].rstrip('}')
for i in range(len(s)):
    a=s[i].isalpha() #確定為英文字母與大寫，就反轉
    b=s[i].isupper()
    if a==True and b==True:
        s[i]=s[i][::-1]
print('{',end='') #列印時要有{字元
print(s[0],end=',') #列印第一個元素
for k in range(1,len(s)-1):
    print(s[k],end=',')
print(s[len(s)-1],end='}') #列印最後一個元素加}字元

105學年度彰雲嘉區資訊能力競賽複賽程式設計題Q2(找出最小的完全平方數)

找出最小的完全平方數

寫一個程式，輸入整數k (0<k<=10)，找出k位數中，所有數字均為偶數的完全平方數中最小的一個數。例如當k=5，五位數中所有數字均為偶數的完全平方數中最小的數為26244(26244=162²) 。

Python code：

# -*- coding: utf-8 -*-

"""

找出最小的完全平方數，但此數的所有數字均需為偶數

1、輸入n，表n組測試資料

2、輸入n組測試資料，表數字的位數

3、輸出n個滿足條件的完全平方數

@author: kujter

"""

import math as lp

def square(n):  #若是完全平方數，回傳1

    a = int(n**0.5)  

    if n==a*a:

        return 1

m=int(input()) #位數

a=[] #儲存完全平方數

x=[] #儲存完全平方數的各位數字

y=[]

z=[]

for i in range(10**(m-1),10**m): #找出完全平方數

    if square(i)==1:

        a.append(i) 

        

for k in range(len(a)):#分解完全平方數的各個數字

    x.append([])

    y.append([])

    z.append([])

    for j in range(m):

        ls=a[k]%10

        x[k].append(ls)

        y[k].append(ls)

        a[k]//=10

    

for p in range(len(a)):

    for q in range(m):

        if (x[p][q]%2)!=0:

            z[p]=x[p]

            

ret=[i for i in y if i not in z] #利用差集，找出滿足條件的完全平方數

for h in range(len(ret)): #將串列反轉及合併取出數字

    ans[h]=[qq for qq in ret[h][::-1]]

    answer=[str(ii) for ii in ans[0]]

    aa=("".join(answer))

    print(aa) 

😊 1、先找出輸入位數的n個完全平方數

   2、再將這些完全平方數分解找出各位數字

   3、判斷各位數字是否偶數

   4、用差集，找出偶數的完全平方數，第一個就是最小的

   5、由於是串列，故需利用合併，再輸出數字       

105學年度彰雲嘉區複賽程式設計題Q1(方格棋盤的走法)

一、方格棋盤的走法

假設輸入一個方格棋盤的寬X與高Y，方格之座標左上角標示為(0,0)，右下角標示為(X-1, Y-1)。每次只能往右走一格或者往下走一格，如範例圖形。假設要從左上角(0,0)走到右下角(X-1, Y-1)，請問有幾種走法？寫出一個程式從鍵盤輸入兩個整數X，Y (以一個空格分開)，其中0<X<=20, 0<Y<=20，輸出走法的個數。

輸入說明 ：

輸入第一行為一個整數 n，表示接下來會有n組測試資料。

接下來有 n 行，每行有兩個整數，數字間以一個空格區隔，分別代表方格棋盤的寬及高。

輸出說明 ：

輸出走法的個數，每個測試資料輸出一行。

範例1輸入：
2

4 8

8 8

範例1輸出：

120

3432

範例2輸入：
1

6 7

範例2輸出：

462

Python code：

"""

利用遞迴寫組合數C(n,m)，並解方格棋盤走法問題

"""

def C(n,m):

    if n<m:

        return 0

    elif m==0 or n==m:

        return 1

    else:

        return C(n-1,m)+C(n-1,m-1)

k=int(input())

c=[]

d=[]

for i in range(k):

    a,b=(int(x) for x in input().split())

    c.append(a)

    d.append(b)

for i in range(k):

    print(C(c[i]+d[i]-2,c[i]-1))

😊 這題不是常見的走線上捷徑的問題，而是走格子內，所以在輸入的長跟寬，都需減1，再取組合數，才是正解。

105學年度台中區資訊能力競賽程式題Q1(計算字串間隔距離)

給定一個由大小寫英文字母所組成的字串以及一個英文字母，請輸出該字母在這個字串中出
現的間隔距離，如
ABCDAAEFeDaBDCBCBcBCbCBBd
A
4 1 5

Python code：
m=input() #輸入字串
a=input() #輸入字母
b=[]#存入各字母編號
for i in range(len(m)):
    if m[i]==a.upper() or m[i]==a.lower():
        b.append(i)
for j in range(len(b)-1):
    print(b[j+1]-b[j],end=' ')
 

105學年度台中區資訊能力競賽程式題Q3(2^k的4個自然數表示法)

Lagrange's four-square theorem：每個正整數均可表示為4個整數的平方和
 ==>  m^2=a^2+b^2+c^2+d^2
(大陸第七屆藍橋杯試題)

Python code：

import time
m=int(input()) #輸入一正整數，找出所有的四平方和表示法
aa=int(m**0.5)+1
flag=0
start=time.clock()
for a in range(0,aa):
    bb=int((m-a*a)**0.5)+1
    for b in range(a,bb):
        cc=int((m-a*a-b*b)**0.5)+1
        for c in range(b,cc):
            d=int((m-a*a-b*b-c*c)**0.5)
            if a*a+b*b+c*c+d*d==m :   
                 flag+=1
                 if flag==1:
                    print(a,b,c,d)
                    end=time.clock()
                    print('It costs time',end-start,'seconds')


@ 正整數化四平方和的解數不一定只有唯一解
     如10=0^2+0^2+1^2+3^2
            =1^2+1^2+2^2+2^2

😺 以下的程式碼是可以找出由小到大排列的a、b、c、d的所有組數：

@藍橋杯規定只需找出一組解就好但執行時間不得超過3秒，
    所以必須優化，原本必須要4個for-loop，但最後一個迴圈
    可省略，讓d=m-a^2-b^2-c^2就好，本人測試過773535，
    如果是4個迴圈，需時22秒，但改成3個，時間縮短成0.36
    秒，大大提升效率。