* 하노이의 탑
이번주 기초프로그래밍 과제가 하노이 탑이더군요. 그래서 가장 먼저 하게 되었습니다.
분명 저번에 영기선배님이 하노이탑 코드를 보여주셔서 해석하느라 뚫어지게 쳐다봤었는데도 정작 과제를 하려니 내가 코드를 쳐다봤다는 사실밖에는 기억이 나지 않았습니다;; 재귀함수 안에 재귀호출을 두 번 한다는 정도??밖에 기억이 안나더군요.
그래서 하노이 탑의 알고리즘을 알고자 하노이 탑 플래시 게임을 계속 해보았습니다. 게임을 하다보니 새싹 때 보았던 기둥을 바꾸는 알고리즘이 이해가 되더군요. 암튼 그렇게 간간히 종이에 끼적이면서 생각하다가 프로그램을 완성하였습니다.
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int first_stick = 1, second_stick = 2, third_stick = 3;
void hanoi(int start, int middle, int goal, int num){
if (num == 1)
printf("%d -> %d\n", start, goal);
else{
hanoi(start, goal, middle, num - 1);
printf("%d -> %d\n", start, goal);
hanoi(middle, start, goal, num - 1);
}
}
int main()
{
int n;
printf("고리의 갯수를 입력하세요 : ");
scanf("%d", &n);
hanoi(first_stick, second_stick, third_stick, n);
printf("\t20141718 이지수\n");
system("pause");
return 0;
}
* 큐 구현
동적할당을 이용해서 순환 큐를 만들었습니다.
처음에 예외처리를 if-else 때려넣으면서 무식하게 하다가 수많은 버그를 양산해서 머리가 폭발하는 줄 알았습니다.
그래서 당분간 큐를 버리고ㅋㅋ하노이탑에 집중을 하다가 오늘 정신이 비교적 맑아서 도전했고 3시간 걸려서 다 풀었습니다.
좋은 알고리즘이란 예외를 최대한 적게 만드는 것이라는 사실을 요즘들어 깨닫고 있습니다.
맨 처음에 프로그램을 작성했을 때는 큐 크기가 2 이상일 때는 되고 1일 때는 아예 안 되길래 큐 크기를 1로 입력받을 때를 대비한 예외함수까지 만들었었는데ㅋㅋ오늘 작성한 프로그램은 큐 크기를 1로 입력받을 때도 잘 처리해주거든요.
어쨌든 덕분에 포인터에 대해 더 잘 이해하게 된 것 같습니다. 그리고 반복문을 for문을 주로 썼는데 for문은 안에 있는 내용을 1번은 꼭 수행하기 때문에 예상치 못한 버그를 만들 수 있다는 것을 깨달았네요. while도 사랑해주어야겠습니다.
#include <stdio.h>
#include <stdlib.h>
int front_count = 0, rear_count = 0, Qsize, n;
int *front, *rear, *queue;
int *push(int* push_ptr){
printf("enter a value to push : ");
scanf("%d", push_ptr);
if(rear_count%Qsize == 0)
return queue;
else
return ++push_ptr;
}
int *pop(int* pop_ptr){
if(front_count%Qsize == 0)
return queue;
else
return ++pop_ptr;
}
void print_queue(){
int a, b, c, i, j;
if(rear_count - front_count == Qsize){
for(i = 0; i < Qsize ; i++)
printf(" %d ", *(queue + i));
}
else if(rear_count == front_count){
for(j = 0; j < Qsize ; j++)
printf(" _ ");
}
else{
int rear_num = rear_count%Qsize;
int front_num = front_count%Qsize;
if(rear < front){
a = 0, b = rear_num, c = front_num;
while( a != rear_num ){
printf(" %d ", *(queue + a));
a++;
}
while( b != front_num ){
printf(" _ ");
b++;
}
while( c != Qsize ){
printf(" %d ", *(queue + c));
c++;
}
}
else{
a = 0, b = front_num, c = rear_num;
while( a != front_num ){
printf(" _ ");
a++;
}
while( b != rear_num ){
printf(" %d ", *(queue + b));
b++;
}
while( c != Qsize){
printf(" _ ");
c++;
}
}
}
printf("\n");
}
int main(){
printf("enter queue size : ");
scanf("%d", &Qsize);
queue = (int *)malloc(sizeof(int)*Qsize);
front = queue;
rear = queue;
while(1){
printf("select (1.push 2.pop 3.print queue 4.end) : ");
scanf("%d", &n);
switch(n){
case 1:
if(rear_count - front_count == Qsize){
puts("the queue is full");
break;
}
rear_count++;
rear = push(rear);
break;
case 2:
if(rear_count == front_count){
puts("the queue is empty");
break;
}
front_count++;
front = pop(front);
break;
case 3:
print_queue();
break;
case 4:
puts("program is closed");
free(queue);
system("pause");
return 0;
default:
puts("please enter a valid number");
}
}
}