登录  /  注册
php - 日本雅虎程序员跳槽程序测试问题
PHPz
PHPz 2017-04-10 15:36:19
[PHP讨论组]
0 14 1025
举报

一救援机器人有三种跳跃模式，可分别跳跃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
PHPz
PHPz

学习是最好的投资！

全部回复(14)
迷茫
迷茫2017-04-10 15:38:19 14楼

谢谢邀请。

出这道题，明显是为了考察你 DP。我也不多说，直接放码过来了：

cppvoid step(int n, std::string str) {
    if (n == 0) { std::cout << str << "\b " << std::endl; }
    if (n >= 1) step(n-1, str+"1m,");
    if (n >= 2) step(n-2, str+"2m,");
    if (n >= 3) step(n-3, str+"3m,");
}

当 n == 4 的时候，调用：step(4, ""); 原样输出你想要的。

这里只是用最短的代码表述我的思路，怕爆栈的，自行修改。
赞 +0
添加回复
天蓬老师
天蓬老师2017-04-10 15:38:19 13楼

It is quite similar to my Facebook interview question: a game has 3 levels of scores: 1 point, 2 points, 5 points. please print all the ways you can get 10 points.
赞 +0
添加回复
PHPz
PHPz2017-04-10 15:38:19 12楼

简单想了一下，这道题目优化思路和斐波那契数列的优化思路相同:记录f(n)。

根据题目可知f(n)=f(n-1)+f(1)=f(n-2)+f(2)=f(n-3)+f(3)=f(1)+f(n-1)=..
手机码字后面两个等式就不写了。
f(n)的可能也就这6种(当然肯定包含重复)

那么一点点推导f(4)因为f123已知，f4可以在O(1)内得到，记录。
f5，此时f1234已知，f5也能在O(1)得到，记录。
那么f(n)，根据上述的公式，可以在O(n)内得到。

这是大致思路，接下来解决重复问题就行了。
赞 +0
添加回复
PHPz
PHPz2017-04-10 15:38:19 11楼

根据 @AUV_503516 的思路, 写以下代码, 存储结构和空间还可以优化

#!/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() # 缓存如 '11', '21' etc. 去重作用
    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) -> 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)
赞 +0
添加回复
黄舟
黄舟2017-04-10 15:38:19 10楼

用C写了一段:

unsigned int count(unsigned int n)
{
    switch(n) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 2;
        case 3: return 4;
        default: return (count(n - 1) + count(n - 2) + count(n - 3));
    }
    return 0;
}

运行结果：

n = 0; t = 0
n = 1; t = 1
n = 2; t = 2
n = 3; t = 4
n = 4; t = 7
n = 5; t = 13
n = 6; t = 24
n = 7; t = 44
n = 8; t = 81
n = 9; t = 149
...

好吧，原来是要详细列出每种方法的方案，我没认真看…… =_,=b
赞 +0
添加回复
高洛峰
高洛峰2017-04-10 15:38:19 9楼

直接采用递归的话会有很多重复的计算，比如在n=7的时候，会有1+1+1+steps(4)，1+2+steps(4)，3+steps(4)，所以step（4）会被重复计算多次。因此在需要做记忆之前的结果

int steps[LENGTH] = {0, 1, 2, 4};
int n, i;
for ( i = 4; i <= n; i++) {
        steps[i] = steps[i-1]+steps[i-2]+steps[i-3];
}
printf("%d\n", steps[n]);
赞 +0
添加回复
ringa_lee
ringa_lee2017-04-10 15:38:19 8楼

写个For循环算了，
赞 +0
添加回复
PHPz
PHPz2017-04-10 15:38:19 7楼

这也就OI初中组的水平......典型的动态规划一点儿弯儿都没绕
赞 +0
添加回复
怪我咯
怪我咯2017-04-10 15:38:19 6楼

这也就是考递归的问题.
赞 +0
添加回复
伊谢尔伦
伊谢尔伦2017-04-10 15:38:19 5楼

如果是要求一共有多少种方法，就可以简单用一位数组做动态规划。如果要求输出所有解，就老老实实的求吧。代码用递归写的。

JAVA    /**
     * return number of all distinct paths for a given distance..
     * O(n) time and O(n) space using dp.
     */
    public int allPath(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1; // useless
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }

    /**
     *
     * return all distinct paths for a given distance.
     *
     */
    public List<List<Integer>> allPaths(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(n, 0, new ArrayList<Integer>(), res);
        return res;
    }
    private void helper(int n, int cur, List<Integer> list, List<List<Integer>> res) {
        if (cur > n) {
            return;
        }
        if (cur == n) {
            res.add(list);
            return;
        }
        for (int i = 1; i < 4 && cur + i <= n; i++) {
            List<Integer> newList = new ArrayList<Integer>(list);
            newList.add(i);
            helper(n, cur + i, newList, res);
        }
    }
赞 +0
添加回复
专题推荐
更多>
热门话题
热门教程
更多>
相关教程
热门推荐
最新课程
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网：公益在线php培训，帮助PHP学习者快速成长！
关注服务号 技术交流群
app下载
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • 精品班

  • 技术支持

  • 技术咨询

  • 学习群

  • 会员优惠

  • 返回顶部