1

教科书般的亵渎

 1 year ago
source link: https://piggerzzm.github.io/2020/02/05/%E6%95%99%E7%A7%91%E4%B9%A6%E8%88%AC%E7%9A%84%E4%BA%B5%E6%B8%8E/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

教科书般的亵渎

炉石传说里术士有一张非常强力的 AOE 卡牌 “亵渎”

xiedu

这张牌的效果是：对所有随从造成 1 点伤害，如果有随从死亡，则再次施放该法术。

在经过仔细地计算之后，即使是非常复杂的场面，也可能通过随从相互进行攻击，构造血量的等差数列，然后使用 2 费的亵渎达到清场。但在一个回合有限的思考时间里，这 “高等术学” 并不是那么容易计算出来的。

亵渎计算器

在编写亵渎计算器之前，先把这个问题描述清楚：

输入：给定敌方和我方不多于 7 个随从的攻击力、生命值、是否具有嘲讽、我方该随从本回合是否能进行攻击（暂时不考虑亡语、圣盾、风怒、复生等复杂的效果）

输出：所有全清场面的我方随从攻击方案

下面用 Python3.7 来实现：

先写一些测试用例和全局变量

a2 = [1, 2, 3] # 敌方随从攻击力
h2 = [2, 4, 4] # 敌方随从生命值
taunt = [0, 1, 0] # 敌方随从是否具有嘲讽

a1 = [1, 1] # 我方随从攻击力
h1 = [1, 2] # 我方随从生命值

flag = False # 是否有解
attack_record = [] # 用一个栈记录攻击
H1 = h1[:]
H2 = h2[:]
num_of_solutions = 0

然后写一个判断等差数列的函数，h1 和 h2 是存储敌方和我方随从生命值的列表，判断是否构成等差数列

def is_AP(h1, h2):
    maxH = max(max(h1), max(h2))
    for i in range(1, maxH):
        if i not in h1 and i not in h2:
            return False
    return True

再写一个主函数，如果初始就构成了等差数列就直接输出，不进行 DFS；如果不构成等差数列，则进行 DFS

def main():
    num_of_taunt = sum(taunt)
    if is_AP(H1, H2):
        print(attack_record)
        print(H2)
        print(H1)
        print("number of solutions: 1" )
    else:
        DFS(0, 0, num_of_taunt)
        if flag == False:
            print("No Solution.")
        print("number of solutions: " + str(num_of_solutions))

然后是 DFS 的实现：

这里需要传入的参数有三个，k1 和 k2 分别代表我方和敌方的随从序号，num_of_taunt 是敌方场上嘲讽随从的数量（这个会影响是否能进行攻击所以要记录）

分支分为两类：我方 k1 攻击敌方 k2，我方 k1 不攻击敌方 k2

攻击分支：根据两个随从的生命值以及场上嘲讽的情况来进行剪枝

不攻击分支：要根据是否还有下一个敌方随从来进行判断

def DFS(k1, k2, num_of_taunt):
    # 已经构成等差数列
    if is_AP(H1, H2):
        global flag
        flag = True # 有解
        global num_of_solutions
        num_of_solutions = num_of_solutions + 1

print(attack_record)
        print(H2)
        print(H1)
        print('\n')

# 递归边界
    if k1 >= len(H1):
        return

# k1撞k2
    if H1[k1] >= 0 and H2[k2] >= 0: # 生命值不为负才能攻击
        if num_of_taunt == 0 or taunt[k2]: # 没有嘲讽随从或k2是嘲讽随从
            attack(k1, k2, num_of_taunt)

# k1不撞k2
    if k2+1 < len(H2): # 还有下一个敌方随从
        DFS(k1, k2+1, num_of_taunt)
    elif k1+1 < len(H1): # 没有下一个敌方随从
        DFS(k1+1, 0, num_of_taunt)

最后是攻击分支的具体实现：需要判断攻击之后是否会对敌方嘲讽状况发生影响

def attack(k1, k2, num_of_taunt):
    H1[k1] = H1[k1] - a2[k2]
    H2[k2] = H2[k2] - a1[k1]
    attack_record.append(str(k1) + " attack " + str(k2))
    if taunt[k2] and H2[k2] <= 0:
        DFS(k1+1, 0, num_of_taunt - 1)
    else:
        DFS(k1+1, 0, num_of_taunt)
    attack_record.pop(-1)
    H1[k1] = H1[k1] + a2[k2]
    H2[k2] = H2[k2] + a1[k1]

程序输出如下：

['1 attack 1']
[2, 3, 4]
[1, 0]


number of solutions: 1

敌方 1 号随从嘲讽，容易验证的确只有这一个解：我方 1 号随从攻击敌方 1 号随从，然后使用亵渎全解

第二、三行输出显示亵渎前敌方和我方随从剩余生命值，的确构成等差数列


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK