Design and Analysis of Algorithms

I collect and make up this pseudocode from the book：

<<Introduction to the Design and Analysis of Algorithms_Second Edition>> _ Anany Levitin
Note that throughout the paper, we assume that inputs to algorithms fall within their specified ranges and hence require no verfication. When implementing algorithms as programs to be used in actual applications, you should provide such verfications.
About pseudocode: For the sake of simplicity, we omit declarations of variables and use indentation to show the scope of such statements as for, if and while. As you saw later, we use an arrow <- for the assignment operation and two slashes // for comments.

Algorithm Euclid(m, n)

    // Computes gcd(m, n) by Euclid's algorithm

    // Input: Two nonnegative, not-both-zero integers m and n

    // Output: Greatest common divisor of m and n

    while n ≠  do

        r <- m mod n

        m <- n

        n <- r
    return m

Algorithm Sieve(n) 
　　// Implements the sieve of Eratosthenes

    // Input: An integer n ≥ 2

    // Output: Array L of all prime numbers less than or equal to n

    for p <-  to n do A[p] <- p

    for p <-  to ⌊√n⌋ do
　　 　　 if A[p] ≠ 0 // p hasn't been eliminated on previous passes
　　　　  　　 j <- p * p
　　　　　　   while j ≤ n do
　　　　　　　　　　A[j] <- 0 // mark element as eliminated
　　　　　　　　　　 j <- j + p
　　// copy the remaining elements of A to array L of the primes
　　i <- 0
　　for p <- 2 to n do 
　　　　  if A[p] ≠ 0
　　　　　　　L[i] <- A[p]
　　　　　　　i <- i + 1
　　return L

Euclid's algorithm, as presented in Euclid's treatise, uses subtractions rather than integer divisions. Write a pseudocode for this version of Euclid's Algorithm. Here is a nonrecursive version:

Algorithm Euclid2(m, n)

    // Computes gcd(m, n) by Euclid's algorithm based on subtractions

    // Input: Two nonnegative interges m and n not both equal to 0

    // Output: The greatest common divisor of m and n

    while n ≠  do

        if m < n swap(m, n)

            m <- m - n

    return m

Write a pseudocode for an algorithm for finding real roots of equation ax^2 + bx + c = 0 for arbitrary real coefficients a, b and c.(You may assume the availability of the square root function sqrt(x).)

Algorithm Quadratic(a, b, c)

    // The algorithm finds real roots of equation ax^2 + bx + c = 0

    // Input: Real coefficients a, b, c

    // Output: The real roots of the equation or a message about their absence

    if a ≠

        D <- b*b - *a*c

        if D >

            temp <- *a

            x1 <- (-b + sqrt(D)) / temp

            x2 <- (-b - sqrt(D)) / temp

            return x1, x2

        else if D =

            return -b / (*a)

        else

            return 'no real roots'

    else // a = 0

        if b ≠  return -c / b

        else // a = b = 0

            if c =  return 'all real numbers'

            else return 'no real roots'

Write a pseudocode to describe the standard algorithm for finding the binary representation of a positive decimal integer

Algorithm Binary(n)

    // The algorithm implements the standard method for finding

    //　　　　 the binary expansion of a positive decimal integer
　　 // Input: A positive decimal integer n

    // Output: The list b(k), b(k-1)..., b(1), b(0) of n's binary digits

    k <-

    while n ≠

        b_k<- n mod

        n <- ⌊n/2⌋
        k <- k +

The following algorithm for finding the distance between the two closest elements in an array of numbers.

Algorithm MinDistance(A[..n-])

    // Input: An array A[0..n-1] of numbers

    // Output: The minimum distance d between two of its elements

    dmin <- ∞

    for i <-  to n- do

        for j <- i+ to n- do

            temp <- |A[i] - A[j]|

            if temp < dmin

                dmin <- temp

    return dmin

Consider the algorithm for the sorting problem that sorts an array by counting, for each of its elements, the number of smaller elements and then uses this information to put the elements in ins appropriate position in the sorted array

Algorithm ComparisionCountingSort(A[..n-], S[..n-])

    // Sorts an array by comparison counting

    // Input: Array A[0..n-1] of orderable values

    // Output: Array S[0..n-1] of A's elements sorted in nondecreasing order

    for i <-  to n- do

        Count[i] <-

    for i <-  to n- do

        for j <- i+ to n- do

            if A[i] < A[j]

                Count[j] <- Count[j] +

            else

                Count[i] <- Count[i] +

    for i <-  to n- do

        S[Count[i]] <- A[i]

New words:
indentation: 缩排 sieve: 筛子 Eratosthenes: a man_埃拉托色尼 treatise: 论文;专著
quadratic: 二次方程式

(End_xpjiang)

巴特西

Design and Analysis of Algorithms_Introduction

最新文章

热门文章