Psuedo code Tutorial

• 1. 今回のスコープ
  • やりたいこと
  • 注意点
• 2. Pseudo-codeとは
  • Pseudo-codeを書くにあたって気をつけるべき点
  • Pseudo codeでよく見るスタイル
    • Sequenceの例
    • IF-THEN-ELSEの例
    • WHILEの例
    • CASEの例
    • REPEAT-UNTILの例
    • FORの例
    • NESTED CONSTRUCTSの例
    • INVOKING SUBPROCEDURESの例
    • EXCEPTION HANDLINGの例
  • 良いPseudo Codeの例
    • Adequate
    • Better
    • Not So Good
    • Better
  • 良いPseudo codeとソースコードの関係の例
    • Pseudo code
    • Java source code
• 3. Pseudo-code Examples
  • Bubble sort アルゴリズム
    • C implementation
    • Pseudo codeでの表現

1. 今回のスコープ

やりたいこと

• 疑似コードの書き方の読み方と書き方の指針のまとめ

注意点

疑似コード(Pseudo code)は、特定のプログラミング言語の知識を持たない人でもアルゴリズムが理解できるように自然言語に近い形で記述するコードです。疑似コードには厳格なルールがあるわけではなく、書く人によって様々な書き方があります。

2. Pseudo-codeとは

Pseudo-codeは、アルゴリズムを記述するための一種の構造化された文章です。これにより、実装者はプログラミング特有のSyntaxに気を取られることなく、アルゴリズムのロジックに集中することができます。同時に、疑似コードはアルゴリズムを他人に伝えるためのツールなので、疑似コードはアルゴリズムのロジック全体を記述する必要があります。

Pseudo-codeを書くにあたって気をつけるべき点

• Pseudo-codeで使用する語彙は、implementation domainの語彙ではなく、problem domainの語彙でなければなりません。
• アルゴリズムのロジックは、単一のループまたは決定のレベルに分解されなければなりません。

例えば「顧客名簿の中から一年間で最も購買したお客様を探す」という文章は曖昧すぎてだめです。Problem domainの共通認識として購買チャネルと購買期間が明確だったとしても、「最も購買したお客様」を探すためには一人ひとりの１年間の購買金額を知った上で、比較して、「最も購買したお客様」を決定する必要があるので、「アルゴリズムのロジックは、単一のループまたは決定のレベルに分解されなければなりません。」という要件を満たしていません。

Pseudo codeでよく見るスタイル

ロジックの流れを表現するにあたってよく見るconstructs（構造を表現するもの）を紹介します。

次に、input, output, and processing operationに関係するキーワードを紹介します。

Sequenceの例

Example

    READ height of rectangle
    READ width of rectangle
    COMPUTE area as height times width

IF-THEN-ELSEの例

一般的な構文は以下のような形となります。

IF condition THEN

    sequence 1

ELSE

    sequence 2

ENDIF

一例として、

    IF HoursWorked > NormalMax THEN

        Display overtime message

    ELSE

        Display regular time message

    ENDIF

WHILEの例

WHILE condition

    sequence

ENDWHILE

という構造を取ります。

    WHILE Population < Limit

        Compute Population as Population + Births - Deaths

    ENDWHILE

CASEの例

CASE expression OF

    condition 1 : sequence 1
    condition 2 : sequence 2
    ...
    condition n : sequence n
    OTHERS:
    default sequence

ENDCASE 

CASE  grade  OF
        A       : points = 4
        B       : points = 3
        C       : points = 2
        D       : points = 1
        F       : points = 0
ENDCASE

REPEAT-UNTILの例

REPEAT

    sequence

UNTIL condition

FORの例

FOR iteration bounds

    sequence

ENDFOR

一例として

FOR each month of the year (good)
FOR month = 1 to 12 (ok)

FOR each employee in the list (good)
FOR empno = 1 to listsize (ok)

NESTED CONSTRUCTSの例

    SET total to zero
    REPEAT

        READ Temperature
        IF Temperature > Freezing THEN
            INCREMENT total
        END IF

    UNTIL Temperature < zero
    Print total

INVOKING SUBPROCEDURESの例

    CALL AvgAge with StudentAges
    CALL Swap with CurrentItem and TargetItem
    CALL Account.debit with CheckAmount
    CALL getBalance RETURNING aBalance
    CALL SquareRoot with orbitHeight RETURNING nominalOrbit

EXCEPTION HANDLINGの例

    BEGIN
        statements
    EXCEPTION
        WHEN exception type
            statements to handle exception
        WHEN another exception type
            statements to handle exception
    END

良いPseudo Codeの例

Adequate

FOR X = 1 to 10
    FOR Y = 1 to 10
        IF gameBoard[X][Y] = 0
            Do nothing
        ELSE
            CALL theCall(X, Y) (recursive method)
            increment counter                 
        END IF
    END FOR
END FOR

Better

Set moveCount to 1
FOR each row on the board
    FOR each column on the board
        IF gameBoard position (row, column) is occupied THEN
            CALL findAdjacentTiles with row, column
            INCREMENT moveCount
        END IF
    END FOR
END FOR

Not So Good

FOR all the number at the back of the array
    SET Temp equal the addition of each number
    IF > 9 THEN
        get the remainder of the number divided by 10 to that index
        and carry the "1"
    Decrement one
Do it again for numbers before the decimal

Better

SET Carry to 0
FOR each DigitPosition in Number from least significant to most significant

    COMPUTE Total as sum of FirstNum[DigitPosition] and SecondNum[DigitPosition] and Carry  

    IF Total > 10 THEN
        SET Carry to 1
        SUBTRACT 10 from Total
    ELSE
        SET Carry to 0
    END IF

    STORE Total in Result[DigitPosition]

END LOOP  

IF Carry = 1 THEN
    RAISE Overflow exception
END IF

public boolean moveRobot (Robot aRobot)
{
    //IF robot has no obstacle in front THEN
        // Call Move robot
        // Add the move command to the command history
        // RETURN true
    //ELSE
        // RETURN false without moving the robot
    //END IF
} 

public boolean moveRobot (Robot aRobot)
{
    //IF robot has no obstacle in front THEN
    if (aRobot.isFrontClear())
    {
        // Call Move robot
        aRobot.move();
        // Add the move command to the command history
        cmdHistory.add(RobotAction.MOVE);
        return true;
    }
    else // don't move the robot
    {
        return false;
    }//END IF
}

#include<stdio.h>

void bubble_sort(int array[], int size)
{
    int i, j, tmp;

    for (i = 0; i < size; i++)
        for (j = size - 1; j > i; j--)
            if (array[j-1] > array[j])
            {
                tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
            }
}

procedure bubble_sort

  Set array: array to be sorted
  Set size : array size

  repeat
  for i = 0 to size-1 do;
    for j = size - 1 to i do;
      if array[j - 1] > array[j] then
        swap array[j - 1] and array[j]
      end if
    end do
  end do 

end procedure