2.1 最基础的“穷竭搜索” 穷竭搜索
将一行数按杨辉三角的规则计算为一个数,已知最后那个数和三角形的高度,求最初的那行数。给家里的老爷机装上VC6+Sp6+VA+WndTabs,写出来的代码怪怪的……
杨辉三角前10行:
1 |
||||||||||||||||||
1 |
1 |
|||||||||||||||||
1 |
2 |
1 |
||||||||||||||||
1 |
3 |
3 |
1 |
|||||||||||||||
1 |
4 |
6 |
4 |
1 |
||||||||||||||
1 |
5 |
10 |
10 |
5 |
1 |
|||||||||||||
1 |
6 |
15 |
20 |
15 |
6 |
1 |
||||||||||||
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
|||||||||||
1 |
8 |
28 |
56 |
70 |
56 |
28 |
8 |
1 |
||||||||||
1 |
9 |
36 |
84 |
126 |
126 |
84 |
36 |
9 |
1 |
杨辉三角第n层第k个数记为Ckn那么=n!/[k!(n-k)!]=n * (n – 1)…*(n – k + 1) / k!
对应着下面这段代码
int c(int n, int k) { int result = 1; for (int i = 0; i < k; ++i) { result = result * (n - i) / (i + 1); } return result; }
上面做了一个简化,因为原始的式子里面分子分母的项数相等所有写进一个loop里。
有了Ckn 那么即使题目中的初始数字不为1,只要乘上这个系数Ckn就行了。
#include <iostream> #include <string> #include <algorithm> using namespace std; int c(int n, int k) { int result = 1; for (int i = 0; i < k; ++i) { result = result * (n - i) / (i + 1); } return result; } int main(int argc, char *argv[]) { int N, Sum; cin >> N >> Sum; int line[16]; int i = 0; for (; i < N; ++i) { line[i] = i + 1; } do { int result = 0; for (i = 0; i < N; ++i) { result += c(N - 1, i) * line[i]; } if (result == Sum) { break; } } while (next_permutation(line, line + N)); copy(line, line + N, ostream_iterator<int>(cout, " ")); return 0; }
我看不懂你怎么运用“杨辉三角第n层第k个数记为Ckn那么=n!/[k!(n-k)!]=n * (n – 1)…*(n – k + 1) / k!”这个东西,我是直接暴力过的