放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

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

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

POJ 3187 Backward Digit Sums

将一行数按杨辉三角的规则计算为一个数,已知最后那个数和三角形的高度,求最初的那行数。给家里的老爷机装上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里。

有了Ck那么即使题目中的初始数字不为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;
}

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

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    我看不懂你怎么运用“杨辉三角第n层第k个数记为Ckn那么=n!/[k!(n-k)!]=n * (n – 1)…*(n – k + 1) / k!”这个东西,我是直接暴力过的

    qingxi曾3年前 (2015-03-08)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机