'하노이탑 재귀 수도'에 해당하는 글 1건

하노이탑 재귀 수도코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// hanoi 함수 : N개의 원판을 A에서 C로 옮긴다. B를 사용할 수 있다.
hanoi(N, A, B, C) {
   if( N == 1) {
 
      // 원판을 A에서 C로 옮긴다. 탈출 조건으로 작용한다.
      print "<1> 원판을 <A>에서 <C>로 옮긴다."
      move(from, to);    
 
   } else {
 
      //1. [1:N-1] 원판을 A에서 B로 옮긴다.
      hanoi(N-1, A, C, B)
 
      //2. [N] 원판을 A에서 C로 옮긴다.
      print "<N> 원판을 <A>에서 <C>로 옮긴다."
      move(from, to); 
      //3. [1:N-1] 원판을 B에서 C로 옮긴다.
      hanoi(N-1, B, A, C)
   }
}
 
cs



하노이탑 반복 소스코드 


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
        #include "stdio.h"
         
        /* 원반이움직이는것을출력한다. */
        void Move(int n, int from, int to);
         
        /* 실제재귀함수*/
        void Hanoi(int n, int from, int by, int to);
         
        /* 스택관련함수및변수들*/
        #define MAX 100
        int Stack[MAX];
        int sp;
        void InitStack();
        void Push(int data);
        int Pop();
        int IsEmpty();
         
         
        int main()
        {
                int i = 0;
         
                printf("\n0 이하의값을입력하시면게임을끝냅니다.\n");
                while ( 1 )
                {
                       printf("\n하노이탑의높이를입력하세요: ");
                       scanf("%d"&i);
         
                       if ( i <= 0 )
                               break;
         
                       /* i 개의원반을기둥에서기둥으로옮김*/
                       Hanoi(i, 123);
                }
         
                return 0;
        }
         
        void Move(int n, int from, int to)
        {
                printf("Move %d from %d to %d\n", n, from, to);
        }
         
        void Hanoi(int n, int from, int by, int to)
        {
                int bContinue = 1;
                InitStack();
         
                while ( bContinue )
                {
                       while ( n > 1 )
                       {
                               Push(to);
                               Push(by);
                               Push(from);
                               Push(n);
                               n--;
                               Push(to);
                               to = by;
                               by = Pop();
                       }
                       Move(n, from, to);
                       if ( !IsEmpty() )
                       {
                               n = Pop();
                               from = Pop();
                               by = Pop();
                               to = Pop();
                               Move(n, from, to);
                               n--;
                               Push(from);
                               from = by;
                               by = Pop();
                       }
                       else
                               bContinue = 0;
                }
        }
         
        void InitStack()
        {
                sp = -1;
        }
         
        void Push(int data)
        {
                if ( sp >= MAX - 1 )
                {
                       printf("Stack overflow!!!\n");
                       return;
                }
         
                Stack[++sp] = data;
        }
         
        int Pop()
        {
                if ( sp < 0 )
                {
                       printf("Stack is already empty!!!\n");
                       return 0;
                }
         
                return Stack[sp--];
        }
         
        int IsEmpty()
        {
                if ( sp < 0 )
                       return 1;
                else
                       return 0;
        }
cs

'해시(Hash) 탐색 알고리즘 구현
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include "stdafx.h"
 
#define MAX 10
 
void store(int db[2][MAX]);
int search(int db[2][MAX], int num);
void menu(int *flag, int db[2][MAX]);
void remove(int db[2][MAX]);
void showDb(int db[2][MAX]);
 
void main()
{
    int db[2][MAX];
    int flag = 0;
    memset(db, 0sizeof(db));
 
    while (1) {
        menu(&flag, db);
        switch (flag) {
        case 0:
            printf("프로그램을 종료합니다.\n");
            return;
        case 1:
            store(db);
            break;
        case 2:
            int num;
            printf("\n검색할 숫자를 넣어주세요 : ");
            scanf_s("%d"&num);
            num = search(db, num);
            break;
        case 3:
            remove(db);
            break;
        case 4:
            showDb(db);
            break;
        default:
            if (flag>3 || flag<0)
            {
                printf("0~3 사이의 정수를 입력하세요.\n");
            }
        }
        //system("cls"); 
    }
 
 
    return;
}
void menu(int * flag, int db[2][MAX])
{
    showDb(db);
    printf("\n\n\t1. 저장 2. 검색 3.삭제 4.DB 상태 보기 0. 종료\t");
    printf("?");
    scanf_s("%d", flag);
}
void store(int db[2][MAX])
{
    int index = 0;
    int cnt = 0;
    int num;
    printf("\n저장할 숫자를 넣어주세요 : ");
    scanf_s("%d"&num);
    index = num%MAX;
 
    while (1)
    {
        if (cnt == MAX) {
            printf("\n\n\n★★★★★ DB 가 가득 찼습니다. ★★★★★\n");
            printf("\n\n\n★★★★★ DB 가 가득 찼습니다. ★★★★★\n");
            printf("\n\n\n★★★★★ DB 가 가득 찼습니다. ★★★★★\n");
            break;
        }
        if (db[0][index] == 0)//비어있으면
        {
            db[0][index] = num;
            if (cnt == 0)
            {
                db[1][index] = 1;//한번에 자기자리에 들어갔는지 여부 표시
            }
            break;
        }
        else if (db[0][index] != 0)//비어있으면
        {
            cnt++;    index++;
            if (index == MAX)index = 0;//circular search
        }
    }
}
 
void remove(int db[2][MAX])
{
    int index = 0;
    int cnt = 0;
    int num;
    int tmpIndex;
    //int tmp;
    printf("\n삭제할 숫자를 넣어주세요 : ");
    scanf_s("%d"&num);
    index = search(db, num);
    if (index)//결과가 있으면
    {
        index--;//search의 결과값이 1크게 들어오므로        
        tmpIndex = index;
 
        db[0][index] = 0;//삭제
        db[1][index] = 0;
 
        index++;
        while (!db[0][index] == 0)//빈자리가 나올떄 까지 검색
        {
            if (db[1][index] == 1)
            {
                index++;
                if (index == MAX)index = 0;
                continue;
            }
            else if (db[0][index] != 0 && db[1][index] == 0)//저장된 자료가 있고 자기 자리가 아니면
            {
                db[0][tmpIndex] = db[0][index];
                if (db[0][index] % MAX == tmpIndex) { db[1][tmpIndex] = 1; }//자기자리로 온것인지 체크
                else { db[1][tmpIndex] = 0; }
                db[0][index] = 0; db[1][index] = 0;//이동한자리 지우기
                tmpIndex = index;//다음 이동 index
            }
            index++;
            if (index == MAX)index = 0;
        }
 
 
    }
    else
    {
        return;
    }
}
 
 
 
 
int search(int db[2][MAX], int num)
{
    int index = 0;
    int cnt = 0;
    index = num%MAX;
    while (1)
    {
        if (cnt == MAX) { printf("\n\n\n★★★★★ %d 가 DB에 없습니다.. ★★★★★\n", num); return 0; }
        if (db[0][index] != num)//찾지 못했을경우
        {
            index++; cnt++;
            if (index == MAX)index = 0;//circular search
            continue;
        }
        else if (db[0][index] == num)//찾았을 경우
        {
            printf("\n\n\n★ %d 는 %2d 방에 저장되어있습니다.. ★\n", num, index + 1); return index + 1;
        }
 
    }
    //return 0;
}
void showDb(int db[2][MAX])
{
 
    printf("\n\n\t 현재 DB 의 상태입니다.\n\n");
    for (int i = 0; i<MAX; i++)
    {
        printf("%2d |", i + 1);
    }
    printf("\n");
    for (int i = 0; i<MAX; i++)
    {
        printf("%3d ", db[0][i]);
    }
}
 
cs


합병정렬 수도코드


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
void mergesort(int n, keytype S[]){
   if(n>1){
      int h = n / 2, m = n - h;
      keytype U[1..h], V[1..m];
      copy S[1] through S[h] to U[1] through U[h];
      copy S[h+1] through S[n] to V[1] through V[m];
      mergesort(h, U);
      mergesort(m, V);
      merge(h, m, U, V, S);
   }
}
 
void merge(int h, int m, keytype U[], keytype V[], keytype S[]){
   index I, j, k;
   
   i = 1; j = 1; k = 1;
   while(i <= h && j <= m){
      if(U[i] < V[j]){
         S[k] = U[i];
         i++;
      }
      else{
         S[k] = V[j];
         j++;
      }
      k++;
   }
 
   if(i > h)
      copy V[j] through V[m] to S[k] through S[h+m];
   else
      copy U[i] through U[h] to S[k] through S[h+m];
cs



WRITTEN BY
내가달이다

,