프로그래밍 공부노트

재귀를 이용한 하노이의 탑 시각화(windows와 linux에서만 컴파일 가능)

-sleep 함수 사용에 대해..

windows에서는 windows.h헤더 내에 선언된 Sleep함수(단위 ms)를 이용.

Linux에서는,

linux의 unistd.h에 존재하는 sleep 함수는 최소 대기시간이 1초이다. 만약 1초보다 짧은 시간 동안 프로그램을 재우고 싶다면, 다른 함수가 필요하다.

usleep함수는 microsecond 단위로 대기할 수 있지만, 더이상 잘 사용되지 않는다.

time.h의 nanosleep(시간단위는 nanosecond)을 사용했다(http://stackoverflow.com/a/7684399).

C언어에서 공식적으로 2진수 표현 방법을 지원하지 않아서 직접 만들었다.

void print_int_to_bin 함수는 unsigned int를 인자로 받아 그것을 2진수 형태로 변환해서, 8자리마다 한 칸씩 띄워서 출력한다.

#include <stdio.h>

void print_char_to_bin(unsigned char ch)
{
    int a;
    _Bool b;
    for (a = 0; a < 8; a++) {
        b = (ch & 1 << 8 - a - 1)? 1 : 0;
        printf("%d", b);
    }
}

void print_int_to_bin(unsigned int i)
{
    unsigned char int8;
    int len = sizeof(int);
    int a;
    printf("in bin: ");

    for(a = 0; a < len; a++)
    {
        int8 = i >> (len - a - 1) * 8 & 0xFF;
        print_char_to_bin(int8);
        printf(" ");
    }
    printf("\n");
}


int main(void)
{
    print_int_to_bin(0xffffffff);
    return 0;
}

/**** stack.h ****/
#include <stdbool.h>

void make_empty(void);       // 스택 내의 모든 노드를 삭제
bool is_empty(void)  ;       // 스택이 비어있는지 여부를 반환함
void push(int i);            // 정수 i를 스택의 맨 위에 push
int pop(void);               // 스택의 맨 위에 있는 정수를 pop


/**** main.c ****/
#include <stdio.h>
#include "stack.h"

int read_number(void);
int main(void) {
	int i;
	printf("연결 리스트로 스택 짜기\n"); 
	do {
		i = read_number();
		push(i);
	} while (i!=0);
	for(;;)
		printf("%d ", pop());
}

int read_number(void) {
	int i;
	printf("숫자 입력(0: 종료): ");
	scanf("%d", &i);
	return i;
}


/**** stack.c ****/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>


struct node {
	int value;
	struct node *next;
};
/* external variables */
struct node *top = NULL;

void make_empty(void) {
	struct node *prev = NULL;
	while (p!= NULL) {
		prev = top;
		top = top->next;
		free(prev);
	}
}

bool is_empty(void) {
	return (top == NULL);
}

void stack_underflow(void) {
	printf("stack is empty.\n");
	exit(EXIT_FAILURE);
}

void stack_overflow(void) {
	printf("cannot allocate memory for new member in stack.\n");
	exit(EXIT_FAILURE);
}

bool push(int i) {
	struct node *new_top;
	new_top = malloc(sizeof(struct node));
	if (new_top == NULL)
		return false;
	new_top->value = i;
	new_top->next = top;
	top = new_top;
	return true;
}

int pop(void) {
	struct node *temp;
	int pop_value;
	if (is_empty())
		stack_underflow();
	temp = top;
	top = top->next;
	pop_value = temp->value;
	free(temp);
	return pop_value;
}

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define STACK_SIZE 100

/**** STACK ****/

/* external variables */
int contents[STACK_SIZE];
int *top_ptr = &contents[0];

void make_empty(void) {
	*top_ptr = 0;
}

bool is_empty(void) {
	return top_ptr == &contents[0];
}

bool is_full(void) {
	return top_ptr == &contents[STACK_SIZE];
}

void stack_underflow(void) {
	printf("stack underflow.\n");
	exit(EXIT_FAILURE);
}

void stack_overflow(void) {
	printf("stack overflow.\n");
	exit(EXIT_FAILURE);
}

void push(int i) {
	if (is_full())
		stack_overflow();
	else
		*top_ptr++ = i;
}

int pop(void) {
	if (is_empty())
		stack_underflow();
	else
		return *--top_ptr;
}

최대공약수(gcd, great common divisor)를 구하는 함수이다. 이 방법은 유클리드의 알고리즘(Euclid's algorithm으로 알려져 있다. 내용은 다음과 같다.

m과 n을 각각 양의 정수라고 하자(m이 n보다 크거나 같다). 만약 n이 0이면, 멈추고, m이 최대공약수가 된다.

그렇지 않다면, m을 n으로 나눈 나머지를 n에 저장하고, 원래 n의 값을 m에 저장한다. 이것을 n이 0이 될 때까지 반복한다.

int get_gcd(int m, int n) {

int temp;

if (m < n) {

temp = m;

m = n;

n = temp;

}

while (n > 0) {

temp = m%n;

m = n;

n = temp;

}

return m;

}

한편 두 수의 최대공약수를 구하면 최소공배수(lcm, least common multiple)도 쉽게 구할 수 있다. 

m * n = gcd(m, n) * lcm(m, n) 이므로, lcm(m, n) = m * n / gcd(m, n)이다.

int get_lcm(int m, int n) {

int gcd = get_gcd(m, n);

return m * n / gcd;

}

주사위 2개를 '시행회수' 만큼 굴린다.

각각의 주사위에서 1부터 6까지 값이 나온 빈도와 두 주사위의 합의 빈도를 표시.

참고로 두 주사위의 합에 대한 확률은 다음과 같다.

합: 확률(퍼센트)    확률(분수)

2 : 2.78    1/36

3 : 5.56    2/36

4 : 8.33    3/36

5 : 11.11    4/36

6 : 13.89    5/36

7 : 16.67    6/36

8 : 13.89    5/36

9 : 11.11    4/36

10 : 8.33    3/36

11 : 5.56    2/36

12 : 2.78    1/36