脈衝光

全排列與迴文題目來源http://tw.group.knowledge.yahoo.com/students-1/message_board/view?tid=11題目 A迴文數目輸入檔: pa.in /輸出檔: pa.out所謂的「迴文」，就是指一個字串從頭開始唸跟倒著唸結果完全一樣。例如abccaaccba就是一個迴文字。而所謂的「全排列」，則是指一個字串裡的每個字母在經過順序的調換以後所能得到的各種排列。例如abcd的全排列就是：abcd abdc acbd acdb adbc adcbbacd badc bcad bcda bdac bdcacabd cadb cbad cbda cdab cdbadabc dacb dbac dbca dcab dcba請寫出一個程式，對於輸入的字串，算出在這個字串的全排列裡有多少個是迴文。例如aabb的全排列為：aabb abab abba baab baba bbaa其中abba和baab是迴文，因此aabb的全排列裡有2個迴文。輸入檔說明：輸入檔第一行是一個整數 N (1 ? N ? 50) 代表題目的數目。接下來N行輸入，每一行會有一個長度不超過40的字串，這個字串會完全由小寫的英文字母構成。﹝字串的長度最少是1﹞輸出檔說明：對每一行字串，請在每行輸出這個字串的全排列裡有幾個迴文﹝如果全排列裡一個迴文都沒有的話，就輸出0﹞。輸出的數字不會超過integer的大小。範例輸入：3aabbaabc範例輸出:210題目好長, 感覺比答案還長由於題目沒有要求列舉, 算出組合數就好了首先, 判斷傳入字串能否形成迴文迴文的定義是, 字串對半切開, 左右是對稱的所以決定了左邊, 右邊也就不能改變了又, 因為左右相同, 所以只有正中間的文字能是奇數個, 其他都是偶數個ex: abc,a,cba ; a:3個,b:2個,c:2個或是全部都是偶數個ex: abc,cba ; a:2個,b:2個,c:2個所以只需要統計字串中每個字母的數量檢查是否有兩個以上的字母有奇數個, 有的話就不能形成迴文若能形成迴文, 接下來就輪到算組合數剛剛說過迴文是左右對稱, 能決定排序的只有半邊, 另一半會隨著這半邊決定後跟著固定ex:abc,a,cba , 我們只需知道左半邊"abc"的全排列數量, 就知道迴文數量了之前已經統計過字串中每個字母的數量, 要算全排列數量的公式(不盡相異排列) = (字串長)! / (字母1數量)! (字母2數量)! (字母3數量)!...(字母n數量)! 因為只剩半邊, 全排列迴文數量 = (字串長\2)! / (字母1數量\2)! (字母2數量\2)! (字母3數量\2)!...(字母n數量\2)! ("\"為整除運算子, !是階層的意思 n! = n*(n-1)*(n-2)*...*3*2*1ex: abb,a,bba： a:3個 b:4個全排列迴文數量 = (7\2)! / (3\2)! (4\2)! = 3! / 1!2! = 3只有3種 列一下給大家看abb,a,bbabab,a,babbba,a,abb至此解說完畢, 以下為實作, 使用Collection做為統計字母用, 可能比較難懂, 可以自己改寫成用迴圈窮舉統計, 反正小寫英文字母也才26個  1: Option Explicit 2:   3: Private Sub Command1_Click() 4: Print "abccaccba"; PMTT("abccaccba") 5: Print "aabb"; PMTT("aabb") 6: Print "a"; PMTT("a") 7: Print "abc"; PMTT("abc") 8: Print "dfaeredafa"; PMTT("dfaeredafa") 9: Print "abccaaccba"; PMTT("abccaaccba") 10: End Sub 11:   12: Function PMTT(ByVal s As String) 13: Dim i As Long 14: Dim word As String 15: Dim col_word As New Collection 16: Dim col_index As New Collection 17: Dim wordcount() As Integer 18: Dim index As Integer 19: Dim str_Len As Long 20: Dim f_c As Double 21: Dim have_odd As Boolean 22: 23: str_Len = Len(s) 24: 25: If str_Len = 0 Then 26: PMTT = 0: Exit Function 27: ElseIf str_Len = 1 Then 28: PMTT = 1: Exit Function 29: End If 30: 31: For i = 1 To str_Len 32: word = Mid(s, i, 1) 33: On Error Resume Next 34: index = col_index.Item(word) 35: If Err.Number = 5 Then 36: Err.Clear 37: ReDim Preserve wordcount(col_word.Count) 38: wordcount(col_word.Count) = 1 39: col_word.ADD word, word 40: col_index.ADD col_index.Count, word 41: ElseIf Err.Number = 0 Then 42: wordcount(index) = wordcount(index) + 1 43: End If 44: Next 45: 46: f_c = factorial(Int(str_Len / 2)) 47: have_odd = False 48: For i = 1 To col_word.Count 49: If wordcount(col_index(i)) And 1 Then 50: If have_odd = True Then PMTT = 0: Exit Function 51: have_odd = True 52: End If 53: f_c = f_c / factorial(Int(wordcount(col_index(i)) / 2)) 54: Next 55: PMTT = f_c 56: End Function 57:   58: Function factorial(n As Integer) 59: Dim i As Integer 60: factorial = 1 61: For i = 2 To n 62: factorial = factorial * i 63: Next 64: End Function.