ULprojectのホームページ © ULproject

2022/1/27(木) N88-BASIC、C、アセンブラでBinary search   Binary search( 二 分探索)のアルゴリズム   以後、探したい値をキーと呼ぶことにします また、データは昇順に並び替えられているものとします 1. 要素の中央位置の値が探したい値なら終了 2. キーが中央位置の値より小ならそれより左を新たな要素にし    キーが中央位置の値より大ならそれより右を新たな要素にし 3. 1.2.を要素がなくなるまで繰り返す となります   例  0  1  2  3  4 (要素番号) 11 15 18 20 23 (要素) … A(0) = 11, A(1) = 15, ... から、キー15の要素番号を得るとします   L = 0, R = 4とし、M = [(L + R) /2] = 2 A(M) = A(2) = 18なので 15 < A(M)より 新たな要素はA(M)より左 L = 0, R = M-1 = 1、M = [(L + R) /2] = 0 A(M) = A(0) = 11なので 15 > A(M)より 新たな要素はA(M)より右 L = M+1 = 1, R = 1、M = [(L + R) /2] = 1 A(M) = A(1) = 15なので 15 = A(M)より要素番号1を返す   N88-BASICでは、途中経過を色付きで表示しています n:nは検索回数 青:検索範囲外 黄:検索範囲内 白:検索中   結果 白:キーの要素番号 赤:キー以外の要素番号   途中経過で黄色の範囲が約半分ずつ狭くなっていく 様子が分かると思います     C、Assemblerでは、途中経過の表示は省いています Enterのみの入力で終了します   NL-BASICとblg～.zip (bsrch001.bas、bsrch001.c、bsrch001asm.c)は このブログ(以下のリンク)からダウンロードできます https://ulprojectmail.blogspot.com Readme.txtを読んで遊んで下さい

N88-BASIC、C、アセンブラでQuick sort   Quick sort(並替え)   N88-BASIC、C C(ポインター)、アセンブラ(8086系) でプログラミング   クイックソートは再帰的に定義すると   1. 要素か1個以下なら以下を操作しない 2. 基準となる数値を決める 3. 基準となる数値より小さい集合と大きい集合に分ける 4. 小さいものに1.～5.を適用する 5. 大きいものに1.～5.を適用する   となります   QSORT(数の集合)を、ある数より小さいものと 大きいものに分ける操作とする   QSORT(数の集合)   数の要素が1個以下ならQSORT終了   基準となる数値を決める   基準となる数値より小さい集合と大きい集合に分ける   QSORT(小さい集合)   QSORT(大きい集合) で並替る事ができます   {8 5 3 2} を昇順に並替えをしてみます   QSORT({8 5 3 2})   要素数4個なので以下の操作をする   中央付近の5を基準に選ぶ   5より小と大の2グループに分ける   つまり、{3 2} {8 5}に分ける   ({3 2} 5 {8} や {3 3 5} {8} に分けても良い)   QSORT({3 2})   QSORT({8 5}) {3 2} {8 5}   QSORT({3 2})   要素数2個なので以下の操作をする   中央付近の3を基準に選ぶ   3より小と大の2グループに分ける   {2} {3}   ({} {3 2} や {3 2} {} とすると終わらない)   QSORT({2})は要素数1個なので何もしない   QSORT({3})は要素数1個なので何もしない   {2} {3} {8 5}   QSORT({8 5})は同様に   {2} {3} {5} {8} となるり、小さい順(昇順)に並んでいます   8   5   3   2  を、基準5で小、大に分ける 3   2 | 8   5  それぞれ3や8で小、大に分ける 2 | 3 | 5 | 8 で並替えできます   分ける基準となる数値の決め方は色々ありますが 今回は中央付近の位置にある数にしています   クイックソートは基準の選び方と、データの並びの 相性によって、ソートにかかる時間が変

2022/1/21(金) N88-BASIC、C、アセンブラで階乗 (2回目)   再帰   N88-BASIC、C、インラインアセンブラ(8086系) で階乗を求めるプログラムを、再帰で作ってみます   関数やサブルーチン内から自身を呼出す 事を再帰呼出しといいます     C、インラインアセンブラは、 Cコンパイラーなどを準備して下さい 例、Microsoft Visual Studioなど windowsのconsoleアプリは実行終了後 ウインドウが閉じてしまうので 最後にキー入力待ちを入れています 数値を入れてenterを押すと終了します 関数名に_sが付いているものは_sを 消した関数名でも良いのですが、 エラーが出る場合があるので、 環境に合わせて選択してください     階乗に関しては、 N88-BASIC、C、アセンブラで階乗(通常) を参照して下さい   階乗の再帰定義 n! = n×(n-1)! 7! = 7×6!    = 7×6×5×4×3×2×1 = 5040   PCの変数の桁には限界がありますので ここでは大きな数の階乗には対応しません nは1桁位と思って下さい   BASICにはローカル変数が無いので 配列で代用しています   Cは再帰の方がすっきりします   インラインアセンブラ(8086系) ローカル変数をスタック(push pop)で 実現しています (Cのローカル変数はアセンブラのスタック で実現されています)   ～.cのファイルはTab=4で書いています (メモ帳はTab=8なのでズレます)   NL-BASICとblg～.zip (fact002.bas、fact002.c、fact002asm.c)は このブログ(以下のリンク)から ダウンロードできます https://ulprojectmail.blogspot.com Readme.txtを読んで遊んで下さい

2022/1/17(月) N88-BASIC、C、アセンブラで階乗 (1回目)   N88-BASIC、C、インラインアセンブラ(8086系) で階乗を求めるプログラムを、 作ってみます   C、インラインアセンブラは、 Cコンパイラーなどを準備して下さい 例、Microsoft Visual Studioなど windowsのconsoleアプリは実行終了後 ウインドウが閉じてしまうので 最後にキー入力待ちを入れています 数値を入れてenterを押すと終了します 関数名に_sが付いているものは_sを 消した関数名でも良いのですが、 エラーが出る場合があるので、 環境に合わせて選択してください     階乗の通常の定義 n! = n×(n-1)×...×1 7! = 7×6×5×4×3×2×1    = 1×2×3×4×5×6×7 = 5040   A,B,C3人の並べ方は 1列目はA,B,Cの3通り 2列目は残り2人の2通り 3列目は残り1人の1通り なので3×2×1=6通り   n人の並べ方はn!通りあります   PCの変数の桁には限界がありますので ここでは大きな数の階乗には対応しません nは1桁位と思って下さい   ～.cのファイルはTab=4で書いています (メモ帳はTab=8なのでズレます)   NL-BASICとblg～.zip (fact001.bas、fact001.c、fact001asm.c)は このブログ(以下のリンク)から ダウンロードできます https://ulprojectmail.blogspot.com Readme.txtを読んで遊んで下さい