Python算法笔试题目，破解Hash值，回溯法

Find the string which has this hash: 25267566250558

The string has length8.

Characters can befrom: c,e,i,a,r,w,u,s,p

The hash functionworks like this:

hash(str):

    1.LETTERS = c, e, i, a, r, w, u, s, p

    2. h =7

    3. forc in str:

        1.i = index of c in LETTERS

        2.h = 37 * h + i

    4.return h

Please send us thestring you found, and the code you used to find it.

上边是题目。

下边是使用回溯法的枚举解法，运行代码几分钟后出现结果：

# calculate the hash number of the str_hash
str_hash_length = 8
hash_result = 25267566250558
LETTERS = [\'c\', \'e\', \'i\', \'a\', \'r\', \'w\', \'u\', \'s\', \'p\']
 
 
def calculate_hash(str_hash):     
    h = 7
    for c in str_hash:
        # print c
        i = LETTERS.index(c) #+ 1 ###
        # print i,
        h = 37*h + i
    return h
 
## for test of calculate_hash()
# str_hash = \'ec\'
# print calculate_hash(str_hash)
 
 
## calculate the str_hash using n-nary and recursive
# instialize a list to store the characters
str_hash_list = [\'\' for i in xrange(str_hash_length)]
# print \'the type is \',type(str_hash_list)
def find_str(k):    
    if str_hash_length == k:        
        # this conversion can move to just before it needs to print
        str_hash = \'\'.join(str_hash_list)
        str_hash_value = calculate_hash(str_hash)        
        # print str_hash_value
        if str_hash_value == hash_result:
            print \"yes! the string \'%s\' is found ,its hash is %d\" %(str_hash,str_hash_value)
        #return   ##!neglected, will it be ok when negelected?, ans: yes
 
        ## can add
 
    else:
        for c in LETTERS:
            #if str_hash_list[len(str_hash_list)-1] is not \'\':
            #print str_hash_list               
            str_hash_list[k] = c
            find_str(k+1)
 
def main():
    find_str(0)
 
if __name__ == \'__main__\':
    main()