欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

游戏合成装备算法面试题

程序员文章站 2022-06-25 15:50:14
**更新时间:2020-09-14**最近很多游戏公司来招聘,下面给出面试到的算法题。我也不懂,为啥这么多游戏公司缺人。而且我也没做过游戏方面啊!!!!面试内容:下图是一个装备系统的合成图谱,箭头指向的是合成之后的装备,每合成一个装备需要消耗一些金币(标注在矩形框里面),箭头上的数字表示合成所需的材料数量。比如,要合成n个装备A,需要消耗3n个装备B、1n个装备C、4n个装备D,而且还需要消耗26n金币(装备B和装备D的合成与此类似)。为了简单起见,下面题目的装备图谱都是一棵多叉树,而且玩家...

**

更新时间:2020-09-14

**

最近很多游戏公司来招聘,下面给出面试到的算法题。
我也不懂,为啥这么多游戏公司缺人。
而且我也没做过游戏方面啊!!!!

面试内容:
下图是一个装备系统的合成图谱,箭头指向的是合成之后的装备,每合成一个装备需要消耗一些金币(标注在矩形框里面),箭头上的数字表示合成所需的材料数量。比如,要合成n个装备A,需要消耗3n个装备B、1n个装备C、4n个装备D,而且还需要消耗26n金币(装备B和装备D的合成与此类似)。
为了简单起见,下面题目的装备图谱都是一棵多叉树,而且玩家最初只拥有指定数量的叶子节点的装备,也就是图中的装备C、装备E、装备F和装备G。
注意,下面的图谱只是一个例子,作答的时候不要局限于这个图谱。

游戏合成装备算法面试题

已知玩家拥有一些初级装备(叶子节点的装备)和n个金币,并且所有装备的合成都需要消耗金币,玩家需要合成尽可能多的某个装备(记为装备X),请用C#语言(后端用c++语言)计算出玩家最多可以合成出多少个装备X。

请在收到题目的一至两天内完成,提交的时候只需要提交源代码以及算法思路。为了规范输入输出,下面给出代码的基本结构,作答的时候不要修改Run函数的函数原型。

public class Exam
{
public class MaterialData
{
public ItemData item; //合成所需的物品
public int count; //合成所需的该物品的数量
}

public class ItemData
{
public int id; //物品 ID
public int count;//当前拥有的物品数量
public int costGold;//合成该物品所需的金币
public List materialList; //合成该物品所需的材料
}

///
/// 计算用 totalGold 金币最多可以合成的 item 装备的数量
///
/// 要合成的装备
/// 拥有的金币
/// 可合成的 item 装备的最大数量
public int Run(ItemData item, int totalGold)
{
return 0;
}
}

其实就是大部分游戏材料合成的算法操作。
玩过网游或者王者的人应该都知道。

代码:测试数据和注释写的挺清楚的。(我也是参考别人的)
可能在暗示我不是做游戏这方面的料吧。
说到这,C#写法和java简直就是一模一样。有点不习惯。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


//目标:
//输入:指定合成的装备
//输出:可合成数量
//条件:金币够,材料够
public class Exam
{
    //物品所需材料
    public class MaterialData
    {
        public ItemData item;   //合成所需的物品
        public int count;       //合成所需的该物品的数量
    }
    //该物品
    public class ItemData
    {
        public int id;  //物品 ID
        public int count;//当前拥有的物品数量
        public int costGold;//合成该物品所需的金币
        public List<MaterialData> materialList; //合成该物品所需的材料
    }

    //满足条件--这句没用上,原本以为是要问能买多少个A
    public int equivalence(int numE, int numF, int numC, int numG,int totalGold)
    {
        int numA=0, numB=0, numD=0;
        int money = totalGold;
        int allMoney = totalGold;

        //满足B--至少能买一个
        if (numE > 0 && numF > 0 && money >= 53)
        {
            //计算材料够合成几个
            int[] array = { numE, numF };
            Array.Sort(array);
            int min = array[array.Length - 1];

            int moneyCanBuyNum = money / 53;
            if(moneyCanBuyNum >= min)//如果钱多,材料够了,买足材料的物品
            {
                numB = min;
                money = money - 53 * min;
            }
            else//钱不够,材料够了
            {
                numB = moneyCanBuyNum;
                money = money - 53 * moneyCanBuyNum;
            }
        }

        //满足D--至少能买一个
        if (numG > 0  && money >= 58)
        {
            int moneyCanBuyNum = money / 58;
            if (moneyCanBuyNum >= numG)//钱多,材料够了,买足材料的物品
            {
                numD = numG;
                money = money - 58 * numG;
            }
            else//钱不够,材料够了
            {
                numD = moneyCanBuyNum;
                money = money - 58 * moneyCanBuyNum;
            }
        }
        //满足A
        if (numB > 0 && numD > 0 && numC > 0 && money >= 26)
        {
            int[] array = { numB, numC, numD };
            Array.Sort(array);
            int min = array[array.Length - 1];

            int moneyCanBuyNum = money / 26;
            if (moneyCanBuyNum >= min)//如果钱多,材料够了,买足材料的物品
            {
                numA = min;
                money = money - 26 * min;
            }
            else//钱不够,材料够了
            {
                numA = moneyCanBuyNum;
                money = money - 26 * moneyCanBuyNum;
            }
        }
        Console.WriteLine("{0},{1},{2},{3}", numA,numB, numD,money);

        return 0;
    }

    //递归获取该物体最多可合成数量
    private int getSynthesisCount(ItemData item)
    {
        //获取物品所需材料品种数量--G and more
        int speciesNum = item.materialList.Count;
        Console.WriteLine("species num:" + speciesNum);

        //如果材料种类为0,代表为节点,返回当前材料数量
        if (speciesNum == 0)
        {
            return item.count;
        }
        int materialCount, canNum;
        int minCount = int.MaxValue;
        Console.WriteLine("minCount num:" + minCount);

        for (int i = 0; i < speciesNum; i++)
        {
            //该材料是否还有下一级材料
            materialCount = getSynthesisCount(item.materialList[i].item);
            Console.WriteLine("G num:" + materialCount);

            //合成材料数 / 所需材料数量 = 物品
            canNum = materialCount / item.materialList[i].count;
            Console.WriteLine("materialCount num:" + canNum);

            minCount = Math.Min(minCount, canNum);
        }
        return minCount;
    }

    //递归获取该物体合成价格
    private int getSynthesisCost(ItemData item)
    {
        //获取物品所需材料品种数量--G and more
        int speciesNum = item.materialList.Count;
        Console.WriteLine("species num:" + speciesNum);

        if (speciesNum == 0)
        {
            return 0;
        }
        int minCount = 0;
        for (int i = 0; i < speciesNum; i++)
        {
            //
            minCount += getSynthesisCost(item.materialList[i].item) * item.materialList[i].count;
        }
        minCount += item.costGold;
        //返回总共的合成花费
        return minCount;
    }

    private int getMaxNum(int canSynthesisNum,int canMoneyNum ,int money)
    {
        int num = 0;
        int moneyCanBuyNum = money / canMoneyNum;
        if (moneyCanBuyNum >= canSynthesisNum)//如果钱多,材料够了,买足材料的物品
        {
            num = canSynthesisNum;
            money = money - canMoneyNum * canSynthesisNum;
        }
        else//钱不够,材料够了
        {
            num = moneyCanBuyNum;
            money = money - canMoneyNum * moneyCanBuyNum;
        }
        Console.WriteLine("money:" + money);

        return num;
    }


    /// <summary>
    /// 计算用 totalGold 金币最多可以合成的 item 装备的数量
    /// </summary>
    /// <param name="item">要合成的装备</param>
    /// <param name="totalGold">拥有的金币</param>
    /// <returns>可合成的 item 装备的最大数量</returns>
    public int Run(ItemData item, int totalGold)
    {
        int canSynthesisNum = getSynthesisCount(item);
        Console.WriteLine("Synthesis can buy Num:" + canSynthesisNum);

        int canMoneyNum = getSynthesisCost(item);
        Console.WriteLine("money Synthesis price:" + canMoneyNum);

        Console.WriteLine("Max Num:" + getMaxNum(canSynthesisNum, canMoneyNum, totalGold)); 

        return 0;
    }
}


namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            //例子为合成D
            Exam.ItemData TestData()
            {
                //D
                Exam.ItemData itemData = new Exam.ItemData();
                itemData.id = 10004;
                itemData.count = 0;
                itemData.costGold = 58;
                itemData.materialList = new List<Exam.MaterialData>();
                itemData.materialList.Add(BoxG());
                return itemData;
            }
            Exam.MaterialData BoxG()
            {
                //所需材料2个G
                Exam.MaterialData material = new Exam.MaterialData();
                material.count = 2;

                //G的拥有量
                Exam.ItemData itemG = new Exam.ItemData();
                itemG.count = 6;
                itemG.id = 10007;
                itemG.costGold = 0;
                material.item = itemG;
                itemG.materialList = new List<Exam.MaterialData>();
                return material;
            }


            Exam ee = new Exam();
            Exam.ItemData item = TestData();
            
            ee.Run(item, 100);




        }
    }
}

本文地址:https://blog.csdn.net/weixin_44353958/article/details/108576921

相关标签: 面试题