하노이탑 재귀 수도코드
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, 1, 2, 3); } 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, 0, sizeof(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
,
