0

我必须编写一个给定国家名称的函数crossing，并且n（所需的步数）为您提供一组国家，我可以从给定国家开始穿越n个国家。

注意：

  • 在零步骤中，您无法从起始国家/地区退出；
  • 一步，您只能在边境国家获得；
  • 路径必须始终是最小的，例如，您可以从意大利到达比利时，穿越瑞士和德国，或者只有法国是第二个选择；
  • 您不能两次或多次穿越一个国家或返回，例如，意大利→瑞士→意大利或意大利→瑞士→法国是错误的。

这是我的地图：

neighborhood = {
'albania': ['greece', 'macedonia', 'serbia', 'montenegro'],
'andorra': ['spain', 'france'],
'austria': ['liechtenstein', 'switzerland', 'italy',
'czech republic', 'germany', 'slovakia',
'hungary', 'slovenia'],
'belarus': ['russia', 'lithuania', 'latvia', 'poland',
'ukraine'],
'belgium': ['luxembourg', 'germany', 'france', 'netherlands'],
'bosnia and herzegovina': ['montenegro', 'serbia', 'croatia'],
'bulgaria': ['romania', 'serbia', 'macedonia', 'greece'],
'croatia': ['bosnia and herzegovina', 'serbia', 'hungary',
'slovenia'],
'czech republic': ['slovakia', 'austria', 'germany', 'poland'],
'denmark': ['germany'],
'estonia': ['russia', 'latvia'],
'finland': ['sweden', 'russia', 'norway'],
'france': ['spain', 'andorra', 'monaco', 'luxembourg',
'belgium', 'germany', 'switzerland', 'italy'],
'germany': ['denmark', 'luxembourg', 'belgium', 'france',
'netherlands', 'poland', 'czech republic',
'austria', 'switzerland'],
'greece': ['bulgaria', 'macedonia', 'albania'],
'hungary': ['romania', 'ukraine', 'slovakia', 'austria',
'slovenia', 'croatia', 'serbia'],
'iceland': [],
'ireland': ['united kingdom'],
'italy': ['france', 'switzerland', 'austria', 'slovenia',
'san marino', 'vatican city'],
'latvia': ['russia', 'estonia', 'lithuania', 'belarus'],
'liechtenstein': ['austria', 'switzerland'],
'lithuania': ['russia', 'latvia', 'belarus', 'poland'],
'luxembourg': ['belgium', 'germany', 'france'],
'macedonia': ['bulgaria', 'serbia', 'albania', 'greece'],
'malta': [],
'moldova': ['ukraine', 'romania'],
'monaco': ['france'],
'montenegro': ['albania', 'serbia', 'bosnia and herzegovina'],
'netherlands': ['germany', 'belgium'],
'norway': ['sweden', 'finland', 'russia'],
'poland': ['russia', 'lithuania', 'belarus', 'ukraine',
'slovakia', 'czech republic', 'germany'],
'portugal': ['spain'],
'romania': ['ukraine', 'moldova', 'bulgaria', 'serbia',
'hungary'],
'russia': ['norway', 'finland', 'estonia', 'latvia',
'lithuania', 'belarus', 'ukraine', 'poland'],
'san marino': ['italy'],
'serbia': ['bosnia and herzegovina', 'hungary', 'croatia',
'montenegro', 'albania', 'macedonia', 'bulgaria',
'romania'],
'slovakia': ['hungary', 'austria', 'czech republic', 'poland',
'ukraine'],
'slovenia': ['italy', 'austria', 'hungary', 'croatia'],
'spain': ['portugal', 'andorra', 'france'],
'sweden': ['norway', 'finland'],
'switzerland': ['germany', 'france', 'liechtenstein', 'austria',
'italy'],
'ukraine': ['russia', 'belarus', 'poland', 'moldova',
'slovakia', 'hungary', 'romania'],
'united kingdom': ['ireland'],
'vatican city': ['italy']
}

测试主要是：

if __name__ == '__main__':
    print("*** From Italy in ")
    for steps in range(0,8):
        print("[{0}] = {1}".format(steps, crossing("italy", steps)))
    print("*** From Sweden in [5] steps, you get in", crossing('sweden', 5))
    print("*** From Germany in [2] steps, you get in", crossing('germany', 2))
    print("*** From Iceland in [3] steps, you get in", crossing('iceland', 3))

以及执行：

*** From Italy in 
[0] = {'italy'}
[1] = {'san marino', 'france', 'slovenia', 'austria', 'switzerland', 'vatican city'}
[2] = {'czech republic', 'hungary', 'luxembourg', 'andorra', 'liechtenstein', 'croatia', 'monaco', 'belgium', 'slovakia', 'germany', 'spain'}
[3] = {'ukraine', 'romania', 'netherlands', 'portugal', 'denmark', 'poland', 'serbia', 'bosnia and herzegovina'}
[4] = {'belarus', 'montenegro', 'lithuania', 'macedonia', 'moldova', 'albania', 'russia', 'bulgaria'}
[5] = {'finland', 'norway', 'latvia', 'estonia', 'greece'}
[6] = {'sweden'}
[7] = set()
*** From Sweden in [5] steps, you get in {'netherlands', 'denmark', 'serbia', 'luxembourg', 'france', 'slovenia', 'austria', 'croatia', 'belgium', 'switzerland', 'bulgaria'}
*** From Germany in [2] steps, you get in {'ukraine', 'belarus', 'italy', 'lithuania', 'andorra', 'slovenia', 'liechtenstein', 'slovakia', 'monaco', 'hungary', 'russia', 'spain'}
*** From Iceland in [3] steps, you get in set()

有人有什么建议吗？

我试着写：

def crossing(naz,step):
 vicini = border(naz)
 for i in range(step):
    next(vicini)
 return next(vicini)

def border(naz):
    vicini = set([naz])
    yield vicini
    yield neighborhood[naz]
4

2 回答 2

3

这是关于图论的任务，这个问题在“Python 算法：掌握 Python 语言中的基本算法”一书中得到了解决。

于 2012-05-17T06:59:52.200 回答
0

根据我更好的判断，基本算法：

有三个数组：currently_at、going_to和been_to。对于每一步：添加到所有你没有going_to的唯一邻居。然后替换为，将它们添加到，然后清空。currently_atbeen_tocurrently_atgoing_tobeen_togoing_to

于 2012-05-17T06:51:48.170 回答