首页 / 技术类 / 工作体验 / 2008金山暑期实习在线考试(2008-06-14)小记

2008金山暑期实习在线考试(2008-06-14)小记

2008-06-22 17:13:00

提前十几分钟登录的系统,8:54 左右就可以看到题了。题目是这样的:

1、编程计算从 1 到 2008080808 之间的整数有多少个含有数字7。

2、结构RECT可以表示一个平面上的矩形区域: struct RECT { int left, right, top, bottom; }; 编程计算两个矩形区域A和B构成的区域总面积。

3、将给定的字符串以词为单位倒序,同时给定一个子串,若字符串中有部分内容与子串相同则该部分不倒序。 例:给定字符串“The quick brown fox jumps over the lazy dog”和子串“brown fox”, 倒序结果是“dog lazy the over jumps brown fox quick The”

看到先把三题都看了下,第一题不是最简单的,但是还是喜欢从第一题做起。虽然是网上考试,还是有点点紧张,思路有点混乱。首先验证了下 2008080808 这个数是不是足够大,大到原有数据类型存不下。所幸,double 类型可以从容存下,那就说明考的不是大数处理,数字这么大仅仅是为了让穷举的代价变得高了而已——显然不能用穷举法。接下去的半个多小时在想算法,当然拿小的数字乱想先,10 以内怎么样,100 以内怎么样,不过也不知道真的在干什么,思路很杂,什么也有用没想到。过了这么久,也越来越紧张了。忽然闪过一个想法,100 到 150 以内的满足题意的数的个数跟 0 到 50 之间的不是一样吗?那么,2008080808 就可以拆成 2000000000、8000000、80000、800、8 这几个部分了;再,200 以内的这样的数的个数是 100 以内的这样的数的个数的 2 倍。所以,最终要解决的是,对于 X0000 (n 个 0)这样的数,结果是多少。X0000 (n 个 0)以内,也就是 n 位数的范围了。对于一个 n 位数,有几个含数字 7 是好算的,它的个数等于

$$ \underbrace{C^1_n10^{n-1}}{至少 1 位是 7 的个数}-\underbrace{C^2_n10^{n-2}}{至少 2 位是 7 的个数}+\underbrace{C^3_n10^{n-3}}{至少 3 位是 7 的个数}-...+\underbrace{(-1)^{n-1}C^n_n10^{n-n}}{至少 n 位是 7 的个数} $$

当时是按这个算的。其实这个式子可以进一步化简,结果是 $$ 10^n-9^n $$,这点我土了,程序里面在算那个复杂的式子。也许当时没那么悠闲让我算来算起。换种思路,结果是 $$ \underbrace{C^1_n9^{n-1}}{有且仅有 1 位是 7}+\underbrace{C^2_n9^{n-2}}{有且仅有 2 位是 7}+\underbrace{C^3_n9^{n-3}}{有且仅有 3 位是 7}+...+\underbrace{C^n_n9^{n-n}}{有且仅有 n 位是 7} $$

再算一步当然也是 $$ 10^n-9^n $$ 咯。

做第二题的时候已经过了差不多 80 分钟了。不过这题还算比较简单。但是那个 struct 我很想改成 class,可是又不知道允不允许。算了,还是纯 C 来吧。为了使用方便,我还是在这个 struct 里加了几个构造函数。这题主要考点是算重叠的情形下覆盖面积是多少。那么我把重叠部分算出来不就好了。起先做第一题顺带考虑第二题的时候我想到重叠要分好几种情况,左右还是上下,还是左上右下,等等。做这题的时候意识到重叠部分不还是一个矩形么?它的 left 是原来两个的 left 的较大者,它的 right 是原来两个的 right 的较小者,它的 top 是原来两个的 top 的较大者,它的 bottom 是原来两个的 bottom 的较小者,这样面积就好算了。于是覆盖面积就是原来两个矩形的面积和减去重叠面积。

第三题我原来打算用 STL 里的 stringstack 的,试了下,因为我对 STL 不是很熟悉,所以非常不顺手。我还是自己写吧。这题想的时间也不是很多,倒序输出可以利用递归解决,剩下的就是字符串比较问题了。做完后还有大概一小时。

还有时间,去网上查查看,第一题有没有什么更好的算法。新算法没找到,在百度知道看到一个求 500 以内不含数字 4 的问题,后面有人给出答案。我想验证一下,可是这题是算 7 的。其实算法已经是通用的了,没必要拘泥于 7、拘泥于 2008080808 的。于是我把它改成一个可以求 n 以内含数字 d (d 不等于 0,等于 0 的情况不能这样算,没时间考虑了) 的数字的个数的。再去验证 500 里含 4 的个数,176 个,于是不含的 324 个,跟那帖的回答中的多数是符合的,于是我就放心了。

这时候已经 11:50 多了,赶紧交,呵呵。

后来吃饭的时候想到了两点疏忽之处:

1、矩形的边长,我直接 right-left,bottom-top 了,没有去 +1,测试数据也是按照不 +1 凑的。虽然题目没有明确说 left、right、top、buttom 的具体含义,可是我想一般还是要 +1 的吧。

2、另一个是第三题的输出字符串中忘了手动赋上结束符 '\0' 了。VC 中会对数组自动赋 0,但是 C/C++ 标准里没有规定要这样。也正因为VC 帮我做了,所以调试的时候我一直没发现这个问题。

更囧的是,那天晚上我想到了一个更严重的问题,第二题中,我只算了有重叠的情形,没重叠的情形没有区分,减去了那个“负重叠矩形”的面积……

我本来以为我没希望了的。惊喜的是前天收到实习邀请邮件了,哈哈。

三个题的代码(当时交的时候的版本,原样保留,错误都保留着):

  1#include <iostream>
  2#include <math.h>
  3
  4using namespace std;
  5
  6int fact_table[10];
  7
  8// 计算 9! 以内阶乘表
  9void init_fact_table()
 10{
 11    fact_table[0] = 1;
 12    for(int i=1; i<10; i++)
 13    {
 14        fact_table[i] = fact_table[i-1] * i;
 15    }
 16}
 17
 18// 查表法计算阶乘, n<=9, 由于是自己使用, 不对 n 作检查
 19int fact(int n)
 20{
 21    return fact_table[n];
 22}
 23
 24// 计算组合数 C(n, m), 即从 n 个元素中取出 m 个元素的取法数(m<=n)
 25// 同样不检查 n 和 m 了
 26int combi(int n, int m)
 27{
 28    return fact(n)/fact(m)/fact(n-m);
 29}
 30
 31// 计算形如 10000 的数内有多少个含有digit
 32// 参数 zeros 表示后面有几个 0
 33// 公式 C(zeros, 1)*10^(zero-1) -C(zeros, 2)*10^(zero-2) +C(zeros, 3)*10^(zero-3) - ……
 34double _count(int digit, int zeros)
 35{
 36    double res = 0;
 37    int sign = 1;
 38
 39    for(int i=1; i<=zeros; i++)
 40    {
 41        res += sign*combi(zeros, i)*pow(10.0, zeros-i);
 42        sign = -sign;
 43    }
 44
 45    return res;
 46}
 47
 48// 计算形如 X0000 的数内中有多少个含有 digit
 49// 参数 zeros 表示后面有多少个 0
 50// 参数 first_num 表示首位数字
 51double _count(int digit, int zeros, int first_num)
 52{
 53    double res = 0;
 54
 55    if(first_num<digit)  // 如果最高位小于 digit,就是 count(zeros) 的结果乘以它既可
 56    {
 57        return first_num*_count(digit, zeros);
 58    }
 59    else if(first_num==digit)  // 最高位正好是 7(digit),加上 700000… 这个数
 60    {
 61        return (first_num)*_count(digit, zeros)+1;
 62    }
 63    else  // 最高位大于 digit,则 digit 开头的全部是,这部分有 pow(10.0, zeros) 个
 64    {
 65        return (first_num-1)*_count(digit, zeros)+pow(10.0, zeros);
 66    }
 67}
 68
 69// 计算 num 内的数有多少个含有 digit(digit != 0)
 70double count(double num, int digit)
 71{
 72    // 算法解释
 73    // 假设 num 是 2008080808
 74    // 拆成 0 到 2000000000
 75    // 2000000000 到 2008000000
 76    // 2008000000 到 2008080000
 77    // 2008080000 到 2008080800
 78    // 2008080800 到 2008080808 这几个部分
 79    // 相当于分别计算 0 到 8000000、0 到 80000、0 到 800、0 到 8
 80    // 每一个部分按照上面的算
 81    // 如果某一次碰到那一位是数字 digit 作特殊处理(当然,仅仅计算 2008080808 内含 7 的话用不到)
 82
 83    double next = num, res = 0;
 84
 85    while(next>=1)
 86    {
 87        double first_num = next; // 最高位
 88        int bits = 0;  // 最高位以外的位数
 89
 90        while(first_num>=10)
 91        {
 92            bits ++;
 93            first_num /= 10;
 94        }
 95
 96        res += _count(digit, bits, (int)first_num);
 97        next = fmod(next, pow(10.0, bits));
 98
 99        if(first_num == digit)
100        {
101            res += next;  // 剩余未统计的 next 个数全部含有 digit 了
102            break;  // 计算结束
103        }
104    }
105
106    return res;
107}
108
109int main()
110{
111 
112    init_fact_table();
113    //printf("%.0lf/n", count(100, 7));  // 结果 19
114    //printf("%.0lf/n", count(160, 7));  // 结果 25
115    //printf("%.0lf/n", count(167, 7));  // 结果 26
116    //printf("%.0lf/n", count(168, 7));  // 结果 26
117    //printf("%.0lf/n", count(170, 7));  // 结果 27
118    //printf("%.0lf/n", count(180, 7));  // 结果 36
119    //printf("%.0lf/n", count(1000, 7));  // 结果 271
120    printf("%.0lf/n", count(2008080808, 7));  // 结果 1229473242
121    //printf("%.0lf/n", count(500, 4));  // 176
122
123    return 0;
124}
 1#include <iostream>
 2#include <math.h>
 3using namespace std;
 4
 5struct RECT
 6{
 7    int left, right, top, bottom;
 8    RECT() : left(0), right(0), top(0), bottom(0) {}
 9    RECT(int left, int right, int top, int bottom) : left(left), right(right), top(top), bottom(bottom)
10    {
11        // 确保 left <= right, top<=bottom
12        // 这样计算重叠面积的时候简便些
13        // 当然由于 struct 的数据成员是 public 的,数据可以在外部随意改
14        // 这个 struct 又是自己用的
15        // 这个检查似乎没什么必要
16        // 只是意思一下,我要在这里保证 left、right 和 top、bottom 的大小关系
17        // 在下面 overlay() 里就不作检查了
18        if(this->left > this->right)
19        {
20            swap(this->left, this->right);
21        }
22        if(this->top > this->bottom)
23        {
24            swap(this->top, this->bottom);
25        }
26    }
27 
28    RECT(RECT &that)
29    {
30        this->left = that.left;
31        this->right = that.right;
32        this->top = that.top;
33        this->bottom = that.bottom;
34    }
35};
36
37int max(int a, int b)
38{
39    return a>=b?a:b;
40}
41
42int min(int a, int b)
43{
44    return a<=b?a:b;
45}
46
47// 返回两个矩形的重叠部分
48RECT overlay(RECT a, RECT b)
49{
50    RECT res;
51
52    res.left = max(a.left, b.left);
53    res.right = min(a.right, b.right);
54    res.top = max(a.top, b.top);
55    res.bottom = min(a.bottom, b.bottom);
56
57    return res;
58}
59
60// 计算一个矩形的面积
61int area(RECT r)
62{
63    return (r.right-r.left)*(r.bottom-r.top);
64}
65
66// 计算两个矩形的面积(重叠的面积只记一次)
67int area(RECT a, RECT b)
68{
69    return area(a) + area(b) -area(overlay(a, b));
70}
71
72int main()
73{
74    RECT a(1, 11, 2, 62), b(8, 28, 0, 40);  // a 600, b 800, 重叠 3*38=114
75    printf("%d/n", area(a, b));  // 结果 1286
76
77    return 0;
78}
 1#include <iostream>
 2#include <string.h>
 3using namespace std;
 4
 5char instr[80], substr[80], outstr[80];
 6int out_pos, substrlen;
 7
 8// 比较 instr 的 start 处开始是否与 substr 相同
 9bool compare(int start)
10{
11    for(int i=0; i<substrlen; i++)
12    {
13        if(instr[start+i] == '/0')
14        {
15            return false;
16        }
17        if(instr[start+i] != substr[i])
18        {
19            return false;
20        }
21    }
22
23    return true;
24}
25
26// 输出 instr 的 start 开始、长为 len 的部分
27void output(int start, int len)
28{
29    for(int i=0; i<len; i++)
30    {
31        outstr[out_pos++] = instr[start+i];
32    }
33
34    outstr[out_pos++] = ' ';
35}
36
37// 递归倒序整个字符串
38void reverse(int start)
39{
40    if(instr[start] == '\0') // 递归结束条件
41    {
42        return;
43    }
44
45    while(instr[start] == ' ')  // 找到一个非空格字符(这里假定单词间以空格分隔, 不考虑 /t 之类的)
46    {
47        start++;
48    }
49
50    if(compare(start))  // 如果当前位置开始与子串一样
51    {
52        reverse(start + substrlen);  // 跳过这个子串长度,处理下面的部分
53        output(start, substrlen);  // 输出这个子串
54    }
55    else  // 如果当前位置开始与子串不一样
56    {
57        int next=start;
58        while(instr[next] != ' ' && instr[next] != '/0')  // 找当前单词结束处
59        {
60            next++;
61        }
62        reverse(next);  // 处理下一个单词
63        output(start, next-start);  // 输出这个单词
64    }
65}
66
67int main()
68{
69    //gets(instr);
70    //gets(substr);
71    strcpy(instr, "The quick brown fox jumps over the lazy dog");
72    strcpy(substr, "brown fox");
73    substrlen = strlen(substr);  // 这个长度多次用到,在这里先算出来
74    reverse(0);
75    printf("%s/n", outstr);
76    return 0;
77}

首发:https://blog.csdn.net/cnStreamlet/article/details/2576153



NoteIsSite/0.4