□ ＜ 第４回　アルゴリズム表記法と基本的なコード記述法 ＞ △

■４．１　アルゴリズム（algorithm） 　たとえ小規模なプログラムであってもを，コードの記述だけでは，そのプログラムの作成意図を正確に理解することは容易でない．まして，そのプログラムを修正する必要がある場合は，記述内容を一から確認しなければならないことも多く，大変な時間と労力が必要となる． 　このような場合に威力を発揮するのが，アルゴリズムの表記である．アルゴリズムとはコンピュータを使ってある特定の目的を達成するための処理手順のことであり，アルゴリズムをプログラミング言語を用いて具体的に記述したものがプログラムである． 　また，プログラムとは，極論すると，何らかの入力データに対してデータを出力するものであり，アルゴリズムとはデータの流れを示す．したがって，プログラムを作る場合は，まずデータをどのようにプログラム全体に流すかを考える必要がある．これがアルゴリズムを考える作業である． 　適切なアルゴリズムの構築によってプログラムの構造を立体化してプログラミングすることで，記述内容を確認する際の時間と労力が格段に少なくなる． 　アルゴリズムは互いに関連し合ったり，階層構造をとったりするが，できるだけ汎用的なアルゴリズムを使いデータの流れを明確にすることに心がけて設計することが，よりよいプログラムを作る近道である．ここで「よい」プログラムとは以下のような特徴を備えたプログラムを指す． 効率が高いこと（計算速度が早いこと） リソース（メモリ等）使用量が低いこと メンテナンスが容易なこと 再利用が容易なこと 拡張性が高いこと ◆4.1.1　オーダー記法 　対象となるデータの個数を n とした時の計算回数． 　オーダーが小さいほど計算量が少なく，高速なアルゴリズムといえる． O(1) n によらなず，計算回数は変わらない．   O(n) n に比例する． for 文など O(log n) 底を 2 とした対数に比例する． 1回の計算ごとにデータを 2等分していくような場合 O(n^2) n の 2乗に比例する． for などでの 2重ループなど O(2^n) 2 の n乗に比例する． データに対して全ての組合せを調べる場合など  ◆4.1.2　アルゴリズム例 ▼バブルソート   　n 個のデータを値の大きさ順に並べるアルゴリズム． 1.   1 番の要素を 2 番の要素と比較して，1 番の方が大きければ交換する． 2 番の要素を 3 の要素と比較して，2 番の方が大きければ交換する． これを 要素 ｎ-1 と ｎ まで繰り返すことで，最も大きい要素が ｎ 番に移動する（泡のイメージ）． 2.   1 番の要素から 要素 ｎ-2 と ｎ-1 まで，1 の操作を行う． これによって，二番目に大きな要素は n-1 番に移動する． 3.   以下繰返し． 　最も直感的なソートアルゴリズムの一つ． 　計算量はO(n^2)であり，実装は容易だが計算量は比較的大きいアルゴリズム． int data[DATA_NUM] = {53, 12, 28, 46, 5, 18, 55, 72, 99, 8}; void bubble_sort() {   int i,j;   for(i = 0; i < DATA_NUM; i++) {     for(j = 1; j < DATA_NUM - i; j++) {       if(data[j-1] > data[j]) {         int tmp = data[j-1];         data[j-1] = data[j];         data[j] = tmp;       }     }   } }  ▼二分探索   　n 個のデータが小さい順に並んでいる場合に，指定された値のデータを探すアルゴリズム． 1.   全データの中央のデータ値を見る． 2.   指定された値が中央のデータ値より大きければ，中央より小さいデータを破棄する（データ数が1/2となる）． 3.   1/2となったデータを全データとし，1からの操作をデータが見つかるまで（見つからないことが判明するまで）繰り返す． 　1回の計算ごとに対象のデータが1/2となるため，計算量はO(log n)． void binary_search(int key) {   int find_flag = 0;   int search_left = 0;   int search_right = DATA_NUM - 1;   int pivot;   while(search_left < search_right) {     pivot = (search_right + search_left) / 2;     if(key == data[pivot]) {       find_flag = 1;       break;     }     if(pivot == search_right || pivot == search_left) break;     if(key < data[pivot]) search_right = pivot;     if(key > data[pivot]) search_left = pivot;   }   if(find_flag == 1)     printf("%d は data[%d] で発見しました！\n", key, pivot);   else     printf("%d は見つかりませんでした..\n", key); }

■４．２　フローチャート ◆4.2.1　表記法 　アルゴリズム（プログラム）を分かりやすくするための手段として，それを図示するという方法がとられることが多い． 　アルゴリズムの図化には様々な方法が提案されているが，一般によく利用されるのはフローチャートという記述法であり，情報処理技術者試験でもその知識は必須のものとされている． 　 しかし，フローチャートは大規模なプログラムの図示には必ずしも適当ではない．大規模プログラムの図示には PAD と呼ばれる表記法が有効であると言われている．以下に両者の特徴を示す． フローチャート （Flowchart） ・表記が容易（時間の経過に沿って記述できる）． ・同じ処理を異なる表現で記述できる． ・構造を表現できない（時間の流れに拘束される），BASIC 言語的． ・小規模プログラム向き． PAD （Problem Analysis Diagram） ・表記するにはアルゴリズムを正確に把握しておく必要がある． ・1つの処理の表現方法は1種類． ・構造表現に適する，C 言語的． ・大規模プログラム向き． 　本実習ではフローチャートを用いてプログラムを図示する． 　以下に， フローチャートの基本的な利用法を示す． ◆4.2.2　記号 　フローチャートで使用する主な記号を以下に示す． 　フローチャートにはたくさんの記号があり，入出力，計算，条件判定等はすべて異なる形で記述しなくてはいけないため，正確なフローチャートの記述は意外と難しい． 　しかし，実際にはそれらの各処理のほとんどを“処理記号”で済ませてしまうことも多い．このような表現の柔軟さが，フローチャートが広く一般に受け入れられている理由の一つである． 記号 名称 意味 流れ線 処理の順序を表す． 順序を明確にするために，矢印を付ける場合もある． 端子 処理の開始と終了を表す． 処理 判断処理以外の処理を表す． 判断 条件により，流れが二つ以上に分岐する処理を表す． 定義済み処理 別に用意した処理（サブルーチン等）を利用することを表す． 入出力 データの入出力を表す． 準備 変数の宣言や初期値の設定などの処理を表す． ループ端 繰り返し処理の開始と終了を表す． 書類 プリンタなどへのデータ出力を表す． ◆4.2.3　基本的な表現法 　以下にプログラムの基本処理をフローチャートを用いて示す． ▼直線処理 　フローチャートの上から下へと処理が一直線に進む形であり，最も単純な処理の流れを示す． 　 　例として，C = A + B を計算するアルゴリズムを考える． 　例題は，【データ A および B の入力（記憶）】→【A および B により C を計算】→【計算結果 C の出力】，という順番で処理でき，各処理は，それぞれ以下の記号で表示できる． 　・変数定義 　・データ A，B の入力：入出力記号 　．A，B により C を計算：処理記号 　．計算結果 C の出力：入出力記号 　．処理全体の開始と終了箇所に端子記号を付ける ▼分岐処理 　条件を判定した結果によって 2 つ以上の方向に処理が分かれる様子を示す． 　条件として，以下の 2 種類が考えられる． 　・等号・不等号の式で表し，成立・不成立によって流れを変える（2 分岐：C 言語の if 文）． 　・比較する値（式）を記述し，比較結果によって流れを変える（多分岐： C 言語の switch 文）． 　 　2 分岐例として，C へ A と B の大きい方を代入するアルゴリズムを考える． 　例題は，【A および B の入力（記憶）】→【A および B の大小判断】→【判断結果により C の値を決定】→【C の出力】，という順番で処理でき，各処理はそれぞれ以下の記号で表示できる． 　・変数定義 　．A，B の入力：入出力記号 　．A，B の大小判断：判断記号 　．判断結果の格納：処理記号 　．C の出力：入出力記号 　．処理全体の開始と終了箇所に端子記号を付ける 　 　多分岐例として，C = 10 の A 乗を計算するアルゴリズムを考える． 　例題は，【A の入力（記憶）】→【A の値判断】→【判断結果により C の値を決定】→【C の出力】，という順番で処理でき，各処理はそれぞれ以下の記号で表示できる． 　・変数定義 　．A の入力：入出力記号 　．A の値判断：判断記号 　．判断結果による処理：処理記号 　．C の出力：入出力記号 　．処理全体の開始と終了箇所に端子記号を付ける ▼繰り返し（ループ）処理 　任意の処理を繰り返し実行する様子を示す． 　繰り返し処理の専用記号であるループ端記号を用いて表す方法と，判断記号を用いて表す方法がある． 　 　例として，C へ 0～10 の総和を格納するアルゴリズムを考える． 　例題は，【A および C の初期値設定】→【A が 10 になるまで加算，A をインクリメント】→【C の出力】，という順番で処理でき，各処理はそれぞれ以下の記号で表示できる． 　・変数定義 　．A および C の初期値設定：処理記号 　．A を C に加算，A をインクリメント：ループ端記号で処理の前後を囲む 　．C の出力：入出力記号 　．処理全体の開始と終了箇所に端子記号を付ける 　なお，ループ端にはループ終了条件（図では A＞10）を記入する． 　ループ終了判定はどちらのループ端にも設定できるが，条件によっては処理が異なる場合が留ので注意すること． 　・左図：前判定（C 言語の while 文や for 文と同様） 　・右図：後判定（C 言語の do-while 文と同様） 　 　同じ例を判断記号を用いて表記すると図のようになる． 　なお，上記とと同様，左図が前判定，右図が後判定による表記である． ▼定義済み処理 　定義済み処理（サブルーチン）を別のフローチャートとし，主処理（メインルーチン）を行うフローチャートから呼び出して利用する場合の処理の流れを示す． 　 　例として，D = 10 の A 乗＋10 の B 乗（A，B：0～4）の計算を，累乗をサブルーチンとして処理する場合のアルゴリズムを考える． 　例題は，【A，B の入力（記憶）】および【D の出力】をメインルーチンで，【A および B の値判断】および【判断結果により C の値を決定】をサブルーチンで処理している・ 　サブルーチンも，メインルーチンと同様に表現し，その呼び出しには定義済み処理記号を使用する．

■４．３　基本的なコード記述法 　以下の実習用基本ソースコードをコピーして利用する．＊赤文字部分を編集する． 　 ;*********************************************************** ;       step04 for PIC16F84A ;       step04.asm, H. OSADA, Nov. 2021 ;*********************************************************** ; ;================================================= ;  definitions ;================================================= ;- hardware -----------------------------------         LIST    P=PIC16F84A         #INCLUDE "P16F84A.INC" ;         __CONFIG _HS_OSC & _WDT_OFF & _PWRTE_ON & _CP_OFF ; ;- constant label ----------------------------- ;**name EQU **value ; ;- file register ------------------------------         CBLOCK  0CH             ;**name         ENDC ; ;================================================= ;  run start ;================================================= ;- reset start --------------------------------         ORG     0         GOTO    INIT ; ;- interrupt start ----------------------------         ORG     4         GOTO    ISR ; ;- initialize --------------------------------- INIT ;**module settings ; ;================================================= ;  main routine ;================================================= MAIN ;** procedure ; ;================================================= ;  interrupt service routine ;================================================= ISR ;** procedure ; ;================================================= ;  subroutine ;================================================= ;** procedure ; ;***********************************************************         END ◆4.3.1　バイト定数と変数の設定 ▼定数の定義 　プログラムで使用する定数は EQU 命令によりラベルを定義できる．通常はプログラムの先頭部分に定義する． 　なお，定数範囲は 000H～0FFH までである． 　以下に，MAX と MIN という定数（それぞれ 240 と 0 ）を定義した例を示す． MAX     EQU     0F0H MIN     EQU     000H ▼変数の定義 　PIC16F84A では，データメモリ中の 0CH～4FH 番地までの 68 個のレジスタが変数として利用できる． 　各変数用レジスタは EQU 命令および CBLOCK～ENDC 命令によりラベルを定義することができる．通常はプログラムの先頭部分（定数の定義後）に定義する． 　定数の定義と区別するため，CBLOCK～ENDC 命令で記述されることが多いが，データメモリの範囲を超えないように注意すること． 　以下に，data1 と data2 という変数（それぞれ 0CH と 0DH 番地）を定義した例を示す． ・EQU を利用する場合 data1   EQU     0CH data2   EQU     0DH ・CBLOCK～ENDC を利用する場合         CBLOCK  OCH             data1             data2         ENDC ▼変数の初期化 　変数を初期化（初期値の設定）するには，通常 MOVLW 命令にとMOVWF 命令を利用する． 　すなわち，MOVLW 命令でリテラルデータを Wreg に格納し，MOVWF 命令で指定されたレジスタに転送する．リテラルデータは数値以外にも定数ラベルによっても指定できる． 　また，0 に初期化する場合に限り，CLRF 命令も利用できる． 　以下に，変数 data1 と data2 に対して，それぞれ 0 と 240 （F0H もしくは定数 MAX）という値を設定した例を示す． ・定数ラベルを利用しない場合         MOVLW   000H         MOVWF   data1 ;         MOVLW   0F0H         MOVWF   data2 ・定数ラベルを利用する場合         MOVLW   MIN         MOVWF   data1 ;         MOVLW   MAX         MOVWF   data2 ・CLRF 命令を利用する場合         CLRF    data1 ;         MOVLW   MAX         MOVWF   data2 ・プログラムメモリ内に定義した定数を利用する場合 　サブルーチンコールを利用することで，任意の場所の定数を読み込むことができる．         MOVLW   0               ;set adr 0          CALL    INIT_DATA         MOVWF   data1         MOVLW   1               ;set adr 1         CALL    INIT_DATA         MOVWF   data2 ; INIT_DATA         ADDWF   PCL,F         RETLW   D'0'            ;adr 0         RETLW   D'240'          ;adr 1 ◆4.3.2　ビット変数（フラグ）の設定 　処理が複雑なプログラムになるに従い，多くの変数を利用して処理を制御する必要が出てくる．それらの変数で，0 か 1 という 2 つの値のみを持つ変数をビット変数もしくはフラグと呼ぶ． 　フラグは，プログラム実行中に，任意の処理が実行されたかどうか（条件を満たしたかどうか：“オン/オフ”）を記憶させ，後の処理で参照するために用いられる． ▼フラグの定義 　0 か 1 を格納できればよいため，任意の変数の任意ビットを利用できる． 　例えば，変数 mode を定義し，その第 0 ビットおよび第 1 ビットをそれぞれフラグ（フラグ名：F_START，F_RESET）として利用する場合は以下のように定数と変数をセットで定義する．（フラグ名の記述に制約はないが，他の定数や変数と明示的に区別するために，“F_”等を付けるとわかりやすい）． ・フラグビット定義 F_START EQU     00H F_RESET EQU     01H ・フラグビットを含む変数を定義         CBLOC  OCH             mode         ENDC ▼フラグの利用法 　フラグに 0 か 1 を設定するには，通常BSF 命令にとBCF 命令を利用する． ・F_START に 1 を設定         BSF     mode,F_START ・F_RESETに 0 を設定         BCF     mode,F_START 　設定されたフラグの状態を参照して処理を制御するには，分岐処理（レジスタの任意ビットの状態による分岐）を利用する． ・BTFSS を利用した場合         BTFSS   mode,F_START    ;if F_START==1 goto START_on         GOTO    START_off START_on         ;F_START=1         GOTO    PROC_END START_off         ;F_START=0 PROC_END ◆4.3.3　分岐処理 　プログラミングとは，すなわちそのほとんどがプログラムの流れ（分岐処理）を設計することである．したがって，分岐処理の方法をマスターすればプログラミングが容易になる． 　分岐処理は，以下に示すタイプに分類できる．算術演算結果による分岐とレジスタの任意ビットの状態による分岐がある． 　また，算術演算結果による分岐には，大小比較による分岐と零かどうかによる分岐（カウントダウン結果による分岐を含む）に分けて考えることができる． ▼大小比較による分岐 　減算等の結果を利用して分岐する． 　演算結果はSTASTUS レジスタの C ビットで判断する． 　 　例として，変数 data1 と data2 の大きい方を変数 result に格納するコードを考える．　 　data1-data2 を実行したとき： 　・data1≧data2 なら C=1． 　・data1＜data2 なら Ｃ=0． 　C による分岐は BTFSC 命令もしくは BTFSS 命令で行う．両命令は論理が反転しているだけで動作は同様である． 　なお，C ビットが 1 の時は演算結果がおおむね正であると言うことができるが，例えば F0H-20Hの 演算結果は D0（2 の補数形式の場合は負）であるが C=1 となるため，注意が必要である． 　算術加算した場合は，オーバーフロー（加算結果が FFH（255）以上）の場合に C=1 となる． 　 ・BTFSS を利用した場合         MOVF    data2,W         SUBWF   data1,W         BTFSS   STATUS,C         GOTO    D2_GT_D1 D1_GT_D2         MOVF    data1,W         GOTO    PROC_END D2_GT_D1         MOVF    data2,W PROC_END         MOVWF   result ・BTFSC を利用した場合         MOVF    data2,W         SUBWF   data1,W         BTFSC   STATUS,C         GOTO    D2_GT_D2 D1_GT_D1         MOVF    data2,W         GOTO    PROC_END D2_GT_D2         MOVF    data1,W PROC_END         MOVWF   result ▼零かどうかによる分岐 　減算等の結果を利用して分岐する． 　演算結果は STASTUS レジスタのZ ビットで判断する． 　 　例として，変数 data1 と data2 が等しければ data1 を，等しくなければ data2 を変数 result に格納するコードを考える． 　data1-data2 を実行したとき： 　・data1＝data2（差：0）なら Z=1． 　・data1≠data2（差：0以外） ならZ=0． 　Z による分岐は BTFSC 命令もしくはBTFSS 命令で行う． 　また，単に等しいかどうかを調べるのであれば，算術加減算命令以外に XORWF/XORLW 命令も全く同様に利用できる． 　 ・BTFSS を利用した場合         MOVF    data2,W         SUBWF   data1,W         BTFSS   STATUS,Z         GOTO    NOT_ZERO ZERO         MOVF    data1,W         GOTO    PROC_END NOT_ZERO         MOVF    data2,W PROC_END         MOVWF   result ・XORWF を利用した場合         MOVF    data2,W         XORWF   data1,W         BTFSS   STATUS,Z         GOTO    NOT_ZERO ZERO         MOVF    data1,W         GOTO    PROC_END NOT_ZERO         MOVF    data2,W PROC_END         MOVWF   result ▼カウントダウン結果による分岐 　ループ処理ルーチンをプログラミングするには，変数から減算命令で1を減算して演算結果を BTFSC 命令もしくはBTFSS 命令で検査しても良いが，カウンタ専用命令を利用する方法もある． 　 　例として，変数 counter（初期値 20H）を 1 ずつ 0H になるまでカウントダウンし，最終値（0H）を変数 result に格納するコードを考える． 　DECFSZ 命令は，任意のレジスタから1減算した結果が 0 であれば次の命令をスキップするため，ループカウンタの制御をシンプルにプログラミング可能である． 　なお，同様な命令に INCFSZ 命令があるが，こちらはレジスタに 1 を加算した結果が 0（FFH→0Hになった場合）に同様な動作をする． 　 ・DECFSZ を利用した場合         MOVLW   020H         MOVWF   counter LOOP_TOP         DECFSZ  counter,F         GOTO    LOOP_TOP PROC_END         MOVWF   result ▼レジスタの任意ビットの状態による分岐 　BTFSC 命令もしくはBTFSS 命令による分岐処理はSTATUS レジスタ以外のレジスタにも適用できる． 　 　例として，PORTB レジスタの第 0 ビット（RB0）が 1 であれば変数 data1 を，0 であれば変数 data2 を変数 result に格納するコードを考える． 　フローチャートでは，PORTB のデータ入力と第 0 ビットの判断が各々の記号により動作を記述されているが，BTFSS/BTFSC 命令は両動作を単独の命令で実行する． 　なお，PORTB の第 0 ビットは事前に入力ポートの設定がなされていなければならない． ・BTFSS を利用した場合         BTFSS   PORTB,0         GOTO    PB0_LOW PB0_HIGH         MOVF    data1,W         GOTO    PROC_END PB0_LOW         MOVF    data2,W PROC_END         MOVWF   result 　 ■課題 　以下に示す内容のプログラムを作成し，その「フローチャート」と「ソースコード」を示しなさい． プロジェクト名 step04 内容 変数 sum と midsum を定義し，sum には 1 から 10 までの総和をループ処理により求める． midsum には，7を加算した時点の sum の内容（途中結果）を格納する． 　レポートは，下記のWordファイルを使用して作成すること．なるべく簡潔にまとめることが望ましい． 　Form04.docx 　WebClassより期限内に提出すること．