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 · 46 天前 · 1457 次点击
    这是一个创建于 46 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如图: 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   46 天前
    我不是程序员哈,这个用博弈论中逆向归纳即可,最后结论是,只要我先拿,我一定有必胜策略
    Xs0ul
        2
    Xs0ul   46 天前 via Android
    具体的实现没看,但是 hardcore 这些数值在函数内而不是作为参数传进来,可能不够“优雅”
    zxCoder
        3
    zxCoder   46 天前   ❤️ 1
    这是 nim 博弈吧

    虽然我理解不了什么叫做分成三行,每行还能自上而下 hhhhh
    cairnechen
        4
    cairnechen   46 天前
    不知道你们有没有看过一个小说叫天才基本法,里面有这个
    MoYi123
        5
    MoYi123   45 天前
    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   45 天前
    这不就是博弈吗? nyist oj 上 取石子
    flyingghost
        7
    flyingghost   45 天前
    到底是什么岗位?
    就只有我一个人觉得这是一道普通编程题,要求实现的不是玩游戏策略算法而只是实现游戏规则,考察的是候选者的代码基础工程能力而不是算法能力吗?
    wzzb
        8
    wzzb   45 天前
    nim 博弈,通常取胜条件是"没有物品可取的选手失败" normal nim,你这个取胜条件是"取走最后一个物品的选手失败" misere nim ;
    将问题一般化,给定 int 数组,表示 n 堆物品的数量,A/B 选手轮流操作,每次可从任意堆中取走任意数量的物品(最少 1 个,不可不取),取走最后一个物品的落败,判断是否先手必胜;
    判断条件是:
    - 1.每一堆的数量都是 1,异或和为 0
    - 2.至少一堆数量大于 1,异或和不为 0
    zxCoder
        9
    zxCoder   45 天前
    @flyingghost 严格来说这是一道数学题,也确实是一道算法题,你说考察工程能力说明这道题你做错了...
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2125 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 00:36 · PVG 08:36 · LAX 16:36 · JFK 19:36
    ♥ Do have faith in what you're doing.