目錄
1. 問題描述
2. 解題分析
2.1 基本思路
2.2 動態規劃
2.3 演算法流程
3. 代碼及測驗
4. 后記
1. 問題描述
注意，本問題不區分人，只考慮各個座位被占用的不同順序的個數，
2. 解題分析
2.1 基本思路
每個人選座位時，首先看有沒有“超空位”（兩邊都沒有挨著人的空位暫稱為“超空位”），如果有則優先從“超空位”中選取，如果沒有超空位，則從空位中任選一個坐下（空位是一定有的，因為人數和座位數是相等的），
由于車廂中的作為安排方式（對面兩排），兩頭兩位的座位有一邊是一定不挨著人的，如何表達才最方便于實作呢？
借用棋盤問題中的圍欄思想，將兩排座位排成一排，但是兩頭和中間各插入一個dummy座位（不能坐人），這樣連同dummy座位總共有15個，可以表達為長度為15的陣列，Dummy座位置為”-1”表示不能坐人，正常座位初始化為“0”，被人占據了則復制為“1”，這樣，判斷一個正常座位是否為“超空位”，只要看它本身是否為0且兩邊都不是1（即為“0”或者“-1”），
2.2 動態規劃
考慮已經有k個座位被占了，從當前狀態出發往后的剩下的(12-k)個座位被占的順序數只與當前這個k個座位被占的狀態有關，而與它們被占的順序無關，因此這個可以用動態規劃的策略來解決，本題考慮用top-down的方式（遞回+memoization）來實作動態規劃策略，
2.3 演算法流程
演算法流程如下：
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 17 10:52:39 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
import numpy as np
memo = dict()
def isFull(pos):
return np.all(pos[1:7]) and np.all(pos[8:14])
def search(pos):
if tuple(pos) in memo:
return memo[tuple(pos)]
if isFull(pos):
return 1
cnt = 0
hasSuperEmpty = False
# Search super empty seat
for k in [1,2,3,4,5,6,8,9,10,11,12,13]:
if pos[k]==0 and pos[k-1]!=1 and pos[k+1]!=1:
pos[k] = 1
cnt = cnt + search(pos)
hasSuperEmpty = True
pos[k] = 0
if not hasSuperEmpty:
for k in [1,2,3,4,5,6,8,9,10,11,12,13]:
if pos[k]==0:
pos[k] = 1
cnt = cnt + search(pos)
pos[k] = 0
memo[tuple(pos)] = cnt
return cnt
N = 12 # Can't modify currently
pos = np.zeros(N+3)
pos[N//2+1] = -1
pos[N+2] = -1
tStart = time.perf_counter()
count = search(pos)
tCost = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost)) 運行結果：count = 14100480, tCost = 0.032(sec)
4. 后記
輕松搞定，
跳過了前面一些題目先做這道，是因為瀏覽了一下“高級篇”中的題目，大多數題目想2~3分鐘感覺沒有頭緒，先捏這種一看就覺得“順眼”的軟柿子捏一捏^-^，這種策略對于學習很重要，盲目地死磕一道題目花費太久時間容易產生挫折感從而打擊學習的積極性，有些問題一時沒有頭緒，放在腦袋里供閑暇時間想一想說不定更容易突然就有什么靈感，，，
上一篇：
下一篇：
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/321099.html
標籤：其他