alex9ufo 聰明人求知心切

2018年1月7日星期日

遞迴法 fact(n) = n!

"""
遞迴法
階乘 n! = 1 x 2 x 3 x ... x n
用函數fact(n)表示，可以看出：
fact(1) = 1
fact(n) = n!
= 1 x 2 x 3 x ... x (n-1) x n
= (n-1)! x n
= fact(n-1) x n
於是，fact(n)用遞迴的方式寫出來就是：
"""

def fact(n):
if n==1:
print("fact(1)=1")
return 1
print ("fact(",n, ")=", n ,"* fact(",n-1,")")
return n * fact(n - 1)

print(fact(5))

=========== == RESTART: F:/Python_APSC/b039-1.py ==== =======

fact( 5 )= 5 * fact( 4 )

fact( 4 )= 4 * fact( 3 )

fact( 3 )= 3 * fact( 2 )

fact( 2 )= 2 * fact( 1 )

fact(1)=1

120

>>>

fact(100000)

File "F:/Python_APSC/b039-1.py", line 18, in fact
return n * fact(n - 1)
File "F:/Python_APSC/b039-1.py", line 18, in fact

return n * fact(n - 1)

使用遞迴函數需要注意防止棧溢出。在電腦中，函式呼叫是通過棧（stack）這種資料結構實現的，每當進入一個函式呼叫，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞迴呼叫的次數過多，會導致棧溢出。可以試試fact(1000)：

>>> fact(1000)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

File "<stdin>", line 4, in fact

...

File "<stdin>", line 4, in fact

RuntimeError: maximum recursion depth exceeded

解決遞迴呼叫棧溢出的方法是通過尾遞迴優化

尾遞迴是指，在函數返回的時候，調用自身本身，並且，return語句不能包含運算式。這樣，編譯器或者解譯器就可以把尾遞迴做優化，使遞迴本身無論調用多少次，都只佔用一個棧幀，不會出現棧溢出的情況。

如：

1 def factorial(n, acc=1):

2 "calculate a factorial"

3 if n == 0:

4 return acc

5 return factorial(n-1, n*acc)

函數返回時只調用了它本身 factorial(n-1, n*acc)

b040: 以物易物

遠古時代，當貨幣制度還沒有產生之前，人們是用以物易物的方式來交換所需要的物資。大南中古交換中心就是以類似的模式在經營，不同的是他們會將裡面所有的物品標價，而當顧客拿東西要來交換的時候，他們會先幫顧客的物品先估一個價格，而顧客則可以從裡面現有的物品裡挑選一個以上，只要加起來的價格沒有超過顧客帶來物品的價格，交易就算成立。
今天小雅來到大南中古交換中心，因為小雅是個非常精打細算的人，如果所挑選的物品的總價比她所帶來的東西低，則她不會從事這次的交易。現在給你交換中心裡所有物品的價格，以及小雅帶來的東西的價格，請你找出她有幾個不同的交易方式，或者不會進行交易。

輸入說明：

輸入資料第一行有兩個正整數 N、M (1<=N<=20、1<=M<=100000000)，N 代表交換中心有幾種物品，M 代表小雅帶來的物品的價格。第二行有 N 個正整數 Ai，即交換中心 N 種物品的價格 (1<=Ai<=M)，而且這些價格都不會相同。

輸出說明：

請輸出所有小雅可以交易的方式，每種方式以一行輸出，將要交換的物品價格依照原本輸入的順序輸出。有多組交易方式時，請以前幾項物品取的方式優先。而如果找不到一種交易方式所交換的物品價格和小雅帶來的東西相等，則請輸出 NO。

範例輸入：

4 31
11 13 24 7

範例輸出 ：

11 13 7
24 7

def ssum(list, sum1):
current = ""
ssum_h(list, len(list), current, sum1)

def ssum_h(list, n, subset, sum1):
if sum1 == 0:
print (subset)
return

if n == 0:
return

if list[n-1] <= sum1:
ssum_h(list, n-1, subset, sum1)
ssum_h(list, n-1, subset+ str(list[n-1]) + " ", sum1-list[n-1])
else:
ssum_h(list, n-1, subset, sum1)

if __name__ == "__main__":
lst = []
print("請輸入各種物品的價格或按enter結束")
while True:
lst1 = (input())
if lst1:
lst.append(int(lst1))
else:
break
text = '\n'.join(str(lst))

print()
print("輸入資料",lst)
print("輸入物品的價格 -> ",end='')
sum1 = int(input())

ssum(lst, sum1)

請輸入各種物品的價格或按enter結束
2
1
3
4
5
5
1
2
8
7
-2

輸入資料 [2, 1, 3, 4, 5, 5, 1, 2, 8, 7, -2]
輸入物品的價格 -> 7
4 1 2
4 3
5 2
5 2
1 3 1 2
1 4 2
1 5 1
1 5 1
2 3 2
2 4 1
2 5
2 5
2 1 3 1
2 1 4
7
-2 4 3 2
-2 5 3 1
-2 5 4
-2 5 3 1
-2 5 4
-2 1 4 3 1
-2 1 5 1 2
-2 1 5 3
-2 1 5 1 2
-2 1 5 3
-2 2 4 1 2
-2 2 4 3
-2 2 5 2
-2 2 5 2
-2 2 1 3 1 2
-2 2 1 4 2
-2 2 1 5 1
-2 2 1 5 1
-2 8 1
-2 8 1
-2 7 2
-2 7 1 1
-2 7 2
>>>

2018年1月4日星期四

1/5 工業電子

1/5 工業電子

1) PPT (音樂盒+ 量測 )

2) PDF (量測1)

3) PDF (量測 2)

巢狀迴圈

Public Class Form1

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim i, j, P As Short
For i = 1 To 9
For j = 1 To 9
P = i * j
TextBox1.Text = TextBox1.Text & i & "*" & j & "=" & P & " "
Next
TextBox1.Text = TextBox1.Text & vbCrLf
Next

End Sub

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim i, j, P As Short
i = 1
j = 1
Do While (i <= 9)
Do While (j <= 9)
P = i * j
TextBox1.Text = TextBox1.Text & i & "*" & j & "=" & P & " "
j = j + 1
Loop
TextBox1.Text = TextBox1.Text & vbCrLf
j = 1
i = i + 1
Loop

End Sub

Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim i, j, P As Short
i = 1
j = 1
Do
Do
P = i * j
TextBox1.Text = TextBox1.Text & i & "*" & j & "=" & P & " "
j = j + 1
Loop While (j <= 9)
TextBox1.Text = TextBox1.Text & vbCrLf
j = 1
i = i + 1
Loop While (i <= 9)

End Sub

Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click

Dim i, j, P As Short
j = 1
For i = 1 To 9
Do
P = i * j
TextBox1.Text = TextBox1.Text & i & "*" & j & "=" & P & " "
j = j + 1
Loop While (j <= 9)
TextBox1.Text = TextBox1.Text & vbCrLf
j = 1
Next

End Sub
End Class

迴圈

for next

do....loop while

do while......... loop

Public Class Form1

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim i, sum As Short
TextBox1.Text = ""
sum = 0
For i = 1 To 10
sum = sum + i
TextBox1.Text = TextBox1.Text & "i = " & i & " , Sum = " & sum & vbCrLf
Next

End Sub

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim i, sum As Short
TextBox1.Text = ""
sum = 0
i = 0
Do
sum = sum + i
i = i + 1
TextBox1.Text = TextBox1.Text & "i = " & i & " , Sum = " & sum & vbCrLf
Loop While (i <= 10)

End Sub

Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim i, sum As Short
TextBox1.Text = ""
sum = 0
i = 0
Do While (i <= 10)
sum = sum + i
i = i + 1
TextBox1.Text = TextBox1.Text & "i = " & i & " , Sum = " & sum & vbCrLf
Loop
End Sub
End Class