目錄
1. 問題描述
2. 解題分析
3. 代碼及測驗
4. 后記
1. 問題描述
假設存在如下圖的正方形，該正方形被劃分成了邊長為1的正方形的格，男生從A到B，女生從B到A，分別沿著最短路徑以相同速度前行（兩人同步，每次都橫向或縱向各走一格），如果符合以下情形，則判定為“命中注定的相遇”
- ?兩次同時停在同一直線內的定點上（相互可見狀態）
- ?在同一頂點交匯（相互接觸狀態）
邊長為3時，幾種成功和失敗的例子如上圖所示，
問題：邊長為6時，發生“命中注定的相遇”的情況共有多少種？
2. 解題分析
兩人都是以最短距離行進，因此男生只有{向右，向下}兩種選項，女生只有{向左，向上}兩種選項，兩人的組合動作因此就是四種：
(1) {男:右；女:左}；
(2) {男:下；女:左}；
(3) {男:右；女:上}；
(4) {男:下；女:上}；
每前進一步，進行是否符合條件的判斷，如果是符合條件(a) ，則直接判斷成功；如果是符號條件(b)，將相互可見次數加1，如果相互可見次數到達2則判定成功；如果女生已經跑到男生的左上位置而還尚未滿足條件的話，則可以判定失敗；最后（作為邊界條件），如果發生越界的話也判定失敗，
這種型別的問題很適合于用遞回的方式實作（唯一需要擔心的是遞回深度），演算法流程如下所示：
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 19 08:24:18 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
from math import sqrt, floor, ceil
import numpy as np
N = 6
M = 6
total_count = 0
def f(manX, manY, womanX, womanY, meet):
# print(manX, manY, womanX, womanY, meet)
global total_count
if manX > N or manY > M or womanX < 0 or womanY < 0:
return # Cross the boundary
if manX > womanX and manY > womanY:
return # Missed forever
if manX == womanX and manY == womanY:
total_count += 1
# print(total_count)
return
if manX == womanX or manY == womanY:
meet += 1
if meet == 2:
total_count += 1
# print(total_count)
return
# Four possible move combination of two people
f(manX+1, manY, womanX-1, womanY, meet)
f(manX+1, manY, womanX, womanY-1, meet)
f(manX, manY+1, womanX-1, womanY, meet)
f(manX, manY+1, womanX, womanY-1, meet)
# return -- No need, Should not come to this point.
tStart = time.perf_counter()
f(0, 0, N, M, 0)
tCost = time.perf_counter() - tStart
print('total_count = {0}, tCost = {1:6.3f}(sec)'.format(total_count,tCost)) 運行結果：total_count = 15752, tCost = 0.026(sec)
4. 后記
這道題目算是最近幾道問題感覺最為輕松的，難得地很快就想清楚了解決方案，
然而，令人尷尬的是，答案錯了，更令人尷尬的是，“偷看”了原書答案以及CSDN上其他小伙伴們貼出來的答案，基本思路是一致的，運行別人的代碼也的確給出了正確答案，可是反復對比看仍然沒有看出自己的代碼究竟錯在哪兒了—自信心受到了一萬點暴擊，
但是，與“看到一個正確的答案后：喔，原來如此”相比，也許看一個錯誤的答案并揪出其中的八阿哥（BUG）更具有挑戰性，也更有助益，所以，這里還是厚著臉皮貼出來供大家批判，并期待有人幫助我指出哪兒錯了^-^.
上一篇：Q33: 飛車與角行的棋步
下一篇：
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301456.html
標籤：其他
上一篇：魚入大海,龍出生天