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
里的 string
和 stack
的,试了下,因为我对 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