呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

【2018秋招笔试】2018.9.7 阿里巴巴 测试工程师

前言

阿里的测试工程师提醒如下:

阿里的测试选择题出了不少数学题,概率论,组合数学,比较难,不愧是大厂。

编程题有两道,过了一道半。

第一题

思路:

小数据,dfs深搜穷举即可。

提交后AC。

ps:题目描述里不能使用循环什么鬼……

代码:

#include <iostream>
#include <stdio.h>
using namespace std;

int num;
int a[3];

void dfs(int cur)
{
    if(a[0]==0 && a[1]==0 && a[2]==0){
        num++;
    }
    int i;
    for(i=0;i<3;i++){
        if(cur == i)
            continue;
        if(a[i]>0){
            a[i]--;
            dfs(i);
            a[i]++;
        }
    }
}


int main()
{
    num = 0;
    scanf("%d,%d,%d",&a[0],&a[1],&a[2]);
    dfs(-1);
    printf("%d",num);
    return 0;
}

第二题

思路:

没想到太好的方法,暴力解决。

提交后没有全部通过测试样例,好像过了50%。

ps:时间匆忙,代码写的不好看。

代码:

#include <iostream>
#include <stdio.h>
using namespace std;

#define eps 1e-8

double a[1000010] = {0};
int len;
double n;   //目标金额

double Abs(double x)
{
    if(x<0){
        return -x;
    }
    else{
        return x;
    }
}

bool dfs(int curi,double curm)
{
    //curi,当前位置,curm,当前金额
    if(Abs(curm-n)<eps){
        return true;
    }
    int i;
    for(i=curi;i<len;i++){
        if(dfs(curi+1,curm+a[i]))
            return true;
    }
    return false;
}

bool isf()
{
    // 判断是否有资格获得红包
    int i;
    int cnt = 0;
    bool f1 = false,f2 = false;
    double Sum = 0;
    for(i=0;i<len;i++){
        Sum += a[i];
        if(a[i]>10){
            cnt++;
            if(cnt>=2){
                f1 = true;
            }
        }
    }
    // 如果第一个条件就不满足,那么直接返回false
    if(!f1)
        return false;
    // 判断是否符合第二个条件
    // 如果总金额直接就小于目标金额,那么直接false
    if(Sum<n)
        return false;
    f2 = dfs(0,0);
    return f2;


}

int main()
{
    int i;
    // 输入
    scanf("%lf",&a[0]);
    for(i=0;scanf("%lf",&a[i])!=EOF;i++){
        char c = getchar();
        if(c=='\n')
            break;
    }
    scanf("%lf",&n);
    len = i+1;

    bool f = isf();
    if(f){
        printf("true");
    }
    else{
        printf("false");
    }

    return 0;
}

原创声明

转载请注明:呓语 » 【2018秋招笔试】2018.9.7 阿里巴巴 测试工程师