C++博客-no_rain

C++的一个语法问题

is-programmer — Fri, 16 Mar 2012 13:13:00 GMT

今天看到《C++ primer》上说：可以用派生类对象初始化基类对象，根据是派生类对象可以赋值给基类的对象的引用。这里我觉得有个语义上的问题：派生类在继承基类的时候，基类的private成员是不可见的，那么基类初始化private对象的时候，就用了派生类的不可见成员去初始化它了。
先贴段测试代码：

1 #include
2 using namespace std;
3 class A
4 {
5       int mem1,mem2;
6 public:
7        A(const A& a);
8        A(int a, int b):mem1(a),mem2(b){}
9        int fun1(){return mem1;}
10        int fun2(){return mem2;}
11 };
12 A::A(const A& a)
13 {
14            mem1 = a.mem1;
15            mem2 = a.mem2;
16            cout << "A's copy constructor called"<17 }
18 class B : public A
19 {
20       int mem3;
21 public:
22   B(int a, int b, int c): A(a,b),mem3(c){}
23     int fun3(){return fun1()};
24 };
25 int main()
26 {
27     B b(1,2,3);
28     A aob(b);
29 }
30

这段代码输出：A's copy constructor called（这是用G++编译器的，DEV C++ 编译通过，可是运行没有输出）
确实如书上说的派生类对象可以赋值给基类的对象的引用，所以调用了拷贝构造函数。其实根据《inside the C++ object model》的说法，派生类的对象中将会保存基类的non-static数据成员的，那么即使不可见，可以用来初始化也在情理之中。
可是再看被初始化对象调用其成员函数的代码:

这就编译错误了：tess.cpp:28:36: error: request for member ‘fun2’ in ‘aob’, which is of non-class type ‘A(B)’这在两个上述编译器都是这样的结果。那么这个对象就无法调用基类的函数了。
我个人肤浅的推断：A（B）将被编译器认为是一种新的类型对待，那么怎么确定这种类型的接口函数呢？这不就有问题了吗？
我再多此一举的实验下如下代码：

1 #include
2 using namespace std;
3 class A
4 {
5       int mem1,mem2;
6 public:
7        A(const A& a);
8        A(int a, int b):mem1(a),mem2(b){}
9        int fun1(){return mem1;}
10        int fun2(){return mem2;}
11 };
12 A::A(const A& a)
13 {
14            mem1 = a.mem1;
15            mem2 = a.mem2;
16            cout << "A's copy constructor called"<17 }
18 class B : public A
19 {
20       int mem3;
21 public:
22   B(int a, int b, int c): A(a,b),mem3(c){}
23     int fun3(){return fun1();}
24 };
25 int main()
26 {
27     B b(1,2,3);
28     A aob(b);
29     cout <// the difference
30 }
31

结果是编译错误：‘class A’ has no member named ‘fun3’这一点也不意外，那么这样的对象不就真的没有了接口了？小弟我虚心等待大牛们的解答，希望能在原理上给俺个解释，不胜感激！

is-programmer 2012-03-16 21:13 发表评论

大三下学期--迷茫困惑

is-programmer — Fri, 24 Feb 2012 05:57:00 GMT

今天去面试了个实习，公司需要一个做java web开发的，可是我完全不明白。面试我的人给我个小项目让我自己做，要我一周内完成，java没学过，web前端后端什么的也只是听说，话说那个小项目如果我现学现卖的话也应该不会很难，可是我却陷入了迷茫：也就是自己发展方向的选择（需要可以找到相应合适工作的发展方向）的困惑。
我个人的情况是这样子的：211本科数学专业，学习过网络，也了解TCP/IP；学习过数据库，可以熟练的写SQL；自学过操作系统，觉得挺有趣，还自学了一点体系结构，汇编语言，后来觉得更有趣了；使用了linux，基本的命令行挺熟悉的；计算机语言也就会C/C++，平时写过一些小东西，实现下一些算法和数学上的东西；用过python写过一个小作业，发现语言这东西都比较像，区别也就在用途和与机器语言的偏离水平，越是新的语言越是脱离机器底层，也越容易应用；当然数据结构算法之类的也会一些，可惜没有拿过ACM省级以上的奖。
现在就是不明白有什么方向可以努力的呢？工作？考研？各位工作过的朋友可不可以不吝赐教，给点建议呀！

is-programmer 2012-02-24 13:57 发表评论

关于人脑的一点思考（二）-幸福

is-programmer — Wed, 15 Feb 2012 13:03:00 GMT

幸福，快乐，happiness这里是同一个词。
如果一个人可以获得一些成功，比如我买彩票获得大奖，比如当年考大学考上了一个好的大学，比如找到一个让旁人震惊的漂亮女朋友等等。那么人就会感到幸福，这是不可否认的。但是，这样子的幸福不可能维持很久，不久我们就会习惯了这一切，就如故事里那个拥有花不完财富的国王说他不幸福一样，我们不会我们已经拥有的一切说是幸福了，即使我们不停地听到要感恩和知足。我们可能会认为获得诺贝尔奖将给一个人的一生获得长久的幸福，而事实是那些获得诺贝尔奖的人在他们的人生的大部分时间都不会因为自己是诺贝尔奖得主而感到幸福，甚至不会觉得自己有和其他人有什么不同。我们都高估了对那些看似意义深远的东西所能给我们的幸福感。

有人不停地追求幸福。他们为了幸福的时刻拼尽全力。以至于吸烟，酗酒，乃至于吸毒，滥交，其实这些没有想象的那么不好，至少可以给人一定时间的满足感，幸福感，不然也就不会有不少明星，大款喜欢这些，只是社会舆论排斥这些。极限运动也是开始备受推崇，如蹦极，跳伞等等。可是这一切也是会过去的，不过可以给人一定时间是出于幸福的状态的。
其实我想说人根本就不应该追求幸福！
没有什么是可以带来长久的幸福感的！获得之后就会take it for granted！
所以我们要做甘于过平淡日子的人，他们实际上不会去刻意追求幸福感本身，而是一些有价值和有意义的事。如金钱，家庭和睦，自由等等。

is-programmer 2012-02-15 21:03 发表评论

动态规划之矩阵连乘问题

is-programmer — Wed, 28 Dec 2011 10:45:00 GMT

如果没有人告诉你矩阵连乘问题就应该用动态规划的方法来解决，那么我们应该如何想到呢？
wiki：动态规划是这样子的
这里有对矩阵连乘问题的描述。首先应该对问题进行抽象，如果能够了解问题中矩阵的部分，那么问题可以抽象成这样poj1651。这里问题的另一种简单的表示方式就是：给定一列数，每次你可以从中抽取1个数（除去头尾两个数不可以抽取），设置一个score，当你抽取该数的时候，score要加上该数和左右两个数的乘积，问抽取到最后只剩下头尾两个数的时候，怎样的抽取顺序可以使score的值最小呢？
很直观的方法就是枚举每种抽取方式，然后找出使score最小的那一次抽取。（这被称为笨办法）
先设有n个要抽取的数，也就是总数为n+2。我们试着从中抽取m个，那么我们会发现在省下的那些还没被抽取的数字中应该存在一种抽取策略使得它们的score最小（最优子结构，这里可以用简单的反证法说明），换句话说，就是我们前面怎样的抽取顺序对后面不会造成影响。这里就说明了笨办法为什么笨了：如果我们找出了后面抽取的最优策略后，那么每次我们改变前面的m个数的抽取顺序时，是不需要对后面抽取顺序进行枚举的，只有用最优那个策略即可（重叠子问题）。
那么这样说的话，只要找出前面抽取的最优策略和后面抽取的最优策略的话，那么就可以找出这样的结果：以先抽取m个为分界限的最优解。那么要求抽取n个球的问题时，就需要从1开始到n/2为分界限的最优解。然后再对每个子问题进行递归的求解，当n=1时那么问题无需再进行分解。
上面这样子理解有个缺点：很难用计算机语言实现。问题在于先抽取m个数，这些数的位置不连续。其实把它改为连续的对题目的求解也是一样的，不过这时候要找的就不是从1到n/2为分界限的最优解了（这样的话就不全面）。应该从开头的1，一直到n-1进行找最优解。
这是poj1651的代码：

1 #include<iostream>
2 using namespace std;
3 const int inf = 0xffffff;
4 int dp[101][101];
5 int num[101];
6 void input(int n){
7      for(int i = 1 ; i <= n; i++)
8              cin>>num[i];
9      for(int i = 0; i <= n; i++)
10              for(int j = 0 ; j <= n; j++)
11                      dp[i][j] = inf;
12 }
13 int solve(int a,int b){
14     if(dp[a][b] != inf)return dp[a][b];
15     if(b - a == 2){
16          dp[a][b] = num[a]*num[a+1]*num[b];
17          return dp[a][b];
18     }
19     if(b - a == 1){
20          dp[a][b] = 0;
21          return dp[a][b];
22     }
23     int min = inf;
24     int temp;
25     for(int i = a+1 ; i < b; i ++){
26             temp = solve(a,i) + solve(i,b) + num[a]*num[i]*num[b];
27             if(temp < min) min = temp;
28     }
29     dp[a][b] = min;
30     return dp[a][b];
31 }
32 int main(){
33     int n;
34     while(cin >> n){
35               input(n);
36               cout << solve(1,n)<<endl;
37     }
38 }

is-programmer 2011-12-28 18:45 发表评论

二分思想在幂中的应用（poj3070）

is-programmer — Wed, 28 Dec 2011 07:06:00 GMT

回想起以前从事ACM活动，每当有一些题目做不出来，总是会去网上找别人的解题报告。可是这些解题报告不是写给人看的：一句dp，二分，线段树，然后直接就贴了代码，而且为了追求效率，这些代码做的优化都很大程度增加了阅读的难度。比如不写函数。
poj3070
这道题的意思是通过矩阵的幂来求Fibonacci数列的第n项，且只要求出它的后4位数。
先贴出我认为写的还是比较清晰的代码：

1 #include
2 using namespace std;
3 class matrix{
4 public:
5   int a[2][2];
6   matrix(){
7     a[0][0]=a[0][1]=a[1][0]=1;
8     a[1][1]=0;
9   }
10 };
11 //矩阵的乘法
12 matrix multi(matrix a,matrix b){
13   matrix temp;
14   for(int i = 0; i < 2; i++)
15     for(int j = 0; j < 2; j++){
16       temp.a[i][j] = 0;
17       for(int k = 0; k < 2;k++)
18     temp.a[i][j] += a.a[i][k]*b.a[k][j];
19       if(temp.a[i][j] >= 10000)
20     temp.a[i][j] %= 10000;//注释1
21     }
22   return temp;
23 }
24 //矩阵的n次幂
25 matrix power(int n){
26   matrix temp,s;
27   temp.a[1][0] = temp.a[0][1] = 0;
28   temp.a[1][1] = 1;//把temp化成单位矩阵
29   while(n != 0){
30     if(n & 1)
31       temp = multi(temp,s);
32     n = n >> 1;
33     s = multi(s,s);
34   }
35   return temp;
36 }
37 int main(){
38   int n;
39   while(cin >> n && n != -1){
40     matrix ans = power(n);
41     cout << ans.a[1][0] << endl;
42   }
43 }
44
45
46
47

注释1：为什么可以在每次乘法的取模呢？这是因为：(a*10000+b)*(c*10000+d)，即(a*10000+b)和(c*10000+d)这两个数相乘得到的后四位数是由b，d决定的。那么每次取模也就不影响后四位数了。
在做幂的时候其实体现的就是二分的思想，这可以算是计算机科学中最重要的思想之一了。
其实像我这样的小菜是有多么希望那些牛人可以花点时间把自己对一道题的理解和思路写出来，你可以不必每道题都写出详细的解题报告，但是你可以在那道没有人写详细思路题上花点时间，这样可以帮助到很多人！

is-programmer 2011-12-28 15:06 发表评论

关于人的大脑一点思考

is-programmer — Sat, 24 Dec 2011 05:10:00 GMT

人在每时每刻都在做着决策，那么人是怎样做出决策的呢？人的大脑有高级的理性部分，也有原始初级的部分。原始初级的部分在几十万年的人类进化长河中是通过优胜劣汰所保留下来。其中贪婪，好斗，嫉妒确实对个体在原始社会中获得了更好的繁殖机会，也就把这部分的基因保存了下来。而近几百年来，人类的理性大脑在社会进步中起到了非常重要的作用，反过来，人类的生活也受到现代社会的深刻变化的影响。
基本不用怀疑的，在当今社会，如果一个人能受理性思维多一点的控制，他应该能够在这个以理性和科学的力量而构建起来的世界有更好的适应能力。
回到开头的问题，人是如何做决策的。人在面对选择的时候，如果他那时候还能用理性思维控制大脑的话，他应该是这样做的：首先，他对这件事情在自己或他人的经历中有没有出现过（特别是自己），当时理论上最成功的决策应该是什么，然后选取它做为当前事情的决策；如果没有发生过，那么理性的推导之后得出结论，从而决策。社会的复杂性使人的推导过程必然是不严谨的，或者说是人的推导总是有很多假设存在的，但是这总比原始大脑那种潜意识的想法要优质的多。
Ok，决策想好了，接下来就要开始行动了。例如，我决定接下来的一个小时的时间要来看一本数据库的书。我翻开书，专注的看了15分钟，在此期间原始大脑发出各种各样的奇怪的请求（它确实会这样，而且一直这样，这毕竟是几十万年进化中遗留下来的），我要吃东西，这本书很无聊，我要打游戏，我要很多钱但是不要辛苦，我要美女~~据一项科学研究的结果，人在不是很重要的会议上，1/3的时间是在进行性幻想的。这时候，在不知不觉中，我的大脑的控制权应经交给了原始大脑，而且更加严重的问题是，像进程切换没有保存上下文一样，我没有记得自己已经看到了哪里！过了一会理性的大脑回来的时候，我又需要重新开始看！这个时候，原始的大脑又开始发话了，算了吧，那就干脆别看了。这也就是为什么坚持做好一件事情有那么的难。
“该干嘛干嘛去！”这是人们常对自己和一些比较亲密的人一句很常见的提醒。这就话有时有一定的功效，归结其原因还是要看一下这句话的本质是什么：在已经做完决策之后，请你根据理性的大脑的决策一直执行下去吧。
接着，我想说的另一个相关的观点就是：如果我们是通过深思熟虑而做出的一个中等期限的决策（比如说半年内要学什么，或者准备什么考试），那么请不要轻易改变它或者取消它。Ok，人即使是用理性的大脑做出的决策也是充满着错误和偏见的，那么还有什么必要去为一个不可靠的决策去坚持呢？其实原因很简单：其一，如果我们推翻自己的结论，那么必然我们需要重新去做一次深思熟虑的决策，那时候的决策不也是一样的不可靠？其二，在现在的社会，如果一个人想对某一方面有所了解，不用说精通，所需要的时间是不可能很短的。短视，急功近利的原始大脑在原始社会中确实起了作用，但是在现代社会则不那么容易有用了。

is-programmer 2011-12-24 13:10 发表评论

huffman 编码学习

is-programmer — Tue, 06 Dec 2011 06:46:00 GMT

该程序实现的功能是将一段字符串进行统计之后再进行huffman编码（二进制）；
注意的地方：
1，huffman编码要用到贪心算法，所以用priority_queue可以在常量时间内取出和插入值。
2，静态建树：huffman树的节点表示方法采用了最多的变量，即父亲节点，左右子节点（因为程序中确实有这种需要，这里不同与二叉堆，无法通过在静态树（链表）的位置来确定其父亲节点和子节点）；

1 #include
  2 #include
  3 #include
  4 #include
  5 using namespace std;
  6 const int MAXSIZE = 27;
  7 class huffNode{
  8 public:
  9   int pr;
10   int lc , rc;
11   char s;
12   int pow;
13   bool operator < (const huffNode& b)const{
14     return pow > b.pow;
15   }
16 };
17 huffNode huff[MAXSIZE * 2];
18 string buf;
19 int count[26];
20 priority_queue greed;
21 //for the sake of convenience , assume that the
22 //standard input is from 'a' to 'z'.
23 int  input(){
24   cout << "input the text!"< 25   cin >> buf;
26   for(int i = 0; i < 26 ; i++) count[i] = 0;
27   memset(huff , 0, sizeof(huff));
28   for(int i = 0; i < buf.length();i++)count[buf[i]-'a']++;
29   int len = 0;
30   for(int i = 0 ,j = 0; i < 26; i++)
31     if(count[i]){
32       huff[j].s = i + 'a';
33       huff[j].pow = count[i];
34       huff[j].pr = j;
35       cout << "the" << ' '<<'\''<< char(i+'a') <<'\''
36        <<' '<<"have arisen for " < 37        < 38       greed.push(huff[j]);
39       len = j;
40       j++;
41     }
42   return len;
43 }
44
45 int createTree(int len){
46   if(len == 0) {
47     cout << " Only one kind of alf !"< 48     exit(1);
49   }
50   huffNode temp1 ,temp2,temp;
51   while(!greed.empty()){
52     temp1 = greed.top();
53     greed.pop();
54     temp2 = greed.top();
55     greed.pop();
56     len ++;
57     temp.lc = temp1.pr;
58     temp.rc = temp2.pr;
59     huff[temp1.pr].pr = huff[temp2.pr].pr = len;
60     temp.pr = len;
61     temp.pow = temp1.pow + temp2.pow;
62     huff[len] = temp;
63     if(!greed.empty()) greed.push(temp);
64   }
65   return len;
66 }
67
68 void reserve(char * a){
69   int len = strlen(a);
70   for(int i = 0 ; i <= len/2 ;i ++)
71     swap(a[i],a[len-i-1]);
72 }
73 struct code{
74   char s;
75   char co[50];
76 };
77
78 void coding(int len1,int len2){
79   code* mycode = new code[len1+1];
80   memset(mycode ,0 ,sizeof(mycode));
81   for(int i = 0; i <= len1 ; i++){
82     int j = i;
83     int t = 0;
84     mycode[i].s = huff[i].s;
85     while(j < len2){
86       if(huff[huff[j].pr].lc == j)
87     mycode[i].co[t++] = '0';
88       else mycode[i].co[t++] = '1';
89       j = huff[j].pr ;
90     }
91     reserve(mycode[i].co);
92     cout << "the code of " << mycode[i].s
93      << " is " << mycode[i].co < 94   }
95   delete[] mycode;
96 }
97
98 int main(){
99   int len1 = input();
100   int len2 = createTree(len1);
101   coding(len1,len2);
102 }
103
104
105
106

is-programmer 2011-12-06 14:46 发表评论