# 算法学习（8）

www.MyException.Cn  网友分享于：2013-08-22  浏览：0次

# 1.Combinations Counting（组合计数）

```A B C D - four sorts of candies

A+B, A+C, A+D, B+C, B+D, C+D - six way to choose a pair of them.```

N的集合中有多少K元素的组合(假设所有N个元素都是不同的)。可以很容易地发现，数学公式是:

```      N!
------------- = C(N, K) - the number of different combinations
K! * (N - K)!```

X !是X的阶乘，也就是product 1 * 2 * 3 ···* X

```7
89 8
57 10
93 86
105 7
83 75
68 8
111 7```

``` 1 cases = int(input())
2
3 def fact(n):
4     """ 构造阶乘函数"""
5     if n == 1 or n == 0:
6         return 1
7     elif n > 1:
8         return n * fact(n-1)
9 Ans = []
10 for i in range(cases):
11     case = input().split()
12     N = int(case[0])
13     K = int(case[1])
14     C = round(fact(N) / (fact(K) * fact(N - K)))  # 代入公式求解
15     Ans.append(C)
16
17 for n in Ans:
18     print(int(n), end=' ') # 格式化输出
19
20 输出：70625252863 43183019880 9473622444 22760723700 39443226966 7392009768 33963647355 ```

# 2.Blackjack Counting（21点计数）

2 3 4 5 6 7 8 9，

T J Q K值为10，Jack，皇后，国王，

Ace - A

```input data:
4
A T
2 K 4
3 A Q 8
A 3 3 3 A

21 16 Bust 21```

```28
2 3 J 7
A Q
K 7
A K
A 4 5
A A J 9
4 3 6 7
8 6 8
A A A K K
7 6 5
2 A T A 7
6 6 5
A 2 T A A A
A A 7
5 7 8
K A
4 9 T
T 7
T A
5 2 J
T 9
K 6
7 T
5 A
A 7
J Q
A A 6
K 7```

``` 1 num1 = ['2', '3', '4', '5', '6', '7', '8', '9']
2 num2 = ['T', 'J', 'Q', 'K']
3 test_cases = int(input())  # 测试用例数
4
5 for i in range(test_cases):
6     case = input().split() # 每个测试用例
7     points = 0  # 初始化点的值为0
8     ans = []
9     for n in range(len(case)):
10         if case[n] in num1:
11             points += int(case[n])
12         elif case[n] in num2:
13             points += 10
14         elif case[n] == 'A' and points + 11 > 21:  # 当含有A并且，加上11点后，值大于21点时，A应算作1点
15             points += 1
16         elif case[n] == 'A' and points + 11 <= 21: # 当含有A并且，加上11点后，值不大于21点时，A应算作11点
17             points += 11
18     if points > 21:  # 总的点数大于21点，失败
19         print('Bust', end=' ')
20     else:  # 总点数不大于21点，打印点数
21         print(points, end='')
22
23 输出：Bust 21 17 21 20 Bust 20 Bust Bust 18 Bust 17 Bust 19 20 21 Bust 17 21 17 19 16 17 16 18 20 18 17 ```