반응형

1. There are three towers and 64 disks of different diameters placed on the first tower. The disks are in order of decreasing diameter as one scans up the tower. Monks were reputedly supposed to move the disk from tower 1 to tower 3 obeying the rules :




(a) Only one disk can be moved at any time.

(b) No disk can be placed on top of a disk with a smaller diameter.

Write a recursive function that prints out the sequence of moves needed to accomplish this task.




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
/*****************************************************************
num : 원판의 갯수 from : 옮기는 판이 원래 있던 기둥
to : 옮기는 판이 옮겨질 기둥  disk : 사용자가 입력한 원판의 개수
pass_stop : from에 있던 (n-1)개의 원판이 to로 가기 위해 경유하는 기둥 
count : 움직인 횟수
기둥은 총 3개가 있는데 각 기둥을 정수 1,2,3으로 표현하였다.
****************************************************************/
 
#include <stdio.h>
void Hanoi(int num, int from, int to);
int count = 0;
int main(void)
{
    int disk = 0; 
    printf("원판 수를 입력하세요: ");
    scanf("%d", &disk); // 옮길 원판 개수 입력
    Hanoi(disk, 1, 3); // 시작 위치 : 기둥1 도착 위치 : 기둥3
    printf("총 움직인 횟수는 %d회 입니다.\n", count);
    return 0;
}
void Hanoi(int num, int from, int to) 
{
    int pass_stop = 2; // 각 기둥을 1,2,3 이라고 정함, 1+2+3=6
    if (num <= 1)
    {
        printf("%d번째 원판을 %d에서 %d로 옮겼습니다.\n", num, from, to);
        count++;
    }
    else {
        pass_stop = 6 - from - to;
        Hanoi(num - 1, from, pass_stop); // (n-1)개를 from에서 pass_stop으로 옮긴다.
        printf("%d번째 원판을 %d에서 %d로 옮겼습니다.\n", num, from, to);
        count++;
        Hanoi(num - 1, pass_stop, to); // (n-1)개를 pass_stop에서 to 로 옮긴다.
    }
}
cs






2. Write the iterative(반복의) (Program 2-1) and recursive(회귀의) (Program 2-2) binary search function and measure the worst case performance of both functions (using Program 1.25), and analyze average case time complexity of binary search algorithm.


*프로그램 1.25에 써있는 numtime 대로 하면 cpu 성능이 너무 좋아 시간이 제대로 나오지 않으므로 곱하기 100씩 한 수를 넣어주었다.





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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COMPARE(mid,searchnum)  (((mid)<(searchnum)) ? (-1) : (((mid)>(searchnum)) ? (1) : (0)))  //미들값과 찾는값의 크기를 비교하여 해당 값 반환
/* mid<searchnum 이면 -1 반환, mid>searchnum이면 1 반환, mid=searchnum이면 1 반환*/
#define MAX_SIZE 1001 //상수 MAX_SIZE는 1001
#define ITERATIONS 16 //상수 ITERATIONS는 16
int binsearch_rec(int list[], int searchnum, int left, int right);
int binsearch_itr(int list[], int searchnum, int left, int right);
int main(void)
{
    int i,j,position;  //int형 변수 i,j,positon 선언
    int list[MAX_SIZE]; //int형 배열 list 선언, 배열의 크기는 MAX_SIZE=1001
    int sizelist[]={0,10,20,30,40,50,60,70,80,90,100,200,400,600,800,1000}; //이진탐색을 시행할 크기
    int numtimes[]={3000000,1200000,600000,500000,400000,400000,400000,300000,300000,200000,200000,100000,50000,50000,50000,20000}; // 이진탐색을 돌릴 횟수
    clock_t start, stop; //clock_t는 time.h에서 정의되어있는데 long 형과 같다. start, stop 변수 선언
    double duration, total; //double 형 변수 duration, total 선언
    for(i=0;i<MAX_SIZE;i++)
    {
        list[i]=i; //각 배열의 원소의 값을 번호로 초기화
    }
        printf("=====================ITERATIVE=====================\n");
        printf("sizelist[i]  numtimes[i]  stop-start     total     duration     positon\n");
    for(i=0;i<ITERATIONS;i++) 
    {
        start=clock(); //start에 프로그램이 시작될 때부터 지난 틱수 저장
        for(j=0;j<numtimes[i];j++) // j=0부터 numtimes[i] 미만까지 반복
        {
            position=binsearch_itr(list,sizelist[i]+1,0,sizelist[i]); //positon에 binseasrch_itr함수의 반환값 저장 최악의 경우로 없는 숫자를 찾는다.
                                                                    //예를들어 sizelist[2]면 searchnum은 0에서 10사이에서 11을 찾는 것이다. 리턴은 -1일 것이다.
        }
        stop=clock(); //stop에 프로그램이 시작될 때부터 지난 틱수 저장
        total=((double)(stop-start))/CLOCKS_PER_SEC; //CLOCKS_PER_SEC는 초당 클락수이다.1000으로 정의되어 있다. stop-start=사이의 클락수이므로 연산을 하면 시간(초)가 반환된다.
        duration=(total/numtimes[i]); //total을 numtimes[i]로 나눈 값
        printf("%11d %11d %11d %11f %11f %11d\n",sizelist[i],numtimes[i],(int)(stop-start),total,duration,position); //화면에 각각의 값을 11자리씩 출력
        list[sizelist[i]]=sizelist[i]; //reset value 라고 써있는데 왜 있는지 잘 모르겠다.
    }
    printf("=====================RECURSIVE=====================\n");
    printf("sizelist[i]  numtimes[i]  stop-start     total     duration     positon\n");
    for(i=0;i<ITERATIONS;i++)
    {
        start=clock();    //start에 프로그램이 시작될 때부터 지난 틱수 저장
        for(j=0;j<numtimes[i];j++)// j=0부터 numtimes[i] 미만까지 반복
        {
            position=binsearch_rec(list,sizelist[i]+1,0,sizelist[i]); //positon에 binseasrch_rec함수의 반환값 저장 최악의 경우로 없는 숫자를 찾는다.
                                                                    //예를들어 sizelist[2]면 searchnum은 0에서 10사이에서 11을 찾는 것이다. 리턴은 -1일 것이다.
        }
        stop=clock(); //stop에 프로그램이 시작될 때부터 지난 틱수 저장
        total=((double)(stop-start))/CLOCKS_PER_SEC; //CLOCKS_PER_SEC는 초당 클락수이다.1000으로 정의되어 있다. stop-start=사이의 클락수이므로 연산을 하면 시간(초)가 반환된다.
        duration=(total/numtimes[i]); //total을 numtimes[i]로 나눈 값
        printf("%11d %11d %11d %11f %11f %11d\n",sizelist[i],numtimes[i],(int)(stop-start),total,duration,position); //화면에 각각의 값을 11자리씩 출력
        list[sizelist[i]]=sizelist[i]; //reset value 라고 써있는데 왜 있는지 잘 모르겠다.
    }
    return 0;
}
int binsearch_itr(int list[], int searchnum, int left, int right)  //반복적으로 짠 이진탐색
{
    int middle; //int형 변수 middle 선언
    while(left<=right) //left가 right 이하일때 반복
    {middle=(left+right)/2;  //미들은 left와 right의 산술평균
    switch(COMPARE(list[middle],searchnum))  //COMPARE 의 값을 받아와 그에 따라 switch-case로 판단
    {
    case -1 : left=middle+1;  
                break;    //-1경우 left에 middle+1로 대입 후 break
    case 0 :    return middle;
                break; //0경우 middle값 리턴 후 break
    case 1 : right=middle-1;
                break; //1경우 right에 middle-1로 대입 후 break
    }
    }
    return -1; //while 루프가 깨졌을 경우 반환값 -1
}
int binsearch_rec(int list[], int searchnum, int left, int right) //recursive function으로 짠 이진탐색
{
    int middle;//int형 변수 middle 선언
    while(left<=right)//left가 right 이하일때 반복 recursive function이라서 if 를 써도 무방하다.
    {middle=(left+right)/2;//미들은 left와 right의 산술평균
    switch(COMPARE(list[middle],searchnum)) //COMPARE 의 값을 받아와 그에 따라 switch-case로 판단
    {
    case -1 : return binsearch_rec(list,searchnum,middle+1,right);
                break; //-1경우 binsearch_rec함수의 left자리에 middle+1, right 인자에 right 넣어 호출 후 break
    case 0 :    return middle; 
                break; //0의 경우 middle값 리턴 후 break
    case 1 : return binsearch_rec(list,searchnum,left,middle-1);
                break; //1경우 binsearch_rec함수의 left자리에 left, right 인자에 middle-1 넣어 호출 후 break
    }
    }
    return -1; //while 루프가 깨졌을 경우 반환값 -1
}
 
 
cs


반응형
저작자표시 비영리 변경금지

'컴퓨터 & 프로그래밍 & 전자공학 > Data Sturcture' 카테고리의 다른 글

dfs, bfs, prim, kruskal  (0) 2017.10.01
preorder, postorder, inorder, heap, tree  (0) 2017.10.01
stack, queue  (0) 2017.10.01
참고 사항  (0) 2017.10.01
Array, Pointer  (0) 2017.10.01
반응형

3.11>배열과 반복문을 이용하여 프로그램을 작성해보자. 키보드에서 정수로 된 돈의 액수를 입력 받아 오만 원권, 만 원권, 천 원권, 500원짜리 동전, 100원짜리 동전, 50원짜리 동전, 10원짜리 동전, 1원짜리 동전이 각 몇 개로 변환되는지 출력하라. 예를 들어 65370이 입력되면 오만 원권 1매, 만 원권 1매, 천 원권 5매, 100원짜리 동전 3개, 50원짜리 동전 1개, 10짜리 동전 2개이다. 이때 반드시 다음의 배열을 이용하고 반복문으로 작성하라.


int []unit={50000,10000,1000,500,100,50,10,1}; //환산할 돈의 종류


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
package HW1_JAVA;
import java.util.Scanner; //Scanner 클래스의 위치
class Sort{ //Sort 클래스 선언
    void sorting(int arr[], int gold){ //sorting 메소드 선언 인자 int형 배열 arr, int형 변수 gold
        int i;  int d;  //int형 변수 i, d 선언
        for(i=0;i<arr.length;i++) //isms 0부터 배열 arr의 길이보다 작을 때까지
        {d=gold/arr[i]; //d는 gold를 arr[i]로 나눈 것의 몫
            if(d==0) //d가 0이면 루프를 완전히 돌지 않고 i를 증가시킨 후 다시 돌게 만든다.
                continue;
            if(i<=2) //i가 2 이하이면 원과 매로 출력
                System.out.println(arr[i]+"원권 "+d+"매");
            else  //i가 2초과이면 동전과 개로 출력
                System.out.println(arr[i]+"원짜리 동전 "+d+"개");
        gold%=arr[i];  // gold = gold % arr[i] 와 같다. (나머지)
        }    
    }
}
public class MoneyDivison { //class MoneyDivison 선언
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in); //Scanner 클래스 객체와 레퍼런스 변수 선언
        Sort so = new Sort(); //Sort 클래스 객체와 레퍼런스 변수 선언
        int []unit={50000,10000,1000,500,100,50,10,1}; // int형 배열 unit 선언과 초기화
        System.out.print("금액을 입력하세요>>");
        int gold=s.nextInt(); // int형 변수 gold 선언과 정수형 입력
        so.sorting(unit, gold); //sorting 메소드를 unit배열과 gold변수를 넣어 호출
    }
}
 
cs




반응형
저작자표시 비영리 변경금지

'컴퓨터 & 프로그래밍 & 전자공학 > JAVA' 카테고리의 다른 글

ArrayUtility class  (0) 2017.06.18
직사각형 클래스  (0) 2017.06.18
2차원 배열  (0) 2017.06.18
정수 오름차순 정렬기  (0) 2017.06.18
하위 문자 모두 출력하기  (0) 2017.06.18
반응형

3.7>4x4의 2차원 배열을 만들고 이곳에 1에서 10까지 범위의 정수를 랜덤하게 생성하여 정수 16개를 배열에 저장하고 2차원 배열을 화면에 출력하라.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package HW1_JAVA;
public class Two_Dimensinal_Array { //Two_Dimensinal_Array class 선언
    public static void main(String[] args) {
        int darr[][]=new int[4][4]; //4 * 4 사이즈의 인트형 이차원배열 darr 선언
        int i=0; int j=0; //int 형 변수 i,j 선언 및 초기화
        for(i=0;i<4;i++)  //i는 0부터 3까지 반복
        {
            for(j=0;j<4;j++) //j는 0부터 3까지 반복
            {
                darr[i][j]=(int)Math.round(Math.random()*9+1);
                //random메소드는 0.0이상0.1미만난수 반환 round메소드는 반올림
                System.out.print(darr[i][j]+"    "); //darr[i][j]출력 후 탭키 입력
            }
            System.out.println(); //개행문자 입력
        }
    }
}
 
 
cs




반응형
저작자표시 비영리 변경금지

'컴퓨터 & 프로그래밍 & 전자공학 > JAVA' 카테고리의 다른 글

직사각형 클래스  (0) 2017.06.18
돈 단위 나누기  (0) 2017.06.18
정수 오름차순 정렬기  (0) 2017.06.18
하위 문자 모두 출력하기  (0) 2017.06.18
직사각형 충돌  (0) 2017.06.18

+ Recent posts

티스토리툴바