알고리즘 Pseudo-code 모음

■ 순차검색 알고리즘 (Pseudo-code)

void seqsearch(int n, // 입력(1)

const keytype S[], // (2)

keytype x, // (3)

index& location) { // 출력

location = 1;

while (location <= n && S[location] != x)

location++;

if (location > n)

location = 0;

}

■ 이분검색 알고리즘

void binsearch(int n, // 입력(1)

const keytype S[], // (2)

keytype x, // (3)

index& location) // 출력

{ index low, high, mid;

low = 1; high = n;

location = 0;

while (low <= high && location == 0)

{ mid = (low + high) / 2; // 정수나눗셈

if(x == S[mid])

location = mid;

else if (x < S[mid])

high = mid – 1;

else low = mid + 1;

 }

}

■ 재귀적 방법으로 피보나찌 수 구하기

int fib(int n) {

if (n <= 1)

return n;

else

return(fib(n-1)+fib(n-2));

}

 

■ 반복적 방법으로 피보나찌 수 구하기

int fib2 (int n)

{

index i;

int f[0..n];

f[0]=0;

if (n>0)

{

f[1]=1;

for (i=2; i<=n; i++)

f[i]= f[i-1]+f[i-2];

}

return f[n];

} 

 

■ Divide & Conquer

procedure D&C (p, q)

int n, A(1:n);

int m, p, q; /*1≤p≤q≤n */

If SMALL(p, q) then return(G(p, q))

else

{ m := DIVIDE(p, q)

return COMBINE (D&C(p, m), D&C(m+1, q))

}

End if

 

■ Binary Search

i) Recursuve 알고리즘

ii) Iterative 알고리즘

■ 합병정렬(Mergesort)

 

■ Quicksort (빠른정렬)

void quicksort (index p, index q)

{      if (p < q)   {

j = q+1;

partition(p, j);

quicksort(p, j-1);

quicksort(j+1, q); }

}

 

Procedure Partition(p, j)

Integer p,j,I;

Global A(p,j);

X=A(p);

I=p;   / * A(p) is the partition element * /

Loop

        Loop i=i+1 until A(i)>=x repeat

        Loop j=j-1 until A(j)<=x repeat

        If i<j then

                Call INTERCHANGE E(A(i),A(j)) / * exchange * /

        Else exit

Repeat

A(p)=A(j); /* the partition element * /

A(j)=x /* belongs at position * / 

 

■ Selection

 

■ Procedure Greedy(A, n)

/*A(1…n)contains the n inputs * /

Solution=null

for i=1 to n do

        x=SELECT(A)

        if FEASIBLE(solution,x)

                then solution=solution U{x}

        endif

endfor

return(solution)

 

■ Fractional Knapsack problem

 

■ Greed-Knapsack(P, W, M, X, n)

  

■ 0-1 Knapsack Problem