注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

烷烃同分异构体个数的计算  

2011-08-19 11:15:42|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
数一个烷有多少个同分异构体(每个点度数不超过4的无根树)是一个有趣的问题。
以前我思考的时候,只会计算烷基(有根树)的个数。这个其实很好办,利用最小表示的思路dp一下就行了。
NOI回来,我和张放在讨论一个有意思的东西:
树的“重心”(我们暂且这么命名吧)。
一个点是一个树的重心当且仅当以这个点为根,所有的子树(不包括整个树自身)的大小都不超过N/2(N是整个树的节点数)
我发现,利用树的重心这个概念,烷烃的计算也可以dp了。
具体的解法和代码见:
我展示一些结果吧:
甲烷:1
乙烷:1
丙烷:1
丁烷:2
戊烷:3
己烷:5
庚烷:9
辛烷:18
壬烷:35
癸烷:75
11烷:159
12烷:355
13烷:802
14烷:1858
15烷:4347
100烷:5921072038125809849884993369103538010139
500烷: 69888806977968318652007568872323509883145559195919337637376568556764896550639165374194198834566064897188044072953504164443147167221896769574954040005634802439024034052447587053721967608928388404735140565376686372508743 
1000烷: 7353542771908520562400571140003803615818310930167721894548536914184563564057345370126384596274247734352048089098710726217236720772089521031575700080791919614143683611691851188502386451682669868198490392038469095344877339792621067981851651485913696975912156720603673430821138942195711200334599833916318407719727683794053350414266385522285497381742331952500813776473702316906830629777627612978475010672965670707321860538101657368032050644746140 
  评论这张
 
阅读(9212)| 评论(34)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017