패드곰

padgom.egloos.com

포토로그

POA(Problems on Algorithms) N267 - increment Algorithms


p52 N267 - increment
    자연수에 1을 이진수로 더하는 알고리즘(재귀호출식)

function(y)
    comment Return + 1;
  1.     if y = 0 then return(1) else
  2.         if y mod 2 = 1 then
  3.             return(2 · increment(⎣y/2⎦))
  4.         else return(y + 1)

Source Code
  1. int increment(int y)
  2. {
  3.     if ( y == 0 )
  4.         return 1;
  5.     else
  6.     {
  7.         if ( (y % 2) == 1 )
  8.             return 2 * increment(y/2);
  9.         else
  10.             return y + 1;
  11.     }
  12. }
태그 : , , , ,
트랙백(0)덧글(3)

POA(Problems on Algorithms) N265 - fib Algorithms


p51 N265 - fib
    n번째 피보나치 합을 구하는 알고리즘

function fib(n)
    comment Return Fn, the nth Fibonacci number
  1.     if n = 0 then return(0) else
  2.         last := 0; current := 1;
  3.         for i := 2 to n do
  4.             temp := last + current; last := current; current := temp;
  5.     return(current)

Source Code
  1. int fib(const int n)
  2. {
  3.     int i, last, current, temp;
  4.  
  5.     if ( n == 0 )
  6.         return 0;
  7.     else
  8.     {
  9.         last = 0;
  10.         current = 1;
  11.         for ( i = 0; i < n; i++ )
  12.         {
  13.             temp = last + current;
  14.             last = current;
  15.             current = temp;
  16.         }
  17.     }
  18.  
  19.     return current;
  20. }
태그 : , ,
트랙백(0)덧글(0)

POA(Problems on Algorithms) N264 - Horner Algorithms


p51 N264 - Horner
    n번의 덧셈과 n번의 곱셈으로 다항식을 푸는 알고리즘(호어법)

function Horner(A, n)
    comment Return ∑ n, i=0 A[i] · x^i
  1.     u := 0
  2.     for i := n downto 0 do
  3.         u := A[i] + u · x;
  4.     return(u)

Source Code
  1. int Horner(int *A, int x, const int n)
  2. {
  3.     int u = 0, i;
  4.  
  5.     for ( i = n; i > 0; i-- )
  6.         u = A[i] + u * x;
  7.  
  8.     return 0;
  9. }
태그 : , , ,
트랙백(0)덧글(0)

POA(Problems on Algorithms) N263 - matmultiply Algorithms


p51 N263 - matmultiply
    nxn 행렬곱을 구하는 알고리즘

function matmultiply(Y, Z, n);
    comment multiplies n x n matrices Y Z
  1.     for i := 1 to n do
  2.         for j := 1 to n do
  3.             X[i, j] := 0;
  4.             for k := 1 to n do
  5.                 X[i, j] := X[i, j] + Y[i, k] · Z[k, j]
  6.     return(X)

Source Code
  1. int **multiply(const int **Y, const int **Z, const int n)
  2. {
  3.     int **X, i, j, k;
  4.  
  5.     X = (int **)malloc(sizeof(int *) * n);
  6.     for ( i = 0; i < n; i++ )
  7.         X[i] = (int *)malloc(sizeof(int) * n);
  8.  
  9.     for ( i = 0; i < n; i++ )
  10.     {
  11.         for ( j = 0; j < n; j++ )
  12.         {
  13.             X[i][j] = 0;
  14.             for ( k = 0; k < n; k++ )
  15.                 X[i][j] = X[i][j] + Y[i][k] * Z[k][j];
  16.         }
  17.     }
  18.  
  19.     return X;
  20. }
태그 : , , ,
트랙백(0)덧글(0)

POA(Problems on Algorithms) N262 - match Algorithms


p51 N262 - match
    문자 S에서 패턴 P가 있는지 찾는 알고리즘

function match(S, P, n, m)
    comment Find the pattern P[0...m-1] in string S[1...n]
  1.     l := 0; matched := false;
  2.     while ( l ≤ n - m ) ∧ ￢matched do
  3.         l := l + 1;
  4.         r := 0; matched := true;
  5.         while ( r < m ) ∧ matched do
  6.             matched := matched ∧ ( P[r] = S[l+r] )
  7.             r := r + 1;
  8.     return(l)

Source Code
  1. int match(const char *S, const char *P, int n, int m)
  2. {
  3.     int l = 0, r;
  4.     bool matched = false;
  5.  
  6.     while ( (l <= (n - m)) & (!matched) )
  7.     {
  8.         r = 0;
  9.         l++;
  10.         matched = true;
  11.         while ( (r < m) & matched )
  12.         {
  13.             matched = matched & (P[r] == S[l+r]);
  14.             r++;
  15.         }
  16.     }
  17.  
  18.     return l;
  19. }

P가 S[0] 부터 일치할 때는 찾지 못 한다.
태그 : , , ,
트랙백(0)덧글(0)
1 2 3 4 5
padgom.egloos.com is powered by Egloos. Subscribe to RSS Skin design by egloos.