当分子式被保证为烷烃时,氢的数目就问题本身而言不重要。这道题的核心转化为构造并计数碳链。
首先回忆一下高中时的解法。
首先来考察链烷烃。还记得主链吗?我们只要用一个数组表达主链,其中每个元素设置为改位置所有可能的支链情况数目,最后求和就可以了。还记得我们无视了氢吗?这意味着对于支链我们可以用同样的方法:主链有支链,支链又有支链,当支链长度为0或长度非法时返回0,为1或2时返回1,从而构成一个递归的计算过程。当然每个碳原子有四条键,因此支链长度需要分配:新戊烷就是个典型的例子,它的中心碳原子可以理解成丙烷的2号碳原子被添加了两条支链——2,2-二甲基丙烷,不是浪得虚名的。
例如:对于戊烷的情况,主链长度为3时,对它尝试支链长度的唯一可能(0, 2, 0), 得到[0, 1, 0]。如此,其他情况简记如下:
3 => (0, 2, 0) => [0, 1, 0] => 1 # 新戊烷
4 => (0, 0, 1, 0) => [0, 0, 1, 0] => 1 # 异戊烷
4 => (0, 1, 0, 0) .................... => 0 # 主链为偶数时,对称部分不计
5 => ................................. => 1 # 正戊烷
至此,基本的解法已经探索清楚,处理支链长度这种事情可能需要使用一些诸如嵌套循环的之类的小技巧,这里不再多提。
我们基本上再现了高中解题的方法。模拟是编写程序的一种很常用的手段。
不过……等等,你还在读吗?还是已经戳开IDE开始着手编写代码了?
在动手之前,你真的想清楚了吗?
让我再重复一下那个用于扩展碳链的算法:
- 对主链和支链我们用同样的方法
- 当支链长度为0或长度非法时返回0,为1或2时返回1
- 枚举支链所有可能的分配情况
- 求和所有枚举
等等!向下分解的最前两项是1,然后再求和?这是什么东西?有没有很像斐波那契数列?!(so bad...)但是你有没有感觉多次求和之后,这个数列比斐波那契数列增长的更快?(even worse!)
斐波那契数列有一个重要性质,就是它是最接近φ的n次幂的整数。这意味着即使只考虑链烷烃,其同分异构体的数目也至少是随着碳原子数目而指数增长!(what a terrible terrible fact...)
严格的、利用组合数学完成的证明太过复杂,我只是感性的描述了这个数字增长有多大:含有53个碳原子的链烷烃的同分异构体的数目已经超越了C中无符号长整数的表示范围。
当然,表示范围不是核心问题,我们有各种各样可用的高精度整数库。但是,如果n=53
的时候结果已经超过了2**64
,你又该如何处理n逼近1000000的情况呢?还有更复杂的,那就是……
事实上,比起如何估算同分异构体数目的增长速度,我更希望你能够采取的策略是及时Google。在一大圈搜索之后,你会沮丧的发现,目前仅有的成熟算法大多是针对无环烷烃的,这意味着本题在通往不可行的路上又迈出了三千大步。
事实上也是如此:虽然蒽(C14H10)能够快速降低局部饱和度,但是想一下那种单键和叁键交替的链状聚合物(嗯...这货好像能导电),想一下蒽的氢全部被烷烃基团取代之后的样子,你会发现推断碳骨架都成了一件很困难的事情……
如果你真的挑战了这两个问题,无论结果如何,你可能已经收获了大量的关于:
- 链表、树、图的性质、实现与应用
- 循环技巧
- 递归
以及
- 如何被坑
- 如何不被坑
- 如何先思考再编码
的经验与知识。如果没有,那么至少对于后三条,你应该已经有了新的理解。
总之,接受现实吧,这是一个理论可解,但现阶段下工程不可行(或者至少经济不可行)的问题。无论信与不信,在未来你会大量的遇到诸如此类的问题,越早意识到这问题,就越有可能避免跳坑。而这也就是我为什么要知其不可而为之了。