今天在 segmentfault 看到有趣的 编程题
描述如下:
” 一救援机器人有三种跳跃模式,可分别跳跃1m,2m,3m的距离,
请用程序实现该机器人行进n米路程时可用的跳跃方式。
程序语言不限,当距离n值足够大时,程序执行时间尽量小。
例:当距离为4米时,输出结果有7种:
1m,1m,1m,1m
1m,1m,2m
1m,2m,1m
1m,3m
2m,1m,1m
2m,2m
3m,1m
“
根据另一个用户 AUV_503516 提供的思路,
转会为数学的思考方式:
由条件定义 f(n) 为 n米的可用步骤序列.
f(1) = ( (1), )
f(2) = ( (1, 1), (2,) )
f(3) = ( (1, 1, 1), (1, 2), (2, 1), (3,) )
求 f(n), 每一跳跃可以使用的距离是 1, 2, 3
f(n) = f(1) + f(n-1) = f(2) + f(n-2) = f(3) + f(n-3)
= f(n-1) + f(1) = f(n-2) + f(2) = f(n-3) + f(3)
另外 f(delta) + f(n – delta) 有可能与 f(n – delta) + f(delta) 是用一个序列,
求 f(n) 需要去重.
由公式定义, 使用 Python代码实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #!/usr/bin/env python3 # -*- coding: utf-8 -*- # # @file robot_steps_calculator.py # @author kaka_ace # @date Mar 27 2015 # @breif # import copy class RobotBrain(object): CACHE_INIT = { 1: [['1']], 2: [['1', '1'], ['2']], 3: [['1', '1' ,'1'], ['1', '2'], ['2', '1'], ['3']], } CACHE_KEY_MAP_INIT = dict() for k, v in CACHE_INIT.items(): for l in v: s = "".join(l) CACHE_KEY_MAP_INIT[s] = True def __init__(self): self.cache = copy.deepcopy(self.CACHE_INIT) self.cache_key_map = copy.deepcopy(self.CACHE_KEY_MAP_INIT) def output_solution(self, n: "total length, positive number") -> None: if n <= 3: print(RobotBrain._ouput_result(self.cache[n])) return i = 4 while i <= n: """ f(i) = 1 + f(i-1) = 2 + f(i-2) = 3 + f(i-3) = f(i-1) + 1 = f(i-2) + 2 = f(i-3) + 3 we need to remove duplicates """ self.cache[i] = [] for step in range(1, 4): self._add_to_cache(1, i, True) self._add_to_cache(2, i, True) self._add_to_cache(3, i, True) self._add_to_cache(1, i, False) self._add_to_cache(2, i, False) self._add_to_cache(3, i, False) i += 1 self._ouput_result(self.cache[n]) def _add_to_cache(self, delta: int, i: int, reverse: bool) -> None: for sl in self.cache[i-delta]: s = ''.join(sl) delta_str = str(delta) if reverse is True: # delta + f(i - delta) new_key = delta_str + s else: # f(i - delta) + delta new_key = s + delta_str if new_key not in self.cache_key_map: self.cache_key_map[new_key] = True self.cache[i].append([delta_str] + sl) @staticmethod def _ouput_result(cache_list: list) -> None: for cache_result in cache_list: print(",".join([i+"m" for i in cache_result])) if __name__ == "__main__": r = RobotBrain() r.output_solution(5) |
segmentfault 帖子里也附上 回复 :)
联系客服