[第40期]字符串的DNA 已结

prober

好象是排列组合问题

ldy

QUOTE:

适逢国庆，这次的题目较简单，属于送分的题目。

QUOTE:

普通的提取重复值，加了一些变化，打乱了字符顺序。

QUOTE:

第一种的解法是 把每个字符串或它的ASC码 按相同的顺序排列，形成新的统一的字符串，

QUOTE:

然后再利用字典提取重复值，论坛里有很多这样的列子。

QUOTE:

第二种比较快的方法是，利用每个asc码 进行特殊计算后累加，也可以得到相同的数字。

QUOTE:

xiangchendub会员 采用的此方法，Log(Abs(Asc码)) 返回 双精度浮点型，考虑到计算精度，取累加后的前15位 做为 DNA 值

QUOTE:

这种方法唯一的缺点： 在理论上存在出错的可能，两个不同的相当长的字符串，会有可能有一样的 DNA值。

QUOTE:

但这仅仅是理论上的，实际需要中出错的概率 无限接近 0 。所以在处理类似问题上，这种方法是相当可靠的，我曾尝试找出这样的两个字符串，但最终还是放弃了，即便是找出来了，也是毫无意义的“乱码”。

QUOTE:

第三种 方法 利用二进制数组，然后再对它排序，形成新的字符串作为 DNA，这种方法与第一种类似，但快很多。VB(A)中,二进制数组与字符串之间的 转化是非常快的，没有专用的函数，直接用 等于号（=） 赋值。

QUOTE:

会员中没有此类答案。

QUOTE:

第一和第三种方法都需要进行数组排序，类似的方法很多，冒泡法，快速法，桶式，希尔 堆式......搜索一下选择合适的套用就行了。

QUOTE:

 附件里 提供了两种比较快的方法。

[此贴子已经被作者于2008-10-23 2:50:47编辑过]

彭希仁

第二种方法我也想过,不过在两位数里面是非常容易出错的,如AD和CB就分不出来了。

当然要降低出错的概率,也是有方法的,他们的ASC码之和他们的ASC码平方之和都要相等,那么这种错识的机率就可以降到无限低。以此类推再来一个立方和就更准确了。

如：ASC码2、 5      3、  4   

2+5=7    2*2+5*5=29

3+4=7    3*3+4*4=25

HHAAMM

第二种方法我试过，在两位数里出错的机会很大的！！

HHAAMM

第二种应该不能算作一种方法，不可取！！

ldy

QUOTE:

以下是引用HHAAMM在2008-10-23 9:39:00的发言：
第二种方法我试过，在两位数里出错的机会很大的！！

请举个例子。是用  Log(Abs(Asc)) 相加得到的前15位，会出错？肯定有，但到底是那两个不同的字符串，可以用第二种方法得出一样的ＤＮＡ值，我很想知道。

13楼的附件 里用的是 第二 和 第三种 方法，请把你找出来的字符串，写到A列中，

如果字符串长度小于300，并且运行结果错误的话，有分相送。[em17]

我估计，符合这样标准的字符串肯定很长。

如果asc码平方相加 或 立方和 相加的话  ，一个是慢二一个是 在题目里已经添加这样的 字符串了。

“l86" 和 "249"  " afh"  和 "bdi"   “仍韧认” 和 “忍妊扔”  题目中的11 到48行 ，那些无意义的文字，并不是随手乱打的。

有些看起来完全不同的字符串，用平方或立方来计算的话，会得到相同的值。

[此贴子已经被作者于2008-10-23 18:25:28编辑过]

ldy

想到了一个更加 好的方法 可以不用按照取前15位 的做法，减少第二种方法的错误概率10倍。

13楼附件中的getDNA过程中两处地方 小改一下

 Dim DNA As Double, DNAS As String * 15    改为 Dim DNA As Double, DNAS As String

 DNAS = DNA                                改为  DNAS = Log(DNA)

如此一改 DNAS 的结果 像这样 "4.42151540977897" 最长15位数字（不含小数点）

其出错的概率 为 1/10^15 ， 10 兆分之一 ，如果不是刻意去计算的话，这辈子估计是碰不上的了。

d

HHAAMM

偶是这么得来的

Sub abc()
[a1] = "你" & Chr(1) & "好"
[a2] = "你好"
End Sub

这样弄偶是不是有些抬杠的意思呀[em04]

HHAAMM

另外二进制数组的方法偶也想到了，但当时想的简单了（就是把它们求和）

但大概的想了下，11根b求和后是一样的，所以就放弃了这种想法！！

zldccmx

哈哈，宁可错杀一千，也不放过一个! 不怕一万，就怕万一哦!

老朽以为，不能以几率论，哪怕是兆兆兆兆...........分之一，都是不可取的!

老朽是个循规蹈矩的人，所以对这种冒险做法不太认同!

因为，一旦错了就有可能造成无法挽回的损失!

老朽觉得，学术如此，生活更是如此! [em05][em05]