V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
KomiSans
V2EX  ›  JavaScript

一个面试题 岗位是 FreeLancer 自己写了下

  •  
  •   KomiSans · 2021-10-14 21:50:55 +08:00 · 2326 次点击
    这是一个创建于 896 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如图: 51esaj.png

    我的个人解法->

    // 判断迁移数组的总和是否为 15
    function filcheck(ar) {
        return ar.reduce((x, k) => {
            return x + k
        }, 0) === 15;
    }
    
    function entrance() {
        // 定义原数据数组
        var constArr = [3, 5, 7];
        // 定义初始迁移数据数组
        var arrReserver = [0, 0, 0];
        // 奇偶数定义 回合制玩家判断
        var odvar = 0;
        // 循环判断条件
        while (!filcheck(arrReserver)) {
            // 当数组中的所有元素已被移除后直接跳出循环
            if (arrReserver.length === 1) break;
            // 生成数组中的随机下标
            var arrIdx = Math.floor(Math.random() * (constArr.length));
            // 两数组同位置上元素的偏差 代表还剩多少物件
            var bxa = constArr[arrIdx] - arrReserver[arrIdx];
            // 当剩余数量为 0 时 移除该行
            if (bxa === 0) {
                constArr.splice(arrIdx, 1);
                arrReserver.splice(arrIdx, 1);
                continue;
            }
            // 迁移数据数组对应行数量添加
            arrReserver[arrIdx] += Math.floor((Math.random() * (bxa)) + 1);
            // 代表玩家本身
            odvar++;
        }
        // 利用回合制进行判断是哪位玩家失败
        return odvar % 2 === 0 ? "player1" : "player2";
    }
    
    9 条回复    2021-10-15 20:47:56 +08:00
    gossip
        1
    gossip  
       2021-10-14 22:07:03 +08:00
    我不是程序员哈,这个用博弈论中逆向归纳即可,最后结论是,只要我先拿,我一定有必胜策略
    Xs0ul
        2
    Xs0ul  
       2021-10-14 22:10:22 +08:00 via Android
    具体的实现没看,但是 hardcore 这些数值在函数内而不是作为参数传进来,可能不够“优雅”
    zxCoder
        3
    zxCoder  
       2021-10-14 22:24:33 +08:00   ❤️ 1
    这是 nim 博弈吧

    虽然我理解不了什么叫做分成三行,每行还能自上而下 hhhhh
    cairnechen
        4
    cairnechen  
       2021-10-14 22:32:20 +08:00
    不知道你们有没有看过一个小说叫天才基本法,里面有这个
    MoYi123
        5
    MoYi123  
       2021-10-15 10:03:44 +08:00
    from functools import cache


    @cache
    def dp(one, two, three, pos):
    ____if one + two + three == 0:
    ________return pos
    ____for i in range(1, one + 1):
    ________if dp(one - i, two, three, not pos) == pos:
    ____________return pos
    ____for i in range(1, two + 1):
    ________if dp(one, two - i, three, not pos) == pos:
    ____________return pos
    ____for i in range(1, three + 1):
    ________if dp(one, two, three - i, not pos) == pos:
    ____________return pos
    ____return not pos


    # True 是 player1,False 是 player2
    print(dp(3, 5, 7, True))

    一般来说这种题目都是考算法吧.
    所以答案应该是求胜者,而不是用 random 模拟这个游戏.
    给一个时间复杂度是 O(n3)的解法.
    Junzhou
        6
    Junzhou  
       2021-10-15 14:00:33 +08:00
    这不就是博弈吗? nyist oj 上 取石子
    flyingghost
        7
    flyingghost  
       2021-10-15 17:33:13 +08:00
    到底是什么岗位?
    就只有我一个人觉得这是一道普通编程题,要求实现的不是玩游戏策略算法而只是实现游戏规则,考察的是候选者的代码基础工程能力而不是算法能力吗?
    wzzb
        8
    wzzb  
       2021-10-15 17:38:06 +08:00
    nim 博弈,通常取胜条件是"没有物品可取的选手失败" normal nim,你这个取胜条件是"取走最后一个物品的选手失败" misere nim ;
    将问题一般化,给定 int 数组,表示 n 堆物品的数量,A/B 选手轮流操作,每次可从任意堆中取走任意数量的物品(最少 1 个,不可不取),取走最后一个物品的落败,判断是否先手必胜;
    判断条件是:
    - 1.每一堆的数量都是 1,异或和为 0
    - 2.至少一堆数量大于 1,异或和不为 0
    zxCoder
        9
    zxCoder  
       2021-10-15 20:47:56 +08:00
    @flyingghost 严格来说这是一道数学题,也确实是一道算法题,你说考察工程能力说明这道题你做错了...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4701 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 09:47 · PVG 17:47 · LAX 02:47 · JFK 05:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.