我想创建一个函数,我给它一个数字,该函数返回一个从 1 到该数字的螺旋线(在二维数组中)。例如,如果我将数字 25 赋予函数,它将返回如下内容:
我尝试了不同的方法,但没有任何结果。我就是想不通。
希望我能正确解释自己。
4 回答
这里的主要问题是枚举坐标之一 - 将数字与坐标匹配,然后根据需要打印出来。
首先注意两个基本模式:
- (方向)向右移动,然后向下,然后向左,然后向上,然后......(希望这是显而易见的)
- (幅度)移动一,然后一,然后二,然后二,然后三……
因此,根据这些规则,编写一个生成number, coordinates
元组的生成器。
如果你先设置一些辅助函数,那是最清楚的;我会更加冗长:
def move_right(x,y):
return x+1, y
def move_down(x,y):
return x,y-1
def move_left(x,y):
return x-1,y
def move_up(x,y):
return x,y+1
moves = [move_right, move_down, move_left, move_up]
很简单,现在生成器:
def gen_points(end):
from itertools import cycle
_moves = cycle(moves)
n = 1
pos = 0,0
times_to_move = 1
yield n,pos
while True:
for _ in range(2):
move = next(_moves)
for _ in range(times_to_move):
if n >= end:
return
pos = move(*pos)
n+=1
yield n,pos
times_to_move+=1
演示:
list(gen_points(25))
Out[59]:
[(1, (0, 0)),
(2, (1, 0)),
(3, (1, -1)),
(4, (0, -1)),
(5, (-1, -1)),
(6, (-1, 0)),
(7, (-1, 1)),
(8, (0, 1)),
(9, (1, 1)),
(10, (2, 1)),
(11, (2, 0)),
(12, (2, -1)),
(13, (2, -2)),
(14, (1, -2)),
(15, (0, -2)),
(16, (-1, -2)),
(17, (-2, -2)),
(18, (-2, -1)),
(19, (-2, 0)),
(20, (-2, 1)),
(21, (-2, 2)),
(22, (-1, 2)),
(23, (0, 2)),
(24, (1, 2)),
(25, (2, 2))]
这是一个图表,可以帮助您思考问题:
您可以将其视为重复添加到 NxN 正方形以生成 (N+1)x(N+1) 正方形:
if N is odd:
move right one step
move down N steps
move left N steps
else:
move left one step
move up N steps
move right N steps
并且在每一步中,您都会在当前位置写入一个数字。
正如@Milan 指出的那样,您可能并不总是想要完成当前的外壳(即,如果您只想数到 23)。最简单的方法是创建一个生成器函数,它会产生无穷无尽的步骤流,然后只使用所需的步骤:
from itertools import count
def steps_from_center():
for n in count(start=1):
if n % 2:
yield RIGHT
for i in range(n):
yield DOWN
for i in range(n):
yield LEFT
else:
yield LEFT
for i in range(n):
yield UP
for i in range(n):
yield RIGHT
在使用它之前,我们必须决定如何存储值,并在此基础上决定如何表示UP
、DOWN
、LEFT
和RIGHT
。
最简单的存储是二维数组,或者在 Python 术语中是列表列表。外部列表将保存输出的行,内部列表将分别保存一行中的单元格,并且每个单元格可以被寻址为my_array[y][x]
x 从左到右增加,y 从上向下增加(这符合我们期望的顺序打印输出)。
这使我们能够定义我们的方向:
from collections import namedtuple
Step = namedtuple("Step", ["dx", "dy"])
RIGHT = Step( 1, 0)
DOWN = Step( 0, 1)
LEFT = Step(-1, 0)
UP = Step( 0, -1)
在分配存储空间之前,我们需要知道我们需要多大的数组:
from math import ceil, floor, log10, sqrt
max_i = int(input("What number do you want to display up to? "))
# how big does the square have to be?
max_n = int(ceil(sqrt(max_i)))
# here is our initialized data structure
square = [[EMPTY] * max_n for _ in range(max_n)]
# and we start by placing a 1 in the center:
x = y = max_n // 2
square[y][x] = output(1)
我在这里添加了两个额外的部分:为了使输出整洁,每个项目都应该打印相同的宽度。output()
是一个函数,它接受一个值并返回一个正确宽度的字符串,并且EMPTY
是一个该宽度的空格字符串:
# how many digits in the largest number?
max_i_width = int(floor(log10(max_i))) + 1
# custom output formatter - make every item the same width
def output(item, format_string="{{:>{}}}".format(max_i_width)):
return format_string.format(item)
EMPTY = output("")
现在碎片就位,我们可以生成螺旋:
for i, step in enumerate(steps_from_center(), start=2):
if i > max_i:
break
else:
x += step.dx
y += step.dy
square[y][x] = output(i)
并打印出来:
print("\n".join(" ".join(row) for row in square))
它运行如下:
What number do you want to display up to? 79
73 74 75 76 77 78 79
72 43 44 45 46 47 48 49 50
71 42 21 22 23 24 25 26 51
70 41 20 7 8 9 10 27 52
69 40 19 6 1 2 11 28 53
68 39 18 5 4 3 12 29 54
67 38 17 16 15 14 13 30 55
66 37 36 35 34 33 32 31 56
65 64 63 62 61 60 59 58 57
有几个步骤可以解决问题。首先,建立一个网格。网格的大小需要等于下一个更高的完美正方形;例如,如果输入 23,则需要 5 × 5 (25) 的网格,或者如果输入 31,则需要 6 × 6 (36) 的网格。接下来,将数列的下一个值存储在“当前位置”(即中心)中。在每一步检查基本方向,将“当前位置”移动到之前没有填写过的最靠近中心的位置,偏向东方(处理初始步骤,这里没有区别在 N、S、E、W 中)。继续直到您的迭代器完成。
编辑:我真的很喜欢这个问题,所以我写了一个很好的解决方案。自从我写 Python 以来已经有一段时间了,所以这可能不是最优雅的,但尽管如此。
from functools import partial
from math import ceil, sqrt
def gen_grid(n):
grid_size = int(ceil(sqrt(n)))
return [[None for _ in range(grid_size)] for _ in range(grid_size)]
def valid_coord(grid, coord):
try:
return grid[coord[0]][coord[1]] is None
except:
return False
def origin(size):
adjustment = 1 if size % 2 == 0 else 0
return (size / 2 - adjustment), (size / 2 - adjustment)
north = lambda y, x: (y - 1, x)
south = lambda y, x: (y + 1, x)
east = lambda y, x: (y, x + 1)
west = lambda y, x: (y, x - 1)
directions = lambda y, x: [east(y, x), south(y, x), west(y, x), north(y, x)]
distance = lambda c, nxt: sqrt((c[0] - nxt[0]) ** 2 + (c[1] - nxt[1]) ** 2)
def walk_grid(nums):
grid = gen_grid(len(nums))
center = origin(len(grid[0]))
current_position = center
center_distance = partial(distance, center)
for n in nums:
y, x = current_position
grid[y][x] = n
unseen_points = [c for c in directions(y, x) if valid_coord(grid, c)]
if n != nums[-1]:
current_position = sorted(unseen_points, key=center_distance)[0]
return grid
def print_grid(highest):
result = walk_grid(range(1, highest + 1))
for row in result:
for col in row:
print "{:>4}".format(col if col is not None else ''),
print "\n"
示例输出:
In [2]: grid.print_grid(25)
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
所以我假设你已经可以以某种方式确定数组的大小和“一”的位置。现在你需要一个允许你改变方向的函数和一个计数器。
def get_new_direction(direction):
switch direction:
case E: return S
case S: return W
case W: return N
case N: return E
i,j = initial_coordinates_of_the_one
direction = right
steps = 1
next_number = 1
while not done:
place(next_number, i, j)
i,j = get_coordinates_after_move(direction, steps)
direction = get_new_direction(direction)
next_number++
if iteration is even:
steps++
这只是一个草图。仍然缺少什么(但很容易弄清楚):
- 如何实现功能
- 如何在一个方向设置多个数字