Loading...
Counting

2013-06-19 Robert Zhang 更多博文 » 博客 » GitHub »

原文链接 http://huiming.io/2013/06/19/counting.html
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。


分析:6.4节《其他计数序列》里提到关于整数拆分的算法,比如,3有三种拆分法:1+1+1,1+2,3。设f(n, k)表示把n拆成一系列不大于k的整数的方法数,则

f(n, k) = f(n, k - 1) + f(n - k, k) (a)

暂不考虑4,如果把n拆成一系列由1、2、3组成的数,分别有k1、k2、k3个,即:

n = 1 * k1 + 2 * k2 + 3 * k3 (b)

k = k1 + k2 + k3

则这些数字可以排列成的不同整数,共有: <!--more-->

k!/(k1!*k2*k3!) (c)

个。再考虑4是1的同义词,分别把0,1,2,3,...,k1个1替换成4,一共有

C(k1, 0) + C(k1, 1) + C(k1, 2) + ... + C(k1, k1) = 2 ^ k1 (d)

种方法。(c)(d)两式相乘即得到由(b)式产生的一个拆分方案所得到的所有不同整数(由此可见当k2和k3为零时共有2 ^ n种不同整数,也就是说拆分n产生的不同整数不小于2 ^ n。在本题中n<=1000,显然高精度整数运算又是必不可少的)。

这种先拆分数字再排列组合的方法可行吗?因为(a)式只给出了方法数,没有具体给出每种方法里1,2,3的数目,所以在编程时必须增加返回值,比如

s = f(n, k, v)

其中v为一个长度为s的数组,每个元素是一个三元组,分别表示一种拆分方法所含的1,2,3的数目,根据v即可进行计算。不要说时间复杂度,空间复杂度就很高了,如果f(1000, 3) * 3超过了内存限制怎么办?

第6章《组合数学》开篇有一句话:当你用正确的角度看待一个问题时,答案就会显而易见(但作者显然在编排题目时经常性的误导读者:))。此题解法相当简单直观:

设f(n)为解,则:

f(n) = 2 * f(n - 1) + f(n - 2) + f(n - 3)

以上表示:各位和为n且每位取1,2,3,4中的一个数的整数的个数 = 以1或4开头的数的个数 + 以2开头的数的个数 + 以3开头的数的个数。区区几十行代码,并不那么简单。

#include <iostream>
#include <vector>
#include "bigint.h"

using namespace std;

vector<BigInt> N;

void init() {
  N.reserve(1001);
  N.push_back(0);
  N.push_back(2);
  N.push_back(5);
  N.push_back(13);
}

BigInt count(int n) {
  if (n >= N.size()) {
    for (int i = N.size(); i <= n; i++) {
      BigInt bi = 2 * N[i - 1] + N[i - 2] + N[i - 3];
      N.push_back(bi);
    }
  }
  return N[n];
}

int main() {
  init();
  int n;
  while (cin >> n) {
    cout << count(n) << endl;
  }
  return 0;
}