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

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个数记为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;
}

知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3187 Backward Digit Sums 《挑战程序设计竞赛(第2版)》练习题答案