辜德 (Good) 的 Python 部落格

2018年5月10日星期四

我所寫過的dev c++程式執行檔~~

2018年5月1日星期二

2017.10月大學程式設計先修檢測實作題第四題(物品堆疊,Stacking)

問題描述
某個自動化系統中有一個存取物品的子系統，該系統是將N個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。
每一次升高某些物品所需要消耗的能量是以這些物品的總重來計算，在此我們忽略貨架的重量以及其他可能的消耗。現在有N個物品，第i個物品的重量是w(i)而需要取用的次數為f(i)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。舉例來說，有兩個物品w(1)=1、w(2)=2、f(1)=3、f(2)=4，也就是說物品1的重量是1需取用3次，物品2的重量是2需取用4次。我們有兩個可能的擺放順序(由上而下)：
 (1,2)，也就是物品1放在上方，2在下方。那麼，取用1的時候不需要能量，而每次取用2的能量消耗是w(1)=1，因為2需取用f(2)=4次，所以消耗能量數為w(1)*f(2)=4。
 (2,1)，也就是物品2放在1的上方。那麼，取用2的時候不需要能量，而每次取用1的能量消耗是w(2)=2，因為1需取用f(1)=3次，所以消耗能量數=w(2)*f(1)=6。
在所有可能的兩種擺放順序中，最少的能量是4，所以答案是4。再舉一例，若有三物品而w(1)=3、w(2)=4、w(3)=5、f(1)=1、f(2)=2、f(3)=3。假設由上而下以(3,2,1)的順序，此時能量計算方式如下：取用物品3不需要能量，取用物品2消耗w(3)*f(2)=10，取用物品1消耗(w(3)+w(2))*f(1)=9，總計能量為19。如果以(1,2,3)的順序，則消耗能量為3*2+(3+4)*3=27。事實上，我們一共有3!=6種可能的擺放順序，其中順序(3,2,1)可以得到最小消耗能量19。
輸入格式
輸入的第一行是物品件數N，第二行有N個正整數，依序是各物品的重量w(1)、w(2)、…、w(N)，重量皆不超過1000且以一個空白間隔。第三行有N個正整數，依序是各物品的取用次數f(1)、f(2)、…、f(N)，次數皆為1000以內的正整數，以一個空白間隔。
輸出格式
輸出最小能量消耗值，以換行結尾。所求答案不會超過63個位元所能表示的正整數。
範例一(第1、3子題)：輸入
2
20 10
1 1
範例一：正確輸出
10
範例二(第2、4子題)：輸入
3
3 4 5
1 2 3
範例二：正確輸出
19

Python Code：

參考資料：
https://henrybear327.github.io/CodingNotes/contest/apcs/1061028/

😌😌
原本的程式碼，在n>10會逾時，因為我的做法是找出所有的排列，再算出所有的energy，接著取最小值，這種做法是可以的，但是在n大的時候，效率就變差了~~~
網路上參考別人C語言的寫法，再利用泡沫排序法，可找到答案!!!

結論：大學與研究所時，怎麼沒去修演算法呢？

2018年4月25日星期三

第三題：軍隊部署

問題描述
亞歷山大將軍準備派遣一支精銳部隊前往攻打鄰國，他麾下有三個種族 – 「人類」、
「骷髏族」和「哥布林族」；每個種族各有不同兵種，例如人類有騎士、法師、弓箭手，而
哥布林族有勇士、投矛手、吹箭手等等。
為了平衡部隊的組成份子，亞歷山大會從三個種族各選擇一個兵種。此外，他還會考慮
這個部隊是否能涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。舉例來說，亞歷山大將軍麾下的三個種族各有三個兵種如下：

亞歷山大可以選擇法師、骷髏兵團和勇士這個組合，因為這個組合涵蓋了三個種族和三個特
性；但他不能選擇弓箭手、骷髏兵團和投矛手這個組合，因為這個組合未能涵蓋「範圍攻
擊」這個特性；他也不能選擇弓箭手、炸彈兵和炸彈塔這個組合，因為這個組合未能涵蓋
「哥布林」這個種族。
亞歷山大為這個問題想了很多天，國王感到很不解，這麼簡單的事情怎麼想那麼久。亞
歷山大為了向國王解釋，他想要告訴國王總共有多少種可能的組合，請你幫幫他。
輸入格式
第一列為一個正整數 N (1  N  10000)，代表亞歷山大麾下有多少種兵種。接下來的 N
列，每一列有四個正整數 ci (ci  {1, 2, 3})、ai、ri 和 di (ai, ri, di  {0, 1})，彼此間以一個空
白隔開，分別代表種族、對空攻擊、範圍攻擊和遠距攻擊。ai、ri 和 di 的值若為 1，代表
具有該特性；否則，不具有該特性。
輸出格式
輸出共有多少個兵種組合可以涵蓋三個種族和三個特性。

Python Code：
n=int(input()) # 輸入兵種
x,y=[],[]
for i in range(n): # 輸入兵種、對空攻擊、範圍攻擊、遠距攻擊
data=input().split(' ')
x.append(data)
for i in range(n): # 將輸入的字串轉成數字
x[i]=[int(p) for p in x[i]]

flag=0 # 合乎條件的組合加1
for i in range(n):
if x[i][0]==1:
for j in range(n):
if x[j][0]==2:
for k in range(n):
if x[k][0]==3:
if (x[i][1]+x[j][1]+x[k][1])>=1 and \
(x[i][2]+x[j][2]+x[k][2])>=1 and \
(x[i][3]+x[j][3]+x[k][3])>=1:
flag+=1
print(flag)

2018年4月20日星期五

第二題：自戀數

問題描述
一個d 位數整數 𝑁 = n1n2n3...nd，ni ∈ {1,2,3,4,5,6,7,8,9,0}被稱為自戀數 (narcissistic
number) 若𝑁 = n1^d+n2^d+....+nd^d
例如3 位數整數153 是自戀數因為153=13+53+33，
而4 位數整數1321 不是自戀數因為14+34+24+14=99 非1321。
非十進位制數字也會有自戀數，例如3 進位制數字(122)3=17 且13+23+23=17，或5 進位
制數字(3134)5=419 且34+14+34+44=419。
請寫一個程式判斷一整數是否為自戀數。
輸入格式
第一列有兩個非負整數 𝑏 與 𝑁，代表 𝑁 為 𝑏 進位制整數。
輸出格式
若輸出之整數為自戀數，輸出YES，若否則輸出 NO。
評分說明
本題共有二個子題，每一子題可有多筆測試資料：
第一子題的測試資料 𝑏 = 10，𝑁 最大為 8 位數整數，全部解出可獲 83 分；
第二子題的測試資料 2 ≤ 𝑏 ≤ 10，𝑁 最大為 8 位數整數，全部解出可獲 17 分。
輸入範例1
10 153
輸出範例1
YES
輸入範例2
10 1321
輸出範例2
NO
輸入範例3
3 122
輸出範例3
YES
輸入範例4
5 3134
輸出範例4
YES

Python Code：
import math as lp
data=input()
li=data.split() #輸入的字串，將之分開
n,x=[],[]
n=[int(x) for x in li] #將輸入的字串改成整數
b=n[0]
N=n[1] # N為b進位制整數
d=lp.floor(lp.log10(N))+1 # 取出N的位數
for i in range(d): #取出N的各位數字
ls=N%10
x.append(ls)
N//=10
s=0 # 計算每個數字的次方和
for j in range(d):
s+=x[j]**d
ss=0 # 計算b進位制和
for k in range(d):
ss+=x[k]*(b**(k))
if s==ss:
print('YES')
else:

print('NO')

第一題：連號或不連號

問題描述
生物學家發現，與特定功能相關的一群基因在基因序列上的位置通常十分靠近，因此在
不同的基因序列中如果都看見相同基因構成的連續片段 (順序不重要)，這些基因構成的集合
就被認為是有意義的，稱為基因群 (gene cluster)。例如: 如果在一條基因序列上看到一個片段
內容為 (a, b, c, d)，同時在另外一條基因序列上看到一個片段內容為 (d, b, a, c)，那麼 {a, b,
c, d} 就構成一組基因群。
找出基因群並不是一件容易的工作，有一個計算生物學家想到一個聰明的方法來簡化這
個問題。經過他的簡化後，基因群辨識的主要工作會被轉換成: 輸入一個由相異正整數組成的
序列 S，然後判斷 S 的內容是否構成連續的一串整數。例如: S = (2, 5, 3, 4) 的內容構成連續
的一串整數 2, 3, 4, 5；但是 S = (2, 6, 3, 4) 的內容並不構成連續的一串整數 (缺了 5)。
給定一個數字所構成的序列，請撰寫一個程式來判斷這個序列中的數字是否構成連續的
一串整數。
輸入格式
測試資料是由一行的數字所構成 (數字間以一個以上的空白隔開)，第一個數字 n 表示
所給定數字序列的長度，1 < n  100，接下來會有 n 個相異的正整數 mi，1  i  n 且 1  mi
 1000，表示數字序列的內容。
輸出格式
輸出一行，如果此序列中的數字構成連續的一串整數，請輸出: a b yes；不行則輸出: a b
no，其中 a 和 b 分別代表序列中所有數字的最小值與最大值。a 和 b 之間以及 b 和 yes/no
之間，請以剛好一個空白隔開。(yes/no 請用小寫)

第一子題輸入範例1
2 6 5
第一子題輸出範例1
5 6 yes
第一子題輸入範例2
2 5 7
第一子題輸出範例2
5 7 no
2
第二子題輸入範例1
3 9 8 7
第二子題輸出範例1
7 9 yes
第二子題輸入範例2
3 10 9 7
第二子題輸出範例2
7 10 no
第三子題輸入範例1
5 2 3 4 5 6
第三子題輸出範例1
2 6 yes
第三子題輸入範例2
5 2 3 4 5 7
第三子題輸出範例2
2 7 no

Python Code：
data=input() # 輸入數字序列長度n與n個相異正整數
li=data.split() # 輸入的字串，將之分開
s,t,u=[],[],[]
s=[int(x) for x in li] # 將輸入的字串改成正整數
for i in range(1,len(s)):
t.append(s[i]) # 列表t存放這n個相異正整數
u=sorted(t) # 將n個相異正整數由小到大排列
M=max(u) # 取出u的最大值
m=min(u) # 取出u的最小值
if M-m==len(u)-1:
print(m,M,'yes')
else:
print(m,M,'no')

2018年4月13日星期五

分堆問題

「分堆問題」到底何時要除(乘)，又要除(乘)多少呢？
統整「分堆問題」如下~~~
Q：8本不同的書，求下列的分法數？
(1)平分成2堆
(2)平分給甲乙2人
(3)分成4本，3本，1本三堆
(4)分給3人，其中1人4本，1人3本，1人1本
(5)甲得4本，乙得3本，丙得1本
(6)分成4本，2本，2本三堆
(7)分給3人，其中1人4本，1人2本，1人2本
(8)甲得4本，乙得2本，丙得2本

口訣：先分堆，再分人，有指定，不要動

解答：

爬樓梯與費氏數列

現在高一講到排列組合，在爬樓梯的題目中，它是跟費氏數列有關係的~~~(用這種解法，學生似乎比較容易做對)

Q：樓梯有8階，每步可爬1階或2階，則共有多少種不同的上
樓方法？
解：(利用費氏數列)
若樓梯只有1階，f(1)=1(一種走法)
若樓梯只有2階，f(2)=2(一次走2階或走2步1階)
費氏數列~~~f(n)=f(n-1)+f(n-2)
1,2,3,5,8,13,21,34，所以f(8)=34種上樓法
解釋
爬到第n階的上樓法會等於爬到第(n-1)階，再爬1階加上爬
到第(n-2)階再爬2階(不能爬2次1階的，因為會回到f(n-1))
，所以f(n)=f(n-1)+f(n-2)

同理，改成每步爬1階或2階或3階，則費氏數列會變成
f(n)=f(n-1)+f(n-2)+f(n-3)

訂閱：文章 (Atom)

辜德 (Good) 的 Python 部落格

總網頁瀏覽量

2018年5月10日星期四

我所寫過的dev c++程式執行檔~~

2018年5月1日星期二

2017.10月大學程式設計先修檢測實作題第四題(物品堆疊,Stacking)

2018年4月25日星期三

第三題：軍隊部署

2018年4月20日星期五

第二題：自戀數

第一題：連號或不連號

2018年4月13日星期五

分堆問題

爬樓梯與費氏數列

發表日期

總網頁瀏覽量

2018年5月10日 星期四

2018年5月1日 星期二

2018年4月25日 星期三

2018年4月20日 星期五

2018年4月13日 星期五

發表日期

2018年5月10日星期四

2018年5月1日星期二

2018年4月25日星期三

2018年4月20日星期五

2018年4月13日星期五