文档章节

阿里笔试鱼丸肉丸问题

o
 osc_lc29nall
发布于 07/01 16:01
字数 2114
阅读 37
收藏 0

精选30+云产品,助力企业轻松上云!>>>

阿里2019年实习春招算法机器学习笔试编程题及解答

题目描述

班上同学聚餐吃火锅,一锅煮了的M(1<=M<=50)个鱼丸和N(1<=N<=50)个肉丸,现欲将M个鱼丸和N个肉丸分到K(1<=K<=50)个碗中,允许有空碗,鱼丸和肉丸不允许混在同一个碗里,问共有多少种装法。假设碗足够大,能装50个鱼丸或者50个肉丸,碗之间也没有区别,因此当N=M=1,K=3时,只有一种解法,因为(1,1,0)(1,0,1)(0,1,1)被看做是同一种装法。

输入:
输入数据包含三行,每行一个整数,分别是M、N、K(1<=M,N,K<=50)

输出:
一个整数,单独一行,输出共有多少种装法,要求输出结果对10000取模,例如,计算出共有123456中装法,则输出3456

解题思路

实际上这题是一个复杂版本的N球M盒问题。解题思路很容易想到,那就是首先将鱼丸放进盒子里,然后再考虑肉丸的放置。

符号定义

  1. d p F i s h [ i ] [ j ] dpFish[i][j] dpFish[i][j]表示 i i i个鱼丸放入 j j j个碗的放法总数,注意这里允许有空碗;
  2. d p M e a t [ i ] [ j ] dpMeat[i][j] dpMeat[i][j]类似 d p F i s h [ i ] [ j ] dpFish[i][j] dpFish[i][j]
  3. r e s res res 表示题目要求的输出。

结果的计算

r e s res res的计算很直观,那就是要先将鱼丸放好,再放肉丸,那么我们只需要遍历鱼丸所需的盒子数就可以了,代码如下:

for (int i = 1; i < k && n - i >= 0; i++)
      res += (dpFish[n - i][i] * dpMeat[m][k - i]);

注意到这里并不是 d p F i s h [ n ] [ i ] dpFish[n][i] dpFish[n][i],是因为 d p F i s h [ n ] [ i ] dpFish[n][i] dpFish[n][i]允许有空碗,会造成重复的case,所以这里用了一个小技巧,如果我先将 i i i个碗里各放一个鱼丸,然后就不会有空碗了,所以实际上 d p F i s h [ n − i ] [ i ] dpFish[n-i][i] dpFish[ni][i]这里想要表达的意思是 i i i个鱼丸放入 j j j个碗的放法总数,不允许有空碗。

d p F i s h [ i ] [ j ] dpFish[i][j] dpFish[i][j]的求法

实际上这就是一个N球M盒问题,相当于要将N个相同的球放入M个相同的盒子中,允许有空盒子,问有多少种放法。显然这是要用动态规划解决的,那么重要的就是如何推出递推公式。

这里我们只允许两个动作,什么都不干和往每个盒子里都放一个球。那么状态转移可以有如下形式:

  1. 如果 i > = j i >= j i>=j, 即球的数量大于等于盒子。那么 d p F i s h [ i ] [ j ] dpFish[i][j] dpFish[i][j]可以从两个状态转移得到,即什么都不干从 d p F i s h [ i ] [ j − 1 ] dpFish[i][j-1] dpFish[i][j1]中得到,或者每个盒子里放一个球从 d p F i s h [ i − j ] [ j ] dpFish[i - j][j] dpFish[ij][j]中得到,即: d p F i s h [ i ] [ j ] = d p [ i ] [ j − 1 ] + d p [ i − j ] [ j ] , i f i > = j . dpFish[i][j] = dp[i][j-1] + dp[i-j][j], if i >= j. dpFish[i][j]=dp[i][j1]+dp[ij][j],ifi>=j.
  2. 如果 i < j i < j i<j, 即球的数量小于盒子,那么就没办法从第二个动作转移得到,即:
    d p F i s h [ i ] [ j ] = d p [ i ] [ j − 1 ] i f i < j . dpFish[i][j] = dp[i][j-1] if i < j. dpFish[i][j]=dp[i][j1]ifi<j.

边界条件也很好设置:
3. d p F i s h [ 0 ] [ j ] = 1 , j < M dpFish[0][j] = 1, j < M dpFish[0][j]=1,j<M,没有球肯定只有不放一种方法。
4. d p F i s h [ i ] [ 1 ] = 1 , i < N dpFish[i][1] = 1, i < N dpFish[i][1]=1,i<N,只有1个盒子肯定只有不放一种方法。
5. d p F i s h [ 1 ] [ i ] = 1 , i < N dpFish[1][i] = 1, i < N dpFish[1][i]=1,i<N, 只有1个球放哪都一样。


代码

#include <iostream>
#include <vector>

int main()
{

    int n, m, k;
    cin>> n >> m >> k;

    vector< vector<int> >dpFish(n + 1,vector<int> (k + 1, 1)); //dp[i][j] 表示第i个fish有k个碗

    for (int i = 2; i < n + 1; i++) //第 2 个物品
        for (int j = 2; j < k + 1; j++) // 第 j
            {
                if ( j  >  i)
                    dpFish[i][j] = dpFish[i][j-1]; // 什么都不干
                else
                    dpFish[i][j] = dpFish[i][j-1] + dpFish[i-j][j]; // 什么都不干或者当前每个盒子都加1
            }

    vector< vector<int> >dpMeat(m + 1,vector<int> (k + 1, 1));

     for (int i = 2; i < m + 1; i++) //第 2 个物品
        for (int j = 2; j < k + 1; j++) // 第 j
            {
                if ( j  > i)
                    dpMeat[i][j] = dpMeat[i][j-1]; // 什么都不干
                else
                    dpMeat[i][j] = dpMeat[i][j-1] + dpMeat[i-j][j]; // 什么都不干或者当前每个盒子都加1
            }


    int res = 0;s

   for (int i = 1; i < k && n - i >= 0; i++)
      res += (dpFish[n - i][i] * dpMeat[m][k - i]);

    cout << res;

    return 0;

}

题目描述

小明,小华是校内公认的数据算法大牛。两人组队先后参加了阿里云天池大赛多项奖金赛事,多次获奖, 小明是其中的队长。最近的一次工业数据智能竞赛中,两人又斩获季军,获得奖金1万元。
作为算法大牛,两人竞赛奖金分配也有独特方式,由两人共同编写的一个程序来决定奖金的归属。每次获奖后,这个程序首先会随机产生若干0-1之间的实数{p_1,p_2,…,p_n}。然后从小明开始,第一轮以p_1的概率将奖金全部分配给小明,第二轮以p_2的概率将奖金全部分配给小华,这样交替地小明、小华以p_i的概率获得奖金的全部,一旦奖金被分配, 则程序终止,如果n轮之后奖金依然没发出,则从从p_1开始继续重复(这里需要注意,如果n是奇数,则第二次从p_1开始的时候,这一轮是以p_1的概率分配给小华) ;自到100轮,如果奖金还未被分配,程序终止,两人约定通过支付宝将奖金捐出去。

输入:

输人数据包念N+1行,

第一行包含一个整数N
接下来N行,每行一个0-1之间的实数, 从p_1到p_N

输出:
单独一行,输出一个小教,表示小明最终获得奖金的概率,结果四舍五入, 小数点后严格保留4位(这里需要注意,如果结果为0.5,则输出0.5000)

解题思路

这道题是一道概率题,实际上只需要模拟一下就可以了。首先计算出一轮中先手获得奖金的概率 p r o b F i r s t probFirst probFirst,后手获得奖金的概率 p r o b S e c o n d probSecond probSecond。然后每一轮获得奖金的条件就是上一轮都没有获得奖金的概率。

符号设置

  1. p r o b F i r s t probFirst probFirst,一轮中先手获得奖金的概率。
  2. p r o b S e c o n d probSecond probSecond,后手获得奖金的概率。
  3. c u r P r o b curProb curProb, 当前轮开始的概率。
  4. p r o b A probA probA, 需要计算的小明获得奖金的概率。

结果求解

小明获得奖金的概率显然只需要将其每一轮获取奖金的概率累加起来,需要注意的地方有两个:

  1. 每一轮如果 N N N是奇数的话,小明是先手还是后手是每轮需要转换的。
  2. 每一轮小明得奖金的概率还需要乘以当前轮能够开始的概率。

代码

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    bool countProb(float & probFirst, float & probSecond)
    {

        //cin >> n;
        vector<float> nums{0.25,0.25,0.25,0.25, 0.14,0.18};
        int n = nums.size();
//        for (auto & i : nums)
//            cin >> i;

        float  probCur = 1.0;

        for (int i = 0; i < n; i++)
        {
            if ((i & 1) == 0)
                probFirst += probCur*nums[i];
            else
                probSecond += probCur*nums[i];

            probCur *= (1 - nums[i]);
        }
        cout << probFirst << endl << probSecond << endl;

        return !(n & 1);
    }

    float countA()
    {
        float  probFirst = 0, probSecond = 0, probA = 0, probB = 0, curProb = 1.0;

        bool isEven = countProb(probFirst,probSecond);


        int n = 100;

        while(n--)
        {
            probA += probFirst * curProb;
            curProb *= (1 - probFirst - probSecond);
            if (!isEven)
                swap(probFirst,probSecond);
        }

        return probA;

    }

};

int main()
{
    Solution s;
    cout <<  s.countA();
}
     
o
粉丝 0
博文 52
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

DateTime2与SQL Server中的DateTime - DateTime2 vs DateTime in SQL Server

问题: Which one: 哪一个: datetime datetime2 is the recommended way to store date and time in SQL Server 2008+? 是在SQL Server 2008+中存储日期和时间的推荐方法吗? I'm aware of......

富含淀粉
28分钟前
6
0
Linux 文件打开过多 (Too many open files)

如图是程序运行了一段时间后抛出来的一个bug, 刚开始看这个bug的时候各种网上找答案, 无外乎教你怎么改ulimit(就是linux最大打开文件数), 当然不是说改这个没有用, 作为程序开发者来说, 如果...

onedotdot
29分钟前
20
0
ZStack实践汇|ZStack与行云管家对接实践ZStack与行云管家对接实践

一、ZStack与行云管家概述 大道至简·极速部署,ZStack致力于产品化私有云和混合云。 ZStack是一家坚持自主创新、专注产品化的云计算公司,以“降低企业上云门槛、让每一家企业都拥有自己的云...

ZStack社区版
35分钟前
7
0
switch linux mint 20 apt repository to tsinghua' mirrors

edit file /etc/apt/sources.list.d/cat official-package-repositories.list lwk@qwfys:/etc/apt/sources.list.d$ lltotal 12drwxr-xr-x 2 root root 4096 Jul 5 20:01 ./drwxr-xr-x 7 ......

qwfys
54分钟前
7
0
面试系列之C++的对象布局【建议收藏】

我们都知道C++多态是通过虚函数表来实现的,那具体是什么样的大家清楚吗?开篇依旧提出来几个问题: 普通类对象是什么布局? 带虚函数的类对象是什么布局? 单继承下不含有覆盖函数的类对象是...

伊牙牙嘿哈哈
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部