给出一个单词,打印其索引,可以相应增加单词

Question

想象一下单词的字母.

例:

 a ==> 1 
 b ==> 2 
 c ==> 3 

 z ==> 26 
 ab ==> 27 
 ac ==> 28 

 az ==> 51 
 bc ==> 52 
 and so on. 

这样字符序列只需要按升序排列(ab有效但ba不是).给定任何单词如果有效则打印其索引,否则打印0.

 Input  Output 

 ab      27 

 ba       0 

 aez     441 

在这个问题中,我可以轻松地做数学,但我没有得到任何算法.

我在数学方面所做的是

一封信26

两封信325

.

.

.

等等

Answer 1

1. 首先制作所有字母数字:
   • 'aez'将成为1,5,26
2. 将这些数字变量称为...... X3,X2,X1
   • 26将是X1,5将是X2,1将是X3(注意,从右到左)

现在为神奇的公式:

即使在最糟糕的情况下,也可以通过示例和速度演示进行编码:

def comb(n,k): #returns combinations
    p = 1 #product
    for i in range(k):
        p *= (n-i)/(i+1)
    return p

def solve(string):
    x = []
    for letter in string:
        x.append(ord(letter)-96)  #convert string to list of integers
    x = list(reversed(x))  #reverse the order of string
    #Next, the magic formula
    return x[0]+sum(comb(26,i)-comb(26-x[i-1]+1,i)*(1-i/(26-x[i-1]+1)) for i in range(2,len(x)+1))

solve('bhp')
764.0
>>> solve('afkp')
3996.0
>>> solve('abcdefghijklmnopqrstuvwxyz')
67108863.0
>>> solve('hpz')
2090.0
>>> solve('aez')
441.0
>>> if 1:
        s = ''
        for a in range(97,97+26):
                s += chr(a)
        t = time.time()
        for v in range(1000):
                temp = solve(s)
        print (time.time()-t)


0.1650087833404541

为了理解我对这个公式的解释,我需要在pascal三角形和二项式定理中检验数学:

这是pascal的三角形:

从右上角到左下角,首先是一系列的1.然后是一系列计数数字.下一个序列是计数数字的总和.这些被称为三角数.下一个序列是三角形数字的总和,称为四面体数字,这种模式继续进行.

现在为二项式定理:

通过组合二项式定理和帕斯卡三角形,可以看出第n个三角形数是:

和第n个四面体数是:

前n个四面体数的总和是:

并...

现在来解释一下.对于这个解释,我将只使用6个字母af,并将用数字1-6替换它们.程序与更多字母相同

如果长度为1,那么可能的序列是:

1
2
3
4
5
6

在这个答案就是价值

现在长度为2:

12  13  14  15  16
23  24  25  26
34  35  36
45  46
56

为了解决这个问题,我们将其分为三部分:

1. 查找上面行中的元素总数
   • 在这种情况下,第一行中有5个元素,第二行中有4个元素,第三行中有3个,依此类推.我们要做的是找到一种方法来对序列的前n个元素求和(5,4,3,2,1).为此,我们减去三角形数字.(1 + 2 + 3 + 4 + 5) - (1 + 2 + 3)=(4 + 5).类似地(1 + 2 + 3 + 4 + 5) - (1 + 2)= 3 + 4 + 5.因此该值等于:
     • 
2. 现在,我们已经考虑了高于目标的值,并且仅关注它所在的列.为了找到这个,我们添加x1-x2
3. 最后,我们需要添加长度为1的序列.这等于6.因此,我们的公式是:
   • 

接下来我们将重复长度为3的序列:

123  124  125  126
134  135  136
145  146
156

234  235  236
245  246
256

345  346
356

456

我们再次将此问题分解为以下步骤:

1. 找出每个数组上方有多少个元素.数组值是向后的三角形数字(10,6,3,1).这一次,我们减去四面体数字,而不是减去三角形数字:
   • 
2. 注意每个单独的数组如何具有长度为2的序列的形状.通过从x1和x2中减去x3,我们将序列减少到2度.例如,我们将从第二个数组中减去2

这个

234  235  236
245  246
256

变

12  13  14
23  24
34  

3. 我们现在可以使用长度为2的公式,使用6-x3而不是6,因为我们的序列现在具有不同的最大值
   • 
4. 最后,我们添加长度1和长度2序列的总数.事实证明,存在特定长度的序列数量的模式.答案是组合.有 长度为1的序列, 长度为2,依此类推.

将这些长度为3的总公式组合成:

对于更高长度的序列,我们可以遵循这种减少模式

现在我们将使用我们的公式来寻找模式:

长度1:y1

长度2:

长度3:

注意:我还使用长度4来确保保持模式

通过一些数学,术语分组,以及从6到26的变化,我们的公式变为:

为了进一步简化这一点,必须进行更多的数学运算.
这个身份适用于所有a和b.为了快速有趣的练习,证明它(并不是很难):

这种身份允许进一步分组和否定术语以达到我们过于简单的公式: