递归问题学习二之卡牌组合问题

问题：

给定17中卡牌，每种卡牌的数值为1-17的平方，给定一个攻击值，卡牌的数值代表卡牌的攻击值，达到这样的攻击值能有多少种组合方式

思路：

题目中的卡牌是可以重复使用的，这个问题是一个典型的递归算法的问题，我在写非递归的实现但是还没有完全写对，感觉是不是思路不对了，如果有已经实现的还望不吝赐教，下面给出来递归方法的简单的实现：

#!usr/bin/env python
#encoding:utf-8

'''
__Author__:沂水寒城
功能：python实现卡牌组合
'''


def deep(num_list,pos,score,m):
    '''
    递归
    '''
    if score==m:
        return 1
    elif m-score<num_list[pos]:
        return 0
    else:
        count=0
        for i in range(0,(m-score)/num_list[pos]+1):
            count+=deep(num_list, pos+1, score+i*num_list[pos],m)
            print '-----------------i={0}, count={1}-----------------------------'.format(i,count)
            print 'deep({0},{1},{2},{3})'.format(num_list, pos+1, score+i*num_list[pos],m)
        return count 


def puke(m):
    '''
    组合卡牌
    '''
    num_list=[]
    for i in range(1,18):
        num_list.append(i*i)
    return deep(num_list,0,0,m)


if __name__ == '__main__':
    #m=int(raw_input())
    #puke(m)
    for one in [11,20,100,177,200]:
        print '达到攻击力{0}，卡牌组合方式为：{1}'.format(one, puke(one))

结果如下：

-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,0,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,9,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,0,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,4,11)
-----------------i=2, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,8,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,0,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,1,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,10,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,1,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,5,11)
-----------------i=2, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,9,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,1,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,2,11)
-----------------i=1, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],3,11,11)
-----------------i=0, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,2,11)
-----------------i=1, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,6,11)
-----------------i=2, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,10,11)
-----------------i=2, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,2,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,3,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,7,11)
-----------------i=2, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,11,11)
-----------------i=3, count=2-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,3,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,4,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,8,11)
-----------------i=4, count=2-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,4,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,5,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,9,11)
-----------------i=5, count=2-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,5,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,6,11)
-----------------i=1, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,10,11)
-----------------i=6, count=2-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,6,11)
-----------------i=0, count=0-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,7,11)
-----------------i=1, count=1-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],2,11,11)
-----------------i=7, count=3-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,7,11)
-----------------i=8, count=3-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,8,11)
-----------------i=9, count=3-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,9,11)
-----------------i=10, count=3-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,10,11)
-----------------i=11, count=4-----------------------------
deep([1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289],1,11,11)
达到攻击力11，卡牌组合方式为：4

下面是去除递归过程打印的结果：

达到攻击力11，卡牌组合方式为：4
达到攻击力20，卡牌组合方式为：12
达到攻击力100，卡牌组合方式为：1116
达到攻击力177，卡牌组合方式为：14607
达到攻击力200，卡牌组合方式为：27482
[Finished in 1.7s]

最后

以上就是大气哈密瓜为你收集整理的递归问题学习二之卡牌组合问题的全部内容，希望文章能够帮你解决递归问题学习二之卡牌组合问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。