如何计算烷烃的同分异构体数目？要公式

如何计算烷烃的同分异构体数目~

O(N^2)DP (Python实现)

我展示一些结果吧：
甲烷：1乙烷：1丙烷：1丁烷：2戊烷：3己烷：5庚烷：9辛烷：18壬烷：35癸烷：7511烷：15912烷：35513烷：80214烷：185815烷：4347
100烷：5921072038125809849884993369103538010139
具体思路详见

http://builtinclz.abcz8.com/showart.php?id=2011/0818_alkane

import sys
N=1000
dp=[[0 for i in range(0,N+1)] for j in range(0,5)]
for i in range(0,5):
dp[i][0]=1
alkyl=[1 for i in range(0,N+1)]
alkane=[1 for i in range(0,N+1)]
for i in range(1,N):
c=[0 for j in range(0,5)]
c[0]=1
for j in range(1,5):
c[j]=c[j-1]*(alkyl[i]+j-1)/j
for j in range(4,0,-1):
for k in range(0,N+1):
dp[j][k]+=sum([dp[j-l][k-i*l]*c[l] for l in range(1,min(j,k/i)+1)])
alkyl[i+1]=dp[3][i]
if i*2+1<=N:
alkane[i*2+1]=dp[4][i*2]
if i*2<=N:
alkane[i*2]=dp[4][i*2-1]-alkyl[i]*(alkyl[i]-1)/2
sys.stderr.write('i='+str(i)+'
')
for i in range(1,N+1):
print i,alkane[i],alkyl[i]

本质上就是一个无标号无根树带度数限制的计数问题.
将问题一般化：求 n 个点的无标号无根树的个数, 且每个点的度数不超过m。
烷基 (有根树)：首先考虑计算烷基的个数 (即有根树)。
考虑暴力 DP.。设状态为 f(i,j,k)f(i,j,k)，表示当前共有 ii个点。
最大的子树大小为 jj，且根的度数为 kk。对于状态 f(i,j,k)f(i,j,k)，通过枚举最大子树的个数 l 和次大子树的大小 size。
有f(i,j,k)=∑l∑s+f(i−jl,size,k−l){s+l−1l}f(i,j,k)=∑l∑s+f(i−jl,size,k−l){s+l−1l}。
其中 s=∑ja=1∑m−1b=0f(j,a,b)s=∑a=1j∑b=0m−1f(j,a,b)。
组合数是用来可重集计数的。这是O(n3m2)O(n3m2)的。
显然可以前缀和优化，但是空间撑不住。还可以做得更好。考虑如何省掉 jj 这一维状态。即设状态为 f(i,j)f(i,j)。表示当前共有 ii 个点，根的度数为 kk。
考虑 DP 的一个技巧: 强行规定转移顺序。即，先 1...n1...n 枚举 size，表示强制用最大子树大小为 size 的情形来转移。
不妨设s=∑m−1k=0f(size,k)s=∑k=0m−1f(size,k)，那么对于一个 f(i,j)f(i,j)。
再枚举一个最大子树 (即子树大小为 size 的子树) 的个数 k。
我们便有转移f(i,j)←f(i,j)+f(i−size×k,j−k){s+k−1k}f(i,j)←f(i,j)+f(i−size×k,j−k){s+k−1k}这是 O(n2m2)O(n2m2) 的。如果是算烷基的话，便是 O(n2)O(n2) 的。
烷烃 (无根树)：只要某个点 uu 满足其子树大小都 ≤n2≤n2，那么这个点是这颗树的重心。比较显然的是, 重心最多只会有两个，并且有两个重心的情形，两个重心一定相邻。
并且另一个重心做根的时候，这个重心的子树大小为 n2n2。(当然 nn 必须要是偶数)
很多无根树同构的问题就可以通过重心转化为有根树同构。烷烃就可以这么计数。因为我们可以在 DP 烷基的时候。
强制size<n2size<n2(注意是小于)，这样求出的 f(i,j)f(i,j) 就是点数为 ii 且重心度数为 jj 的无根树个数。那么答案为：∑mk=0f(n,k)+[n(mod2)=0]{∑m−1k=0f(n2,k)+12}。

扩展资料：
烷系同分异构体结构特征：
在烃及其含氧衍生物的分子式中必然含有这样的信息：该有机物的不饱和度。利用不饱和度来解答这类题目往往要快捷、容易得多。下面先介绍一下不饱和度的概念：
设有机物分子中碳原子数为n，当氢原子数等于2n+2时，该有机物是饱和的，小于2n+2时为不饱和的，每少两个氢原子就认为该有机物分子的不饱和度为1。
分子中每产生一个C=C或C=O或每形成一个环，就会产生一个不饱和度，每形成一个C≡C，就会产生两个不饱和度，每形成一个苯环就会产生4 个不饱和度。
例⒉烃A和烃B的分子式分别为C1134H1146和C1398H1278，B的结构跟A相似，但分子中多了一些结构为的结构单元。
则B分子比A分子多了33 个这样的结构单元。(注：构成高分子链并决定高分子结构以一定方式连接起来的原子组合称之为结构单元。）
参考资料来源：百度百科-烷烃
参考资料来源：百度百科-同分异构体

我学了四年的有机化学，从来就没有在任何资料上看来过有烷烃同分异构体数目的计算公式，我自己也推不出来。因此我推断是没有这样的公式的。
在高中阶段只要记住1到3个碳的只有一种结构，4个碳的有两种，5个碳的有3种就够了。另外，你还可以记得6个碳的有5种，7个碳的有9种，8个碳的有18种。

计算烷烃的同分异构体数目没有万能公式，只有慢慢数，或记忆常见C数对应的同分异构体数目。

这个应该是没有公式的吧 要自己一个一个列出来数 只要不数重复了就好 在草稿纸上列一列就出来了~~

供参考

---

如何计算烷烃的同分异构体数目？要公式视频