目錄
1. 問題描述
2. 解題分析
2.1 DFS演算法流程
2.2 遍歷下一個狀態
3. 代碼及測驗
4. 后記
1. 問題描述
對喜愛棒球的少年而言，“三振出局”是一定要試一次的，這是一個在本壘上放置 9 個靶子，擊打投手投來的球，命中靶子的游戲，據說這可以磨練球手的控制力，
現在來思考一下這 9 個靶子的擊打順序，假設除了高亮的 5 號靶子以外，如果1個靶子有相鄰的靶子，則可以一次性把這 2 個靶子都擊落，譬如，如圖2所示，假設 1 號、6 號、9 號已經被擊落了，
那么接下來，對于 “2和3” “4和7” “7和8” 這3組靶子，我們就可以分別一次性擊落了，
求：9 個靶子的擊落順序有多少種？這里假設每次投手投球后，擊球手都可以擊中靶子，
2. 解題分析
第一感就是深度優先路徑搜索問題，因為本系列已經出現來太多這樣的問題，比如Q23, Q18, Q14, just to name a few.
2.1 DFS演算法流程
由于已經擊落的靶子就不能再用了，所以靶盤狀態用尚未被擊落的靶子的串列表示即可，
2.2 遍歷下一個狀態
深度優先搜索的同一類問題都可以直接套用上一節所示的框架套路，除了一些problem-specific的細節需要針對個別問題具體處理，本問題的要點在于如何給出下一個狀態的遍歷串列來，
本題解采用(比較笨拙的)辦法如下：
首先，定義一個查找表，包括所有可能的double-strike（一次擊落兩塊）的可能組合，
其次，搜索當前的unStriked的2-combination’s，并查找各自是否出現在double-strike串列中，如果在的話則表明這是一種可能的double-strike結果，由此導致一種next-state
最后，所有unStriked的中靶子都可能被單獨擊落，也分別導致一種next-state
代碼參見findNext(unStriked)
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 12 08:49:46 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
double_strike = [{1,2},{1,4},{2,3},{3,6},{6,9},{8,9},{7,8},{4,7}]
class Solution:
def baseball_game(self, unStriked: List)->int:
"""
Parameters
----------
Returns : The number of order of striking
-------
"""
memo = dict()
def findNext(unStriked):
global double_strike
ansLst = []
strike2Lst= []
# Search for all possible double strikes
for item in it.combinations(unStriked, 2):
# print(item)
if set(item) in double_strike:
new = unStriked.copy()
new.remove(item[0])
new.remove(item[1])
ansLst.append(new)
strike2Lst.append(item)
# Search for all possible single strikes
for num in unStriked:
new = unStriked.copy()
new.remove(num)
ansLst.append(new)
# print('findNext: {0}-->{1}'.format(unStriked,ansLst))
return ansLst
def explore(unStriked):
"""
unStriked : The list of targets not yet striked
Returns : The number of order of striking
-------
"""
# print(unStriked)
if len(unStriked) == 0:
return 1
if tuple(unStriked) in memo:
return memo[tuple(unStriked)]
count = 0
nextUnStriked = findNext(unStriked)
for item in nextUnStriked:
count = count + explore(item)
memo[tuple(unStriked)] = count
return count
return explore(unStriked)
if __name__ == '__main__':
sln = Solution()
tStart = time.perf_counter()
count = sln.baseball_game([k for k in range(1,10)])
tCost = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost)) 運行結果：count = 798000, tCost = 0.004(sec)
4. 后記
本題說明其實是有一定模糊性（因為我一開始恰好掉到坑里去了）的，在關于一次能擊落兩塊的情況中，題意其實是說當除了5以外，任意兩塊連著的靶子，擊中其中任意一塊時可能只掉下被擊落的那一塊，也可能把相鄰的那一塊帶下去（但是兩邊都有相鄰靶子的話，也只會帶下一塊），這對應著實際的游戲情況應該是球正好幾種兩個靶子的交界處附近，對于實際玩過棒球或者觀看過類似電視節目的人來說可能是理所當然的，但是作為一道抽象的演算法題目來說則很難說是理所當然的，
既然說到這兒，這道題目可以稍微做一下條件修改：任意兩塊連著的靶子，擊中其中任意一塊時一定會連同相鄰的那一塊一起掉下去（兩邊都有相鄰靶子的話，也只會帶下其中某一塊），在這種條件下，9個靶子的擊落順序有多少種呢？
嗯，這道延申題目算不算有點原創的意思？^-^
上一篇：???????Q23: 二十一點通吃
下一篇：???????Q27: 禁止右轉
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299626.html
標籤：其他