Algorithm Dynamic planning

A question of interview about egg casting from microsoft

use algorithm of dynamic planning can easily deal with it

Posted by Maizi on 2016-09-15 with time read

来自微软的扔鸡蛋面试题

问题描述如下:

有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。(假设每次摔落时，如果没有摔碎，则不会给鸡蛋带来损耗)
        据说下图的力学结构可以保证鸡蛋从20楼扔下不碎,可见知识就是力量 ☺

算法描述:


算法分析:

在保证能确切知道哪一层是分割点的前提下,该问题很显然采用动态规划会有比较好的,若采用步进为2时,算法复杂度为O(n)=n,此时最坏的情况是分割点在99层,要扔51次.

①从第二层开始,两层的两层的向上推进.

②若第一个鸡蛋碎了,则退回下一层继续扔另一个蛋,并根据第二个蛋的完整状况直接给出结果.

若能想到这个思路,恭喜您!您的算法入门了.

贴上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ERROR_PARAMS -1
#define ILLEGAL_PARAMS -2
int MAX_FLOOR = 100;
int CUT_POINT_FLOOR;
/**
 * 裁决该层扔鸡蛋是否破了
 * @param floor 准备扔的楼层数
 * @return 1代表没破,0代表破了
 */
int judge(int const floor) {
    if (floor < CUT_POINT_FLOOR) {
        printf("attempt to cast the egg in the floor %d with the result of egg complete\n", floor);
        return 1;
    } else {
        printf("attempt to cast the egg in the floor %d with the result of egg break\n", floor);
        return 0;
    }
}
/**
 * 扔鸡蛋
 * @return 分割点的楼层数
 */
int castEgg() {
    int i;
    for (i = 1; i < MAX_FLOOR; ++i) {
        int floor = i << 1;
        if (judge(floor)) {//第一个蛋没破
            continue;
        } else {//第一个蛋破了
            if (judge(floor - 1)) {//第二个蛋没破
                return floor;
            } else {//第二个蛋破了
                return floor - 1;
            }
        }
    }
}
/**
 * 处理程序的输入
 * @param argc 参数的个数
 * @param arg 用户的输入的楼层
 * @return 分割楼层
 */
int handleArgs(int const argc, char const * const arg) {
    if (argc != 2) {
        perror("please input the floor of cut point");
        return ERROR_PARAMS;
    }
    size_t len = strlen(arg);
    int i;
    for (int i = 0; i < len; ++i) {
        char tmp = *(arg + i);
        if (tmp < 47 || tmp > 58) {
            printf("please check your args, your args seems not like a number.");
            return ILLEGAL_PARAMS;
        }
    }
    return atoi(arg);
}
int main(int argc, char **argv) {
    int ret = handleArgs(argc, *(argv + 1));
    if (ret < 1)
        return ILLEGAL_PARAMS;
    else
        CUT_POINT_FLOOR = ret;
    printf("the cut point floor is : %d\n", castEgg());
    return 0;
}

附上测试结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/home/maizi/.CLion2016.2/system/cmake/generated/Demo-71a0270b/71a0270b/Debug/Demo 52
attempt to cast the egg in the floor 2 with the result of egg complete
attempt to cast the egg in the floor 4 with the result of egg complete
attempt to cast the egg in the floor 6 with the result of egg complete
attempt to cast the egg in the floor 8 with the result of egg complete
attempt to cast the egg in the floor 10 with the result of egg complete
attempt to cast the egg in the floor 12 with the result of egg complete
attempt to cast the egg in the floor 14 with the result of egg complete
attempt to cast the egg in the floor 16 with the result of egg complete
attempt to cast the egg in the floor 18 with the result of egg complete
attempt to cast the egg in the floor 20 with the result of egg complete
attempt to cast the egg in the floor 22 with the result of egg complete
attempt to cast the egg in the floor 24 with the result of egg complete
attempt to cast the egg in the floor 26 with the result of egg complete
attempt to cast the egg in the floor 28 with the result of egg complete
attempt to cast the egg in the floor 30 with the result of egg complete
attempt to cast the egg in the floor 32 with the result of egg complete
attempt to cast the egg in the floor 34 with the result of egg complete
attempt to cast the egg in the floor 36 with the result of egg complete
attempt to cast the egg in the floor 38 with the result of egg complete
attempt to cast the egg in the floor 40 with the result of egg complete
attempt to cast the egg in the floor 42 with the result of egg complete
attempt to cast the egg in the floor 44 with the result of egg complete
attempt to cast the egg in the floor 46 with the result of egg complete
attempt to cast the egg in the floor 48 with the result of egg complete
attempt to cast the egg in the floor 50 with the result of egg complete
attempt to cast the egg in the floor 52 with the result of egg break
attempt to cast the egg in the floor 51 with the result of egg complete
the cut point floor is : 52

算法进阶:


算法分析:

若步进n更大呢? n∈[1,100)&n∈N

①若取n=x(x∈[1,100)&x∈N)时,那么最坏的情况是先跳了100/x次,然后从[100/x]x-x层依次向上尝试x-1次.

②分析完毕,开始对问题进行数学建模,该问题现在就转化成一个求最小值的数学问题:
x∈[1,100)&x∈N,求f(x)=100/x + (x - 1)的最小值.

③开始解题:
    f(x)=100/x + (x - 1);
    f(x)=(10/x) X 10 + (x/10) X 10 -1;
    f(y)=(1/y + y) X 10 -1;
∵ y∈R+ f(y)min=1/y+y => y = 1/y;
∴ x∈[1,100)&x∈N f(x)min=(10/x) X 10 + (x/10) X 10 -1;
        =>10/x = x/10 => x=10;

④设计算法:从第10层开始,以步进为10向上推进,若在第10n(n∈[1,10]&n∈R+)层第一个蛋碎了,就从第10n-9层依次往上一层层的用第二个蛋尝试,直至找到分割点楼层.

若您的思路一开始就是此方式,恭喜您!您的算法水平还不错哦 ☺ *

贴上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define ERROR_PARAMS -1
#define ILLEGAL_PARAMS -2
int MAX_FLOOR = 100;
int CUT_POINT_FLOOR;
/**
 * 裁决该层仍鸡蛋是否破了
 * @param floor 准备仍的楼层数
 * @return 1代表没破,0代表破了
 */
int judge(int const floor) {
    if (floor < CUT_POINT_FLOOR) {
        printf("attempt to cast the egg in the floor %d with the result of egg complete\n", floor);
        return 1;
    } else {
        printf("attempt to cast the egg in the floor %d with the result of egg break\n", floor);
        return 0;
    }
}
/**
 * 扔鸡蛋
 * @param delta 步进
 * @return 分割点的楼层数
 */
int castEgg(int const delta) {
    int i, j;
    for (i = delta; i <= MAX_FLOOR; i += delta) {
        if (judge(i))//第一个蛋没破
            continue;
        else {//第一个蛋破了
            for (j = i - 9; j < i; ++j) {
                if (!judge(j))//第二个蛋破了
                    return j;
            }
        }
    }
}
/**
 * 处理程序的输入
 * @param argc 参数的个数
 * @param arg 用户的输入的楼层
 * @return 分割楼层
 */
int handleArgs(int argc, char *arg) {
    if (argc != 2) {
        perror("please input the floor of cut point");
        return ERROR_PARAMS;
    }
    size_t len = strlen(arg);
    int i;
    for (int i = 0; i < len; ++i) {
        char tmp = *(arg + i);
        if (tmp < 47 || tmp > 58) {
            printf("please check your args, your args seems not like a number.");
            return ILLEGAL_PARAMS;
        }
    }
    return atoi(arg);
}
/**
 * 计算步进
 * @param n 楼层的总数
 * @return 步进
 */
int calculate(int const n) {
    // n/x = x => x² = n =>x = √n
    return sqrt(n * 1.0);
}
int main(int argc, char **argv) {
    int ret = handleArgs(argc, *(argv + 1));
    if (ret < 1)
        return ILLEGAL_PARAMS;
    else
        CUT_POINT_FLOOR = ret;
    printf("the cut point floor is : %d\n", castEgg(calculate(MAX_FLOOR)));
    return 0;
}

附上测试结果:

1
2
3
4
5
6
7
8
9
10
/home/maizi/.CLion2016.2/system/cmake/generated/Demo-71a0270b/71a0270b/Debug/Demo 52
attempt to cast the egg in the floor 10 with the result of egg complete
attempt to cast the egg in the floor 20 with the result of egg complete
attempt to cast the egg in the floor 30 with the result of egg complete
attempt to cast the egg in the floor 40 with the result of egg complete
attempt to cast the egg in the floor 50 with the result of egg complete
attempt to cast the egg in the floor 60 with the result of egg break
attempt to cast the egg in the floor 51 with the result of egg complete
attempt to cast the egg in the floor 52 with the result of egg break
the cut point floor is : 52


2016-09-15
— Maizi

FEATURED TAGS
Algorithm Dynamic planning
FRIENDS