2009年7月30日 星期四

ACM Q10110


#include <iostream>
#include <math.h>
using namespace std;
int main(void){
        unsigned int N;
        while(true){
                cin>>N;
                if(N==0)
                        break;
                if((int)(sqrt(N))*(int)(sqrt(N))==N)
                        cout<<"yes"<<endl;
                else
                        cout<<"no"<<endl;
        }
        return 0;
}

下面是錯誤的code:


#include <iostream>
#include <math.h>
using namespace std;
int main(void){
        long long int N;
        while(true){
                cin>>N;
                if(N==0)
                        break;
                if((int)(sqrt(N))*(int)(sqrt(N))==N)
                        cout<<"yes"<<endl;
                else
                        cout<<"no"<<endl;
        }
        return 0;
}

2009年7月22日 星期三

範本(Template)& 名稱空間(Namespace)(C++)

 範本(Template)


提供被參數化的型態(Parameterized Types)功能


將數據跟操作分開


名稱空間 (Namespace)


則提供一個名稱管理容器,減低名稱衝突的機會發生


引用: http://caterpillar.onlyfun.net/Gossip/CppGossip/CppGossip.html

函數指標 (Function pointer) v.s. 指標函數(Pointer to function) (c++)

函數指標 (Function pointer)


例如: int (*p) (int, int)


指向函數地址的指標


指標函數(Pointer to function)


例如: float * q = function(num1, num2)


會return 指標的函數

指標陣列(Pointer Array) v.s. 陣列指標(Array Pointer) (c++)

指標陣列 (Pointer Array):

陣列內的元素都為指標

例如: int *a[10];


陣列指標(Array Pointer):

指向陣列的指標

例如: int *a = new int [100];

記得要使用 delete[] 否則會造成 memory leak

常數指標(pointer to constant object) v.s. 指標常數(constant pointer to object) (c++)

Pointer to constant object (const 放在 * 的左邊):


char const * p2;
const char *p3;


被指向的內容不得被修改


但可以做以下的操作


const char* node1 ="abc";
node1 = "xyz"; // node1 可以改指向xyz


Constant pointer to object (const 放在* 的右邊)


char*const p1;
本身不能被修改,但指向的內容可以修改

Class v.s. Struct (c++)

Class 和 Struct 的差別主要有兩個:

1. Struct 定義複雜數據類型, 不能用於OO上

2. class 默認的權限是private
Struct 默認為public

Typedef (c++)

主要功用是為型態取別名

細分為三種應用

1. 簡單型態的別名

typedef unsigned long DWORD;

2. 結構型態的別名

例:
typedef struct card{
int point, char suit;
}name1, *name2;

即可用 name1 obj1, name2 obj2 來建構結構

3. 函式型態的別名

typedef int (*fun)(int x, int y);

定義了函數指標的類型

malloc/free v.s. new/delete

在c中,malloc 只負責配置記憶體, free 只負責釋放記憶體

並不負責初始化與解構化

而當使用new/delete 時

編譯器在編譯到new 後

會自動呼叫 Constructor, 初始化類別

編譯到delete 時

會呼叫destructor, 解構化實體

this 指標 (c++)

每一個類別的函式成員(非靜態)都會隱含一個this指標

指向對象物件

當在函式中使用資料成員時

都會隱含的使用this指標指向對象地址

例如:
int data;
MyClass(int data){
this->data = data;
}

引用跟指標的差別

不同指標可以指向NULL

引用必須初始化

例如: int&rn = a; (a 引用 rn)

而且一但初始化後就不能改變引用的對象

因此比指標來的安全

物件導向

物件導向包含以下三個元素:

1. 封裝 (Encapsulation)

將資料屬性與操作方法放在一起
使程式碼易於理解

2. 繼承 (Inheritance)

子類別可以繼承父類別的屬性與方法
重複使用程式碼

3. 多型 (Polymorphism)

可以透過Overriding 和 Overloading 將使用同一方法卻產生不同行為
方便擴充與維護程式

Inline v.s. Macro

Inline 是在c++ 中加進來以改進c macro 的缺點

不同於macro, Inline 有透過 compiler 做編譯

因而擁有Compiler 所提供的型別確認(Type checcking)的好處

例如:

#define ABS(a) ((a>0)?(a):(-a))

inline int ABS(int a){
if(a>0)
return a;
else
return -a;
}

抽象類別 (Abstract classes)

當所使用的物件都繼承同一基礎類別時

但該類別方法卻不需被實現時

可以建立一個純虛擬函數

例: virtual int f() = 0

做為抽象類別

虛擬函數 (virtual functions)

虛擬函數主要是用來實現多型 (Polymorphism)

透過Overriding 的手法

可以覆寫掉base class 的方法

不用宣告類別為何

即可使用該類別方法

VIM 常用指令

PATTERN 代表符合的樣式

開新的分割視窗
:sp [filename]
- 切換游標所在視窗: ctrl+w 按兩次


所有列做排版:
gg=G

取代指令: s
- 將文件中所有strinA的字串換成stringB: %s/stringA/stringB/g (g表示整行有符合的都換掉, 不加g只取代一行的第一個符合字串)
- 區域取代: 選取一段文字後按s之後接/stringA/stringB/g
- 從游標所在行數開始到最後一行做取代: .,$s/stringA/stringB/g (.表示目前所在行, $表示最後一行)
- 在2~300行之間取代: 2,300s/stringA/stringB/g

將所有符合PATTERN樣式的行做刪除
:g/PATTERN/d

自訂一個strcat (c++)


#include <iostream>
using namespace std;

char *strcat2(char *dest, const char*src);
int main(void){

        char* dest = (char *)malloc(256);
        *dest='\0';
        cout<<strcat2(dest,"concat string")<<endl;

        return 0;
}

char *strcat2(char *dest, const char*src){
        char *ret;
        ret = dest;
        while(*dest++);
        dest--;
        while(*dest++= *src++);

        return ret;
}

Extern (c++)

Extern可以聲明變數會在其它的位置被定義,這個位置可能是在同一份文件之中,或是在其它文件之中.

2009年7月21日 星期二

Static 的作用 (c++)

Static 主要有三種功能:

1. 修飾檔案中的全域變數或函式 保護檔案中的全域變數或函式只限於該檔案使用,不受其他檔案存取

2. 修飾函式中的區域變數,使區域變數具有全域變數的效果,受到static 修飾的變數只會初始一次.

例:
#include
using namespace std;

void func(void){
static int i=0;
i++;
printf("%d", i);
}
int main(void){
for(int j=0; j<10; j++)
func();

return 0;
}

印出:12345678910

3. 修飾類別中的資料或函式成員
static 成員可以用 類別名稱:: 直接使用

參考資料: http://shukaiyang.myweb.hinet.net/courses/cpp/static.zhtw.htm

Palindrome (c++)



#include <iostream>
#include <string>
using namespace std;

int main(void){
string s = "abcdef";
string::iterator pos;
reverse(s.begin(), s.end());

string tmp ="";
for(int i=0; i< s.length(); i++){
tmp += s[s.length()-i-1];
}

for(pos = s.begin(); pos != s.end(); ++pos)
cout<<*pos;
cout<<endl;

cout<<s<<endl;
cout<<tmp<<endl;
return 0;
}

String & int conversion (c++)



#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main(void){

string s= "12345678";

/*string to int:: c_str() version*/
cout<<atoi(s.c_str())+123<<endl;

/*string to int :: stringstream version*/
int tmp;
stringstream ss1(s);
ss1 >> tmp;
cout<< tmp+4<<endl;

int ints = 123;
/*int to string :: sprintf version*/
char str_2[10];
sprintf(str_2,"%d",ints);
cout<<str_2[2]<<endl;
/*int to string :: stringstream version*/
stringstream ss;
ss <<ints;
string str = ss.str();
cout<<str<<endl;
cout<<str[2]<<endl;

return 0;
}

Character Array Shift (c++)



#include <iostream>
using namespace std;

int main(void){
char input[] ="12345678";
int length =(sizeof(input)-1);
int shift;
cin>>shift;
shift = shift % length;
char *tmp = new char[length];
for(int i=0; i< length; i++)
tmp[i]= input[(i+shift)%length];
cout<< tmp <<endl;
return 0;
}

MAX, MIN ,AVG (c++)



#include <iostream>
using namespace std;

int main(void){
int loop;
cin>>loop;
int *ary = new int[loop];

for(int i=0; i<loop; i++){
int tmp;
cin>>tmp;
ary[i] = tmp;
}

int min=ary[0];
int max =ary[0];
float sum =0;
for(int j=1; j< loop ; j++){
if(ary[j]<min)
min = ary[j];
if(ary[j]>max)
max = ary[j];
sum += ary[j];
}
cout<<"Min = "<<min<<endl;
cout<<"Max= "<<max<<endl;
printf("Avg= %.2f\n",(sum/loop));

}

Leap Year (c++)



#include <iostream>
using namespace std;

int main(void){
int year;
cin>> year;
if(year%4==0 && year%100!=0||year%400==0)
cout<<year<<" is Leap Year"<<endl;
else
cout<<year<<" is not Leap Year"<<endl;

return 0;
}

Card Shuffle (c++)



#include <iostream>
#include <time.h>
using namespace std;
struct card{
char color;
int point;

};

void shuffle (struct card *deck, int n){
srand((unsigned) time (NULL));
struct card tmp;
for(int i=0; i< n; i++){
int j = rand()%52;
tmp = deck[i];
deck[i] = deck[j];
deck[j] = tmp;

}

}
int main(void){
struct card deck[52];
for(int i=0; i< 52; i++){
if(i%4==0){
deck[i].color = 's';
deck[i].point = (i/4)+1;
}else if(i%4==1){
deck[i].color = 'd';
deck[i].point = ((i-1)/4)+1;
}else if(i%4==2){
deck[i].color = 'c';
deck[i].point = ((i-2)/4)+1;
}else{
deck[i].color = 'h';
deck[i].point = ((i-3)/4)+1;
}
}
shuffle(deck, 52);
return 0;
}

自訂一個strcmp (c++)



#include <iostream>
using namespace std;
int strcmp2(const char *dest, const char *ori);
int main(void){
cout<<strcmp2("aello","a")<<endl;
return 0;
}
int strcmp2(const char *dest, const char *ori){
assert(ori !=NULL && dest!=NULL);
int tmp =0;
while(!(tmp = *(unsigned char*)dest - *(unsigned char*)ori)&&*ori){
++dest;
++ori;
}
if(tmp <0){
tmp= -1;
}else if(tmp >0){
tmp=1;
}
return tmp;
}

自訂一個strlen(c++)



#include <iostream>
using namespace std;
int strlen2(const char *ori);
int main(void){
cout<<strlen2("hello world")<<endl;
return 0;
}
int strlen2(const char *ori){
assert(ori !=NULL);
int len =0;
while(*ori++ !='\0'){
len++;
}
return len;
}

memcpy v.s. strcpy

從strcpy 跟 memcpy 的實做中可以發現

strcpy 限定複製字串內容

而memcpy 並未限定複製內容,可以複製任何類型的內容

strcpy 遇到 '\0' 時停止複製

memcpy 可以指定要複製多少"內容" (int size)

自訂一個memcpy (c++)



#include <iostream>
using namespace std;
void *memcpy2(void *dest, const void *ori, int size);
int main(void){
char tmp[] = "adfadfaf";
memcpy2(tmp, "hello world",4);
tmp[4]='\0';
cout<<tmp;
return 0;
}
void *memcpy2(void *dest, const void *ori, int size){
assert(dest!=NULL && ori !=NULL);
char *dest2= (char *) dest;
char *ori2= (char *) ori;
for(int i=0; i< size; i++){
*dest2++ = *ori2++;
}
return dest2;
}

自訂一個strcpy (c++)



#include <iostream>
using namespace std;

char *strcpy2(char *dest, const char *ori);
int main(void){
char tmp[] = "adfadfaf";
strcpy2(tmp, "hello world");
cout<<tmp;
return 0;
}
char *strcpy2(char *dest, const char *ori){
assert(dest!=NULL && ori !=NULL);
char *addr= dest;
while((*dest++ = *ori++)!='\0');
return addr;
}