2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q34: 会有几次命中注定的相遇(2)

时间:12-29来源:作者:点击数:42

0. 前情概要

参见:Q34: 会有几次命中注定的相遇

1. 分析

如上所述,在满足相遇的两种条件之一后即提前退出会导致大量的路径(满足相遇条件后的路径分岔)被漏算了。正确的做法是只要不出界,就必须一直走到底。由此可以看出在之前的错误的解答中的以下4个return的条件(如下图所示)中,第2个、第3个、第4个其实都是错的,都是不需要的。

第3、4个的错的原因已经解释了,其实不能提前退出,每条路径都走到底再做判断。

其中第2个是错误的原因还需要再追加一点解释。第2个return是基于这样的考虑:(在错解中认为)一旦找到满足条件的就应该提前退出,而如果两者都已经擦肩而过(满足了“manX > womanX and manY > womanY”之后就不可能再相遇了)且还没有满足条件的话就不必继续搜索下去了。而现在要求不管是否已经满足条件,都必须每条路径走到底,这个return自然就不再需要了。因为任何一对路径不管是否满足相遇的条件下,最后一段都必然是满足“manX > womanX and manY > womanY”条件的。

进一步如以下代码所示统计条件和退出条件做了一些调整优化。

首先meet递增改为针对X坐标和Y坐标分别统计。X和Y坐标同时相同(即题设中的相互解除状态)无非就是统计成加2而已(反正现在不比提前退出)。这样做的好处是统一了两种相遇的情况的统计。

此外,最终判断是否满足相遇条件是用(meet>=2),有人可能会有疑惑会有meet>2的情况吗?是的。因为统计是每走一步都统计的,考虑两者在某一点相遇后两者继续朝相反方向走,那两人的某一个坐标必定继续保持一致,因此会导致meet一直增加直到到达边界不得不转向为止。

2. 代码

  • # -*- coding: utf-8 -*-
  • """
  • Created on Sun Sep 19 08:24:18 2021
  • @author: chenxy
  • """
  • import sys
  • import time
  • import datetime
  • import random
  • from typing import List
  • from collections import deque
  • import itertools as it
  • 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 == N and manY == M and womanX == 0 and womanY == 0:
  • # Can be simplied as below:
  • if manX == N and manY == M:
  • # Both people reach their target respectively, then do the judgement
  • if meet >= 2:
  • total_count += 1
  • return
  • if manX == womanX:
  • meet += 1
  • if manY == womanY:
  • meet += 1
  • # 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
  • 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 = 527552, tCost = 1.438(sec)

3. 后记

在很多的路径遍历搜索问题中的确是一旦找到目标(满足要求)就停止继续搜索下去的。前面的错解恰恰是掉在了这样的惯性思维所造成的陷阱中。

反过来说,完全通用的解题策略是不存在的。每一个实际问题都有它的一些独特的地方需要仔细分析case-by-case地处理。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门