题目

Q4: 使Python或者C++完成以下问题(30分)

Spiral Memory

You come across an experimental new kind of memory stored on an infinite two dimensional grid. Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:

While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1. For example: Data from square 1 is carried 0 steps, since it’s at the access port. Data from square 12 is carried 3 steps, such as: down, left, left. Data from square 23 is carried only 2 steps: up twice. Data from square 1024 must be carried 31 steps. How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port? How to test your answer:

If you input: 100000 Your Answer should be: 173

If you input: 2345678 Your Answer should be: 1347

If you pass these 2 test cases, you can get the credits!

我的方法显然很繁琐,但这是开放性题目,能符合要求就行……

解析

我越来越觉得,拿到一道复杂题目,要学会拆分问题,把它拆分为能够完成的小步骤。是英文的,没关系,拆分!

step1:先做英语阅读理解

step2:用中文进行概括

大概意思是从1开始,对所有正整数做逆时针螺旋式依次排列,然后对于任意给定的数字,要求出它到1最短走几步(不允许走斜线)。

step3:画图进行可视化理解

红色箭头就是其螺旋排列的方式,而绿色箭头是12和15回到1需要走的最短路径的示意。可见,15想要回来最少得2步,而12则需要3步。

step4:观察这些数字回到1的共同点

那些与1在同一直线上的数字,以直线回来就是最短路径了;那些与1不在同一直线上的数字,则要先径直先走到与1在同一直线的位置,再以直线赶回来;

所以那些在十字位置的数字非常关键,直觉上我们会感觉找到它的规律将很有利于解题。

step5:寻找“十字数字”规律

不直观?把它们按顺序依次写出来:

1 2 4 6 8 11 15 19 23

不够多?扩充一圈,多增加些:

1 2 4 6 8 11 15 19 23 28 34 40 46

根据与1的距离,这些数字是一圈一圈地分组的:

1是第一圈,为初始值1;1到2加了1,这个1即为2,、4、6、8这一圈共同距离1的步数,且2,、4、6、8相隔都2;8到11这里由于向外扩展了新的一圈,因此相较于2,、4、6、8圈内以步数2循环,8到11需要走3步;

依次类推,第3圈以其边长4进行圈内循环3次,再以步数5进入更外一圈,然后在其中以步数6进行3次圈内循环……

以上是几何观察的结果,数学问题一般能从几何和算术两大角度进行思考,我们在算术上验证一下:

确实,算术上也符合观察结果。

step6:构思程序

这道题要求最后是输入任何一个数,输出它到1的步数,所以如果生成的参照对象——“十字数”应该是动态的,不可能是先生成好所有的“十字数”(无限多),再去算步长。因此我们选择动态的形式来生成“十字数”,对应Python里就是“生成器”了。生成器可以动态地计算出下一个数,例如斐波拉契的生成器写法:

def fib(max): 
    n, a, b = 0, 0, 1
    while n < max:
        yield b
        a, b = b, a + b
        n = n + 1
        return 'done'

这个函数在进入while循环后,yield b将返回b,但是不像return b,yield b调用后,如果下次再次调用这个函数(用next()),它将从yield b这条语句下面接着走,在while循环里再走一遍,结果b被赋值为前它前面两个数之和后,又碰到了yield b,这时返回b,下次调用依次类推。可见,生成器是可以动态地生成序列。当循环跳出而遇到return后,没有新的数字生成了,用next()再次调用将抛出StopIteration的错误。

step7:依据思路写代码

def get_number(number): # 对于给定数字number
    n, i, gap, count = 1, 0, 1, 3 # n代表当前“十字数”,i代表圈内增量;count是计数器(圈内走3趟)
    distance = 0 # gap代表进入下一圈时所需增量,distance记录当前圈的“十字数”距离1的步数
    max_min = 0 # max_min代表比number小或等于的最大“十字数”
    while n <= number: # 当生成的“十字数”小于等于number时
        max_min = n # 记录目前小于等于number的最大“十字数”,并不断更新
        yield n # 返回当前十字数
        if count < 3: # 圈内循环3趟
            count = count + 1
            n = n + i # 根据圈内增量计算出新的“十字数”n
        else: # 当count为3时,就该换圈子了
            n = n + gap # n加换圈增量则成为新圈子的“十字数”
            if n > number: # 我发现当n大于number时,大循环不会跳出,整个else语句会全部执行完
                break # 为了防止下面那列“十字数”的distance错误变成了下一圈的distance,故break
            distance = distance + 1 # 当前圈的“十字数”距离1的步数增加1
            gap = gap + 2 # 换圈增量变化+1 +3 +5,每增一圈加2
            i = i + 2 # 每换圈后圈子大了,圈内自增量增加
            count = 0 # count变化,以便下一循环中进入圈内循环3次

    # 跳出了循环,说明max_min <= number,而n > number且n为下一个“十字数”
    if number == max_min: # 如果number恰好是等于它的最大十字数,则直接以直线返回1,步数为distance
        return distance
    else: # 如果number不等于max_min
        if n-number > number-max_min: # 看其与上一个“十字数”max_min与下一个“十字数”n哪个近
            return number-max_min+distance # 选择近的进行步数计算,返回结果
        else:
            return n-number+distance

number = int(input("Please enter the number: "))
o = get_number(number)
while True:
    try:
        x = next(o)
        # print('n:', x)
    except StopIteration as e:
        print(e.value)
        break

跳出循环后,步数计算显然是看number距离前后哪个“十字数”近,把其到更近的“十字数”步数与“十字数”到1的步数相加即可。

测试

测试成功!

评论(网址可空)