[Abe先生の授業] プログラム応用講義資料 (Chapter1)

 Abe 교수님은 우리 연구실 제일 어른이신 분인데 Tanaka 교수님께서 4학년 수업이지만 지도 교수님 수업이니까 들어보라고 하셔서 들은 수업이다. 주로 이미지 프로세싱에 관해 배우고 선수 과목은 Visual C++ 이다.

오늘은 간단한 수업의 강의와 가볍게 풀어보라는 퀴즈를 내주셨는데 다음과 같다.

プログラム応用課題１　　　　　　

 

 

一般にｎ個のデーターを処理するプログラムの計算量は logｎ，　ｎ，　ｎlogn,  ｎの２乗，……となる．

 以下で指定されたプログラムの作成方針を考えた後，そのプログラムを作成しなさい． 

配列　v[0] からv[n-1]  にｎ個のデーターが入っているとする．

（１）ｎ個のデーターが，　v[i]≦v[i+1]  （ただし，0≦i≦n-2）を充たすようにデーターを並び替えるプログラムを下記に従って２つ作成しなさい，

 

［Ａ］　プログラムの計算量がデーターの個数ｎの２乗に比例するもの

아마도 버블정렬(Bubble Sort)을 만들어 보라고 하신거 같아서 개선하지않은 단순한 버블정렬을 만들어 보았다.

#include "bubbleSort.h"

void bubbleSort::bubble_sort(int a[], int n)
{
 //variable declare
 int i, j, t, d;

 for(i=0; i<n-1; i++)
 {
  for(j=0; j<n-i; j++)
  {
   if(a[j-1] > a[j])
   {
    //calcualation
    t = a[j-1];
    a[j-1] = a[j];
    a[j] = t;

    //test debugging
    for(d=0; d<n; d++)
    {
     printf("%d, ",a[d]);
    }//end for

    printf("\n");
   }//end if
  }//end for j
 }//end for i
}


［Ｂ］　最悪の場合を除いて，計算量が［Ａ］を凌ぐもの．最悪の場合とはどのような場合か．

첨부파일을 열어보면 퀵 정렬(Quick Sort)을 만들어 보라는 이야기 인듯 싶다^^.

#include "quickSort.h"

void quickSort::quick_sort(int a[], int n)
{
 int v, t;
 int i, j;

 if(n>1)
 {
  v = a[n-1];

  i = -1;
  j = n -1;

  while(1)
  {
   while (a[++i] < v);
   while (a[--j] > v);
   if (i >= j)
    break;

   t = a[i];
   a[i] = a[j];
   a[j] = t;

  }//end while

  t = a[i];
  a[i] = a[n-1];
  a[n-1] = t;

  quick_sort(a, i);
  quick_sort(a+i+1, n-i-1);
 }//end if

 //debug
 //for(int x=0; x<n; x++)
 //{
 // printf("%d, ", a[x]);
 //}

 //printf("\n");

}

 

(２）　（１）で並び替えられた配列の中にある数が含まれているか否かを調べるプログラムを下記に従って２つ作成しなさい．

 

［Ｃ］　プログラムの計算量がデーターの個数ｎに比例するもの
순차 검색을 만들어 보았다.

#include "sequentialSearch.h"

int sequentialSearch::li_search(int key, int a[], int *num)
{
 int i=0;

 while ( (a[i] != key) && (i < *num) )
  i++;

 return(i < *num ? i : -1);
}


［Ｄ］　計算量が［Ｃ］を凌ぐもの．
이분 검색을 만들어 보았다.

#include "binarySearch.h"

int binarySearch::bi_search(int key, int a[], int n)
{
 int mid = 0;
 int left = 0;
 int right = n-1;

 while(right >= left)
 {
  mid = (right + left) / 2;
  if(key == a[mid])
   return mid;
  
  if(key < a[mid])
   right = mid -1;
  else
   left = mid + 1;
 }//end while

 return -1;
}

 

プログラムを配列でなくポインターを使って書き直す．

 

참고자료

1. Chpater1 강의 자료

プログラム応用課題１.doc

 

 

2. Source Code Zip

ProgrammingApp1A.zip