전전컴/C++에 해당되는 글 64건

글

Realization of combination on C++

전전컴/C++ 2014. 1. 15. 14:42

the following source code make many recursive overheads.

We can see the redundancy happened.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int combination(int n, int r);
 
void main(){
    cout<<combination(7,3);
}
 
int combination(int n, int r){
 
    if( (n==r) || (r ==0) ) return 1;
    
    return combination(n-1,r-1) + combination(n-1,r);
}
 


In order to reduce these redundancy, we can use previous value which was calculated before.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
const int MAX = 20;
 
int combination(int n, int r);
 
void main(){
    cout<<combination(7,3);
}
 
int combination(int n, int r){
    static int memo[MAX][MAX];
 
    if( memo[n][r] >0 ) return memo[n][r];
 
    if( (n==r) || (r ==0) ) return memo[n][r] = 1;;
    
    return memo[n][r] = combination(n-1,r-1) + combination(n-1,r);
}
 


The static int value are initialized to 0;



저작자표시

설정

,

트랙백

댓글

글

소켓프로그래밍 예제

전전컴/C++ 2014. 1. 15. 01:02

server이다

cmd에서 파일이름 9190으로 먼저 실행후 대기한다

Colored By Color Scripter™

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <winsock2.h>
#pragma comment(lib, "ws2_32.lib")
using namespace std;
 
void ErrorHandling(char* message);
 
void main(int argc, char* argv[]){
    WSADATA wsaData;
    SOCKET hServSock, hClntSock;
    SOCKADDR_IN servAddr, clntAddr;
 
    int szClntAddr;
    char* message= "Hello World!";
    if(argc != 2){
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }
    if(WSAStartup(MAKEWORD(2,2), &wsaData)!=0)
        ErrorHandling("WSAStartup() error!");
 
    hServSock = socket(PF_INET, SOCK_STREAM, 0 );
    if(hServSock == INVALID_SOCKET)
        ErrorHandling("socket() error");
 
    memset(&servAddr, 0 , sizeof(servAddr));
    servAddr.sin_family = AF_INET;
    servAddr.sin_addr.s_addr =inet_addr("127.0.0.1");
    //servAddr.sin_addr.S_un.S_addr = htonl(INADDR_ANY);
    //servAddr.sin_addr.S_un.S_addr =inet_addr("127.0.0.1");
 
    //.sin_addr.s_addr=inet_addr("127.0.0.1");
    servAddr.sin_port = htons(atoi(argv[1]));
 
    if( bind( hServSock, (SOCKADDR*)&servAddr, sizeof(servAddr) ) == SOCKET_ERROR  )
        ErrorHandling("bind() error");
 
    if(listen(hServSock, 5) ==SOCKET_ERROR)
        ErrorHandling("listen() error");
 
    szClntAddr = sizeof(clntAddr);
    hClntSock = accept(hServSock, (SOCKADDR*)&clntAddr, &szClntAddr);
    if(hClntSock == INVALID_SOCKET){
        ErrorHandling("accept() error");
    }
 
    send(hClntSock, message, sizeof(message), 0 );
    closesocket(hClntSock);
    closesocket(hServSock);
    WSACleanup();
 
 
 
}
 
void ErrorHandling(char* message){
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}


아래는 client이다 

cmd에서 파일이름 127.0.0.2 9190으로 대기한다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <winsock2.h>
#pragma comment(lib, "ws2_32.lib")
 
using namespace std;
 
void ErrorHandling(char* message);
 
int main(int argc, char* argv[])
{
    WSADATA wsaData;
    SOCKET hSocket;
    SOCKADDR_IN servAddr;
 
    char message[30];
    int strLen;
    if(argc!=3){
        printf("Usage : %s <IP> <port>\n", argv[0]);
        exit(1);
    }
 
    if(WSAStartup(MAKEWORD(2,2), &wsaData) !=0 )
        ErrorHandling("WSAStartup() error!");
 
 
    hSocket = socket(PF_INET, SOCK_STREAM, 0);
    if(hSocket == INVALID_SOCKET)
        ErrorHandling("socket() error");
 
    memset(&servAddr, 0, sizeof(servAddr));
    
    servAddr.sin_family = AF_INET;
    servAddr.sin_addr.S_un.S_addr = inet_addr(argv[1]);
    servAddr.sin_port = htons(atoi(argv[2]));
 
    if(connect(hSocket, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR)
        ErrorHandling("connet() error!");
 
    strLen = recv(hSocket, message, sizeof(message),0);
    if(strLen == -1)
        ErrorHandling("read() error!");
 
    printf("Message from server : %s \n", message);
    closesocket(hSocket);
    WSACleanup();
    
    return 0;
}
 
 
void ErrorHandling(char* message){
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}


저작자표시

설정

,

트랙백

댓글

글

자료구조설계과제

전전컴/C++ 2013. 12. 3. 00:52

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <ctime>
using namespace std;
 
void swap(int& a, int& b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}
 
class Sort{
    int NumOfElements;
    int* elements;
    void makeNum(int Num){
        cout<<"생성된 데이터 :";
        for(int i = 0; i<Num; i++){
            *(elements+i)=rand()%100;
            cout<<*(elements+i)<< ' ';
        }
        cout<<endl;
    }
public:
    Sort(int NumOfElements){
        this->NumOfElements = NumOfElements;
        elements = new int[NumOfElements];
        makeNum(NumOfElements);
    }
    Sort(){
        cout<<"자료의 개수를 입력해주세요:";
        cin>>NumOfElements;
        elements = new int[NumOfElements];
        makeNum(NumOfElements);
    }
    void display(){
        for(int i = 0; i<NumOfElements; i++){
            cout<<*(elements+i)<< ' ';
        }
        cout<<endl;
    }
    ~Sort(){
        if(elements != NULL) delete[] elements;
        elements = NULL;
    }
    void smallest_select(){
        int smallest = elements[0];
        int i;
 
        for(i = 1; i<NumOfElements; i++){
            if( elements[i] < smallest ) smallest = elements[i];
        }
 
        cout<<"가장 작은 값은"<<smallest<<"입니다"<<endl;
    }
 
    void large_select(){
        if(elements == NULL){
            cout<<"자료가 없습니다"; 
            return;
        }
 
        int largest=0;
        int temp = 0;
        int i,j;
        for(i = NumOfElements-1; i>=0; i--){  //자료형이 0번 방부터 시작함을 유의
            largest=i;
            for(j = i-1 ; j>=0; j--){
                if(elements[j] > elements[largest]) largest=j;
            }
            if(i != largest ){
                swap(elements[i], elements[largest]);
                cout<<i<<"번째 자료 "<<elements[i]<<"와 "<<largest<<"번째 데이터"<<elements[largest]<<" Exchange"<<endl;
                display();
            }
        }
    }
 
    void quick_sort(){
        _quick_sort(0, NumOfElements-1);
 
    }
 
    void _quick_sort(int _left, int _right){
 
        if( _left >= _right ) return;
 
 
        int pivot = elements[_left];
        //cout<<"Pivot"<<pivot<<endl;
        display();
        int left_index = _left, right_index=_right+1;
        
        do{
            do{
                left_index++;
                cout<<"left_index:"<<left_index<<"  left_index 값:"<<elements[left_index]<<endl;
            }while( (elements[left_index] < pivot)&&(left_index <= _right));
 
            do{
                right_index--;
                cout<<"right_index:"<<right_index<<"  right_index 값:"<<elements[right_index]<<endl;
            }while( (elements[right_index] > pivot)&&(right_index >= _left+1) );
            
            if(left_index<right_index){
                cout<<"피벗보다 큰"<<elements[left_index]<<"값과 피벗보다 작은"<<elements[right_index]<<"값을 교환"<<endl;
                swap(elements[left_index],elements[right_index]); 
            }
            //교차점근처서 바꾸고 나서, 다시 값이 바뀔수 있다
            //위의 left_index++와 right_index--를 거쳐야 교차를 한다.
            //그런데 이 검사를 밑 while에서 하므로 if문으로 확인해줘야한다.
            
        }while(left_index<right_index);
    
        cout<<"[Pivot]:"<<elements[_left]<<"와"<<elements[right_index]<<"를 교환"<<endl;
        swap(elements[_left],elements[right_index]); //피벗과 교환
        display();
 
        if(_left<right_index-1){
        cout<<"재귀함수 호출... 인덱스"<<_left<<"에서 인덱스"<<right_index-1<<"까지 재귀함수 호출"<<endl;
        _quick_sort(_left, right_index-1);
        }
 
        if(right_index+1<_right){
        cout<<"재귀함수 호출... 인덱스"<<right_index+1<<"에서 인덱스"<<_right<<"까지 재귀함수 호출"<<endl;
        _quick_sort(right_index+1, _right);
        }
    }//void _quick_sort
};
void main(){
    srand(time(0));
    
    Sort* s = new Sort;
    
    //s->large_select();
    s->quick_sort();
 
    cout<<"====================최종 결과:======================="<<endl;
    s->display();
    delete s;1
 
}


저작자표시

설정

,

트랙백

댓글

글

BST (Binary Search Tree)

전전컴/C++ 2013. 11. 3. 15:33





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <string>
using namespace std;
 
typedef struct tTreeNode{
    struct tTreeNode *left, *right;
    int data;
}TreeNode;
 
TreeNode* createNode(TreeNode* left, int root, TreeNode* right){
    TreeNode *p = (TreeNode*)malloc(sizeof(TreeNode));
    
    p->left = left;
    p->right = right;
    p->data = root;
 
    return p;
}
 
void destroyTree(TreeNode* p){
    if( p == NULL) return;
 
    destroyTree(p->left);
    destroyTree(p->right);
    cout<<"node remove"<<endl;
    free(p);
}
 
void preorder(TreeNode* root){
    if(root == NULL) return;
 
    cout<<root->data;
    preorder(root->left);
    preorder(root->right);
}
 
void postorder(TreeNode* root){
    if(root == NULL) return;
    
    postorder(root->left);
    postorder(root->right);
    cout<<root->data;
}
 
void inorder(TreeNode* root){
    if(root == NULL ) return;
 
    inorder(root->left);
    cout<<root->data;
    inorder(root->right);
 
}
 
void insertNode(TreeNode* root, int item){
    
}
 
TreeNode* addTree(TreeNode* root, TreeNode* NewNode){
    if( root == NULL) return NewNode;
 
    if( root->data > NewNode->data ){
        root->left = addTree(root->left, NewNode);
    }else{//root->data < newNode->data;
        root->right = addTree(root->right , NewNode);
    }
 
    return root;
}
 
void main(){
    TreeNode* root = createNode(NULL,7,NULL);
    
    TreeNode* NewNode = createNode(NULL, 5, NULL);
    TreeNode* NewNode2 = createNode(NULL,3,NULL);
    TreeNode* NewNode3 = createNode(NULL,8,NULL);
    TreeNode* NewNode4 = createNode(NULL,10,NULL);
    
    
    root = addTree(root ,NewNode);
    root = addTree(root ,NewNode2);
    root = addTree(root ,NewNode3);
    root = addTree(root ,NewNode4);
 
    cout<<"inorder";
    inorder(root);
    cout<<endl;
    cout<<"preorder";
    preorder(root);
    
    
    cout<<endl;
    destroyTree(root);
 
}


저작자표시

설정

,

트랙백

댓글

글

tree2

전전컴/C++ 2013. 10. 28. 23:46





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string>
using namespace std;
 
typedef struct tTreeNode{
    struct tTreeNode *left, *right;
    char data;
}TreeNode;
 
TreeNode* createNode(TreeNode* left, char root, TreeNode* right){
    TreeNode *p = (TreeNode*)malloc(sizeof(TreeNode));
    
    p->left = left;
    p->right = right;
    p->data = root;
 
    return p;
}
 
void destroyTree(TreeNode* p){
    if( p == NULL) return;
 
    destroyTree(p->left);
    destroyTree(p->right);
    cout<<"node remove"<<endl;
    free(p);
}
 
void preorder(TreeNode* root){
    if(root == NULL) return;
 
    cout<<root->data;
    preorder(root->left);
    preorder(root->right);
}
 
void postorder(TreeNode* root){
    if(root == NULL) return;
    
    postorder(root->left);
    postorder(root->right);
    cout<<root->data;
}
 
void inorder(TreeNode* root){
    if(root == NULL ) return;
 
    inorder(root->left);
    cout<<root->data;
    inorder(root->right);
 
}
 
void main(){
    TreeNode* a = createNode(NULL, 'a', NULL);
    TreeNode* b = createNode(NULL, 'b', NULL);
    TreeNode* c = createNode(NULL, 'c', NULL);
    TreeNode* d = createNode(NULL, 'd', NULL);
 
    TreeNode* plus1 = createNode(b, '+', c);
    TreeNode* multi = createNode(a, '*', plus1);
    TreeNode* plus2= createNode(multi, '+', d);
    
    cout<<"Preorder========"<<endl;
    preorder(plus2);
    cout<<endl;
    cout<<"Postorder======="<<endl;
    postorder(plus2);
    cout<<endl;
    cout<<"Inorder========="<<endl;
    inorder(plus2);
    cout<<endl;
 
 
    destroyTree(plus2);
 
}


저작자표시

설정

,

트랙백

댓글

1 2 3 4 ··· 13
지역로그| 태그| 방명록| 관리자| 쓰기
워라's Blog is powered by Daum & Tattertools / Designed by Tistory

티스토리툴바