给定一个字，打印的指数，也就是说，可相应增加 [英] given a word, print its index, words can be increased accordingly

问题描述

想象一下单词的字母。

例如：

  A ==＆GT; 1
 b ==＆GT; 2
 Ç==＆GT; 3

 ž==＆GT; 26
 AB ==＆GT; 27
 AC ==＆GT; 28

 AZ ==＆GT; 51
 BC ==＆GT; 52
 等等。
 

这样的字符序列必须按升序排列只（AB是有效的，但巴不是）。鉴于任何文字打印和0的索引，如果有效，如果没有。

 输入输出

 AB 27

 BA 0

 AEZ 441
 

在这个问题上，我可以很容易做数学，但我没有收到任何算法。

我就是这样做的数学是

一个字母26

两个字母的325

等

解决方案

1. 首先让所有的字母数字：
   • 在农业生态区将成为1,5,26
2. 请这些数字变量叫... X3，X2，X1
   • 26是X1，5是X2，1人X3（注意，从右到左）

现在的妙方：

$ C $光盘的例子，甚至在最坏的情况下演示速度：

高清梳（N，K）：#returns组合     p为1 #product     因为我在范围内（K）：         P * =（N-1）/第（i + 1）     返回p 高清解决（串）：     X = []     对于信中的字符串：         x.append（ORD（字母）-96）#convert字符串整数列表     X =列表（反转（X））#reverse串的顺序     #Next，神奇公式     返回X [0] +总和（梳（26，i）的-comb（26-X [I-1] + 1，I）*（1-I /（26-X [I-1] 1）），用于我在范围内（2，LEN（X）+1）） 解决（必和必拓） 764.0 ＆GT;＆GT;＆GT;解决（afkp） 3996.0 ＆GT;＆GT;＆GT;解决（ABCDEFGHIJKLMNOPQRSTUVWXYZ） 67108863.0 ＆GT;＆GT;＆GT;解决（HPZ） 2090.0 ＆GT;＆GT;＆GT;解决（农业生态区） 441.0 ＆GT;＆GT;＆GT;如果1：         S =''         对于在范围（97,97 + 26）：                 S + = CHR（一）         T = time.time（）         对于V IN范围（1000）：                 临时=解决（S）         打印（time.time（） - T） 0.1650087833404541

为了了解我的解释这个公式，我需要去在数学出现在杨辉三角与二项式定理：

下面是杨辉三角：

从右上方向左下方去，先有1秒的序列。然后计数数字序列。下一个序列是计数数字的总和。这些被称为三角号码。下一个序列是三角形数，被称为四面体数字的总和和这个图案上和去

现在的二项式定理：

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

和第n个四面体数为：

第一n-四面体数的和是：

和

现在的解释。对于这样的解释，我将只使用6个字母，自动对焦，并用数字1-6替换这些。该过程是相同的多个字母

如果长度为1，则可能的序列是：

  1
2
3
4
五
6
 

在这个简单的答案是值

现在的2的长度：

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

要解决这个问题，我们将其分成3个部分：

1. 找到元素在上面的行的总数
   • 在这种情况下，有在所述第二在第三的第一行中5个元素，4,3和等等。我们要做的是找到一种方法来总结序列（5,4,3,2,1）的第n个元素。为了做到这一点，我们减去三角形数。 （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
 

1. 我们现在可以使用长度2公式，6-X3，而不是6，因为我们的序列现在有一个不同的最大值
   • 
2. 最后，我们添加长度1和长度为2的序列的总数。原来有为特定长度有多少序列的图案。答案是组合。有长度为1的序列，长度为2，等等。

有长3结合以上我们的总公式变为：

我们可以按照减少这种模式更高的全长序列

现在，我们将纠正我们的公式来寻找模式：

长1：Y1

长度2：

长3：

注：我也用长度为4，以确保持有的模式

通过一点数学，计算的分组，并且改变从6到26我们的公式变为：

为了进一步简化这一点，更多的数学必须做到的。
这个身份成立的所有a和b。对于一个快速有趣的练习，证明这一点（不是真的很难）：

这个身份可以为另一组和否定方面，以达到我们太多过于简单的公式：

Imagine an alphabet of words.

Example:

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

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

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

Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.

 Input  Output 

 ab      27 

 ba       0 

 aez     441 

In this question, I can do math easily but I am not getting any algorithm.

What i did in math is

one letter 26

two letter 325

.

.

.

so on

解决方案

1. First make all the letters numbers:
   • 'aez' would become 1,5,26
2. Make these numbers variables called ...X3,X2,X1
   • 26 would be X1, 5 would be X2, 1 would be X3 (note, right to left)

Now for the magic formula:

Coded with examples and demonstration of speed even in worse case scenario:

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

In order to understand my explanation to this formula, I need to go over a mathematical occurrence in pascal's triangle and the binomial theorem:

Here is pascal's triangle:

Going from top right to bottom left, first there is a sequence of 1s. Then a sequence of the counting numbers. The next sequence is the sum of the counting numbers. These are known as the triangular numbers. The next sequence is the sum of the triangular numbers, known as the tetrahedral numbers and this pattern goes on and on.

Now for the binomial theorem:

By combining the binomial theorem and pascals triangle, it can be seen that the nth triangular number is:

and nth tetrahedral number is:

the sum of the first n tetrahedral numbers is:

and on ...

Now for the explanation. For this explanation, I will only use 6 letters, a-f, and will replace these with the numbers 1-6. The procedure is the same with more letters

If the length is 1, then the possible sequences are:

1
2
3
4
5
6

In this the answer is simply the value

Now for a length of 2:

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

To solve this we split it into 3 parts:

1. Find the total number of elements in the rows above
   • In this case, there are 5 elements in the first row, 4 in the second, 3 in the 3rd and so forth. What we have to do is find a way to sum the first n elements of the sequence (5,4,3,2,1). In order to do this, we subtract triangular numbers. (1+2+3+4+5)-(1+2+3) = (4+5). Similarly (1+2+3+4+5)-(1+2) = 3+4+5. Therefore this value is equal to:
2. Now, we have accounted for the values above our target and are only concerned with the column it is in. To find this, we add x1-x2
3. Lastly, we need to add the amount of length 1 sequences there are. This is equal to 6. Therefore, our formula is:

Next we will repeat for sequences of length 3:

123  124  125  126
134  135  136
145  146
156

234  235  236
245  246
256

345  346
356

456

Once again we split this problem into steps:

1. Find how many elements are above each array. The arrays values are the backwards triangular numbers (10, 6, 3, 1). This time, instead of subtracting triangular numbers we subtract tetrahedral numbers:
2. Notice how each individual array has the shape of a length 2 sequence. By subtracting x3 from x1, and x2, we reduce the sequence to degree 2. For example, we will subtract 2 from the second array

This

234  235  236
245  246
256

becomes

12  13  14
23  24
34  

1. We can now use the length 2 formula, with 6-x3 instead of 6, because our sequences now have a different maximum value
2. Lastly, we add the total number of length 1 and length 2 sequences. It turns out there is a pattern for how many sequences of a particular length there are. The answer is combinations. There are sequences of length 1, of length 2, and so on.

Combining these our total formula for length 3 becomes:

We can follow this pattern of reduction for higher length sequences

Now we will right out our formulas to look for patterns:

Length 1: y1

Length 2:

Length 3:

Note: I also used length 4 to make sure the patterns held

With a bit of math, grouping of terms, and the change from 6 to 26 our formula becomes:

In order to simplify this further, more math must be done.
This identity holds true for all a and b. For a quick fun exercise, prove it (not really difficult):

This identity allows as to further group and negate terms to reach our much oversimplified formula:

这篇关于给定一个字，打印的指数，也就是说，可相应增加的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！