POJ 3187 Backward Digit Sums 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 穷竭搜索

POJ 3187 Backward Digit Sums

将一行数按杨辉三角的规则计算为一个数，已知最后那个数和三角形的高度，求最初的那行数。给家里的老爷机装上VC6+Sp6+VA+WndTabs，写出来的代码怪怪的……

杨辉三角前10行：

杨辉三角第n层第k个数记为C^k_n那么=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里。

有了C^k_n 那么即使题目中的初始数字不为1，只要乘上这个系数C^k_n就行了。

#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;
}