2012年3月16日
今天看到《C++ primer》上說(shuō):可以用派生類對(duì)象初始化基類對(duì)象,根據(jù)是派生類對(duì)象可以賦值給基類的對(duì)象的引用。這里我覺(jué)得有個(gè)語(yǔ)義上的問(wèn)題:派生類在繼承基類的時(shí)候,基類的private成員是不可見(jiàn)的,那么基類初始化private對(duì)象的時(shí)候,就用了派生類的不可見(jiàn)成員去初始化它了。
先貼段測(cè)試代碼:
1 #include<iostream>
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"<<endl;
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++ 編譯通過(guò),可是運(yùn)行沒(méi)有輸出)確實(shí)如書(shū)上說(shuō)的派生類對(duì)象可以賦值給基類的對(duì)象的引用,所以調(diào)用了拷貝構(gòu)造函數(shù)。其實(shí)根據(jù)《inside the C++ object model》的說(shuō)法,派生類的對(duì)象中將會(huì)保存基類的non-static數(shù)據(jù)成員的,那么即使不可見(jiàn),可以用來(lái)初始化也在情理之中。
可是再看被初始化對(duì)象調(diào)用其成員函數(shù)的代碼:
1 #include<iostream>
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"<<endl;
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 <<aob.fun1() << aob.fun2();//the //difference
30 }
31
這就編譯錯(cuò)誤了:tess.cpp:28:36: error: request for member ‘fun2’ in ‘aob’, which is of non-class type ‘A(B)’這在兩個(gè)上述編譯器都是這樣的結(jié)果。那么這個(gè)對(duì)象就無(wú)法調(diào)用基類的函數(shù)了。
我個(gè)人膚淺的推斷:A(B)將被編譯器認(rèn)為是一種新的類型對(duì)待,那么怎么確定這種類型的接口函數(shù)呢?這不就有問(wèn)題了嗎?
我再多此一舉的實(shí)驗(yàn)下如下代碼:
1 #include<iostream>
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"<<endl;
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 <<aob.fun3();// the difference
30 }
31
結(jié)果是編譯錯(cuò)誤:‘class A’ has no member named ‘fun3’這一點(diǎn)也不意外,那么這樣的對(duì)象不就真的沒(méi)有了接口了?小弟我虛心等待大牛們的解答,希望能在原理上給俺個(gè)解釋,不勝感激!
2012年2月24日
今天去面試了個(gè)實(shí)習(xí),公司需要一個(gè)做java web開(kāi)發(fā)的,可是我完全不明白。面試我的人給我個(gè)小項(xiàng)目讓我自己做,要我一周內(nèi)完成,java沒(méi)學(xué)過(guò),web前端后端什么的也只是聽(tīng)說(shuō),話說(shuō)那個(gè)小項(xiàng)目如果我現(xiàn)學(xué)現(xiàn)賣的話也應(yīng)該不會(huì)很難,可是我卻陷入了迷茫:也就是自己發(fā)展方向的選擇(需要可以找到相應(yīng)合適工作的發(fā)展方向)的困惑。
我個(gè)人的情況是這樣子的:211本科數(shù)學(xué)專業(yè),學(xué)習(xí)過(guò)網(wǎng)絡(luò),也了解TCP/IP;學(xué)習(xí)過(guò)數(shù)據(jù)庫(kù),可以熟練的寫(xiě)SQL;自學(xué)過(guò)操作系統(tǒng),覺(jué)得挺有趣,還自學(xué)了一點(diǎn)體系結(jié)構(gòu),匯編語(yǔ)言,后來(lái)覺(jué)得更有趣了;使用了linux,基本的命令行挺熟悉的;計(jì)算機(jī)語(yǔ)言也就會(huì)C/C++,平時(shí)寫(xiě)過(guò)一些小東西,實(shí)現(xiàn)下一些算法和數(shù)學(xué)上的東西;用過(guò)python寫(xiě)過(guò)一個(gè)小作業(yè),發(fā)現(xiàn)語(yǔ)言這東西都比較像,區(qū)別也就在用途和與機(jī)器語(yǔ)言的偏離水平,越是新的語(yǔ)言越是脫離機(jī)器底層,也越容易應(yīng)用;當(dāng)然數(shù)據(jù)結(jié)構(gòu)算法之類的也會(huì)一些,可惜沒(méi)有拿過(guò)ACM省級(jí)以上的獎(jiǎng)。
現(xiàn)在就是不明白有什么方向可以努力的呢?工作?考研?各位工作過(guò)的朋友可不可以不吝賜教,給點(diǎn)建議呀!
2012年2月15日
幸福,快樂(lè),happiness這里是同一個(gè)詞。
如果一個(gè)人可以獲得一些成功,比如我買彩票獲得大獎(jiǎng),比如當(dāng)年考大學(xué)考上了一個(gè)好的大學(xué),比如找到一個(gè)讓旁人震驚的漂亮女朋友等等。那么人就會(huì)感到幸福,這是不可否認(rèn)的。但是,這樣子的幸福不可能維持很久,不久我們就會(huì)習(xí)慣了這一切,就如故事里那個(gè)擁有花不完財(cái)富的國(guó)王說(shuō)他不幸福一樣,我們不會(huì)我們已經(jīng)擁有的一切說(shuō)是幸福了,即使我們不停地聽(tīng)到要感恩和知足。我們可能會(huì)認(rèn)為獲得諾貝爾獎(jiǎng)將給一個(gè)人的一生獲得長(zhǎng)久的幸福,而事實(shí)是那些獲得諾貝爾獎(jiǎng)的人在他們的人生的大部分時(shí)間都不會(huì)因?yàn)樽约菏侵Z貝爾獎(jiǎng)得主而感到幸福,甚至不會(huì)覺(jué)得自己有和其他人有什么不同。我們都高估了對(duì)那些看似意義深遠(yuǎn)的東西所能給我們的幸福感。
有人不停地追求幸福。他們?yōu)榱诵腋5臅r(shí)刻拼盡全力。以至于吸煙,酗酒,乃至于吸毒,濫交,其實(shí)這些沒(méi)有想象的那么不好,至少可以給人一定時(shí)間的滿足感,幸福感,不然也就不會(huì)有不少明星,大款喜歡這些,只是社會(huì)輿論排斥這些。極限運(yùn)動(dòng)也是開(kāi)始備受推崇,如蹦極,跳傘等等??墒沁@一切也是會(huì)過(guò)去的,不過(guò)可以給人一定時(shí)間是出于幸福的狀態(tài)的。
其實(shí)我想說(shuō)人根本就不應(yīng)該追求幸福!
沒(méi)有什么是可以帶來(lái)長(zhǎng)久的幸福感的!獲得之后就會(huì)take it for granted!
所以我們要做甘于過(guò)平淡日子的人,他們實(shí)際上不會(huì)去刻意追求幸福感本身,而是一些有價(jià)值和有意義的事。如金錢(qián),家庭和睦,自由等等。
2011年12月28日
如果沒(méi)有人告訴你矩陣連乘問(wèn)題就應(yīng)該用動(dòng)態(tài)規(guī)劃的方法來(lái)解決,那么我們應(yīng)該如何想到呢?
wiki:
動(dòng)態(tài)規(guī)劃是這樣子的這里有對(duì)矩陣連乘問(wèn)題的描述。首先應(yīng)該對(duì)問(wèn)題進(jìn)行抽象,如果能夠了解問(wèn)題中矩陣的部分,那么問(wèn)題可以抽象成這樣
poj1651。這里問(wèn)題的另一種簡(jiǎn)單的表示方式就是:給定一列數(shù),每次你可以從中抽取1個(gè)數(shù)(除去頭尾兩個(gè)數(shù)不可以抽取),設(shè)置一個(gè)score,當(dāng)你抽取該數(shù)的時(shí)候,score要加上該數(shù)和左右兩個(gè)數(shù)的乘積,問(wèn)抽取到最后只剩下頭尾兩個(gè)數(shù)的時(shí)候,怎樣的抽取順序可以使score的值最小呢?
很直觀的方法就是枚舉每種抽取方式,然后找出使score最小的那一次抽取。(這被稱為笨辦法)
先設(shè)有n個(gè)要抽取的數(shù),也就是總數(shù)為n+2。我們?cè)囍鴱闹谐槿個(gè),那么我們會(huì)發(fā)現(xiàn)在省下的那些還沒(méi)被抽取的數(shù)字中應(yīng)該存在一種抽取策略使得它們的score最小(
最優(yōu)子結(jié)構(gòu),這里可以用簡(jiǎn)單的反證法說(shuō)明),換句話說(shuō),就是我們前面怎樣的抽取順序?qū)竺娌粫?huì)造成影響。這里就說(shuō)明了笨辦法為什么笨了:如果我們找出了后面抽取的最優(yōu)策略后,那么每次我們改變前面的m個(gè)數(shù)的抽取順序時(shí),是不需要對(duì)后面抽取順序進(jìn)行枚舉的,只有用最優(yōu)那個(gè)策略即可(
重疊子問(wèn)題)。
那么這樣說(shuō)的話,只要找出前面抽取的最優(yōu)策略和后面抽取的最優(yōu)策略的話,那么就可以找出這樣的結(jié)果:以先抽取m個(gè)為分界限的最優(yōu)解。那么要求抽取n個(gè)球的問(wèn)題時(shí),就需要從1開(kāi)始到n/2為分界限的最優(yōu)解。然后再對(duì)每個(gè)子問(wèn)題進(jìn)行遞歸的求解,當(dāng)n=1時(shí)那么問(wèn)題無(wú)需再進(jìn)行分解。
上面這樣子理解有個(gè)缺點(diǎn):很難用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)。問(wèn)題在于先抽取m個(gè)數(shù),這些數(shù)的位置不連續(xù)。其實(shí)把它改為連續(xù)的對(duì)題目的求解也是一樣的,不過(guò)這時(shí)候要找的就不是從1到n/2為分界限的最優(yōu)解了(這樣的話就不全面)。應(yīng)該從開(kāi)頭的1,一直到n-1進(jìn)行找最優(yōu)解。
這是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 }
回想起以前從事ACM活動(dòng),每當(dāng)有一些題目做不出來(lái),總是會(huì)去網(wǎng)上找別人的解題報(bào)告??墒?strong>這些解題報(bào)告不是寫(xiě)給人看的:一句dp,二分,線段樹(shù),然后直接就貼了代碼,而且為了追求效率,這些代碼做的優(yōu)化都很大程度增加了閱讀的難度。比如不寫(xiě)函數(shù)。
poj3070
這道題的意思是通過(guò)矩陣的冪來(lái)求Fibonacci數(shù)列的第n項(xiàng),且只要求出它的后4位數(shù)。
先貼出我認(rèn)為寫(xiě)的還是比較清晰的代碼:
1 #include<iostream>
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:為什么可以在每次乘法的取模呢?這是因?yàn)椋?a*10000+b)*(c*10000+d),即(a*10000+b)和(c*10000+d)這兩個(gè)數(shù)相乘得到的后四位數(shù)是由b,d決定的。那么每次取模也就不影響后四位數(shù)了。
在做冪的時(shí)候其實(shí)體現(xiàn)的就是二分的思想,這可以算是計(jì)算機(jī)科學(xué)中最重要的思想之一了。
其實(shí)像我這樣的小菜是有多么希望那些牛人可以花點(diǎn)時(shí)間把自己對(duì)一道題的理解和思路寫(xiě)出來(lái),你可以不必每道題都寫(xiě)出詳細(xì)的解題報(bào)告,但是你可以在那道沒(méi)有人寫(xiě)詳細(xì)思路題上花點(diǎn)時(shí)間,這樣可以幫助到很多人!
2011年12月24日
人在每時(shí)每刻都在做著決策,那么人是怎樣做出決策的呢?人的大腦有高級(jí)的理性部分,也有原始初級(jí)的部分。原始初級(jí)的部分在幾十萬(wàn)年的人類進(jìn)化長(zhǎng)河中是通過(guò)優(yōu)勝劣汰所保留下來(lái)。其中貪婪,好斗,嫉妒確實(shí)對(duì)個(gè)體在原始社會(huì)中獲得了更好的繁殖機(jī)會(huì),也就把這部分的基因保存了下來(lái)。而近幾百年來(lái),人類的理性大腦在社會(huì)進(jìn)步中起到了非常重要的作用,反過(guò)來(lái),人類的生活也受到現(xiàn)代社會(huì)的深刻變化的影響。
基本不用懷疑的,在當(dāng)今社會(huì),如果一個(gè)人能受理性思維多一點(diǎn)的控制,他應(yīng)該能夠在這個(gè)以理性和科學(xué)的力量而構(gòu)建起來(lái)的世界有更好的適應(yīng)能力。
回到開(kāi)頭的問(wèn)題,人是如何做決策的。人在面對(duì)選擇的時(shí)候,如果他那時(shí)候還能用理性思維控制大腦的話,他應(yīng)該是這樣做的:首先,他對(duì)這件事情在自己或他人的經(jīng)歷中有沒(méi)有出現(xiàn)過(guò)(特別是自己),當(dāng)時(shí)理論上最成功的決策應(yīng)該是什么,然后選取它做為當(dāng)前事情的決策;如果沒(méi)有發(fā)生過(guò),那么理性的推導(dǎo)之后得出結(jié)論,從而決策。社會(huì)的復(fù)雜性使人的推導(dǎo)過(guò)程必然是不嚴(yán)謹(jǐn)?shù)?,或者說(shuō)是人的推導(dǎo)總是有很多假設(shè)存在的,但是這總比原始大腦那種潛意識(shí)的想法要優(yōu)質(zhì)的多。
Ok,決策想好了,接下來(lái)就要開(kāi)始行動(dòng)了。例如,我決定接下來(lái)的一個(gè)小時(shí)的時(shí)間要來(lái)看一本數(shù)據(jù)庫(kù)的書(shū)。我翻開(kāi)書(shū),專注的看了15分鐘,在此期間原始大腦發(fā)出各種各樣的奇怪的請(qǐng)求(它確實(shí)會(huì)這樣,而且一直這樣,這畢竟是幾十萬(wàn)年進(jìn)化中遺留下來(lái)的),我要吃東西,這本書(shū)很無(wú)聊,我要打游戲,我要很多錢(qián)但是不要辛苦,我要美女~~據(jù)一項(xiàng)科學(xué)研究的結(jié)果,人在不是很重要的會(huì)議上,1/3的時(shí)間是在進(jìn)行性幻想的。這時(shí)候,在不知不覺(jué)中,我的大腦的控制權(quán)應(yīng)經(jīng)交給了原始大腦,而且更加嚴(yán)重的問(wèn)題是,像進(jìn)程切換沒(méi)有保存上下文一樣,我沒(méi)有記得自己已經(jīng)看到了哪里!過(guò)了一會(huì)理性的大腦回來(lái)的時(shí)候,我又需要重新開(kāi)始看!這個(gè)時(shí)候,原始的大腦又開(kāi)始發(fā)話了,算了吧,那就干脆別看了。這也就是為什么堅(jiān)持做好一件事情有那么的難。
“該干嘛干嘛去!”這是人們常對(duì)自己和一些比較親密的人一句很常見(jiàn)的提醒。這就話有時(shí)有一定的功效,歸結(jié)其原因還是要看一下這句話的本質(zhì)是什么:在已經(jīng)做完決策之后,請(qǐng)你根據(jù)理性的大腦的決策一直執(zhí)行下去吧。
接著,我想說(shuō)的另一個(gè)相關(guān)的觀點(diǎn)就是:如果我們是通過(guò)深思熟慮而做出的一個(gè)中等期限的決策(比如說(shuō)半年內(nèi)要學(xué)什么,或者準(zhǔn)備什么考試),那么請(qǐng)不要輕易改變它或者取消它。Ok,人即使是用理性的大腦做出的決策也是充滿著錯(cuò)誤和偏見(jiàn)的,那么還有什么必要去為一個(gè)不可靠的決策去堅(jiān)持呢?其實(shí)原因很簡(jiǎn)單:其一,如果我們推翻自己的結(jié)論,那么必然我們需要重新去做一次深思熟慮的決策,那時(shí)候的決策不也是一樣的不可靠?其二,在現(xiàn)在的社會(huì),如果一個(gè)人想對(duì)某一方面有所了解,不用說(shuō)精通,所需要的時(shí)間是不可能很短的。短視,急功近利的原始大腦在原始社會(huì)中確實(shí)起了作用,但是在現(xiàn)代社會(huì)則不那么容易有用了。
2011年12月6日
該程序?qū)崿F(xiàn)的功能是將一段字符串進(jìn)行統(tǒng)計(jì)之后再進(jìn)行huffman編碼(二進(jìn)制);
注意的地方:
1,huffman編碼要用到貪心算法,所以用priority_queue可以在常量時(shí)間內(nèi)取出和插入值。
2,靜態(tài)建樹(shù):huffman樹(shù)的節(jié)點(diǎn)表示方法采用了最多的變量,即父親節(jié)點(diǎn),左右子節(jié)點(diǎn)(因?yàn)槌绦蛑写_實(shí)有這種需要,這里不同與二叉堆,無(wú)法通過(guò)在靜態(tài)樹(shù)(鏈表)的位置來(lái)確定其父親節(jié)點(diǎn)和子節(jié)點(diǎn));
1 #include<iostream>
2 #include<cstring>
3 #include<queue>
4 #include<cstdlib>
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<huffNode> 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!"<<endl;
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 " <<count[i]<<" time(s)"
37 <<endl;
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 !"<<endl;
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 <<endl;
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