Counting

PC/UVa IDs: 110603/10198

分析: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
则这些数字可以排列成的不同整数,共有: 
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;
}

《Counting》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>