1: 2016-07-26 (火) 21:14:22 osinko  |
2: 2016-07-27 (水) 00:11:21 osinko |
| | TITLE:式木、二項演算、括弧のネスト処理 | | TITLE:式木、二項演算、括弧のネスト処理 |
| | + | #jsmath |
| | **式木、二項演算、括弧のネスト処理 [#a7139d8b] | | **式木、二項演算、括弧のネスト処理 [#a7139d8b] |
| | | | |
| - | ネットをぶらぶら散策していると面白い問題を見つけた。以下のリンクのページにその問題はある | + | ネットをぶらぶら散策していると面白い問題を見つけた。25年前に活躍していた低価格パーソナルコンピュータMSXを扱った雑誌で、その標準機能だったBASICを使って問題を解くというクイズ記事。以下のリンクにそのページが公開されている |
| | [[MSX_Magazine_1991-12_ASCII_JP:https://archive.org/stream/MSX_Magazine_1991-12_ASCII_JP#page/n93/mode/2up]] | | [[MSX_Magazine_1991-12_ASCII_JP:https://archive.org/stream/MSX_Magazine_1991-12_ASCII_JP#page/n93/mode/2up]] |
| - | 論理や算術演算を自動生成して目的に合わせ問題を解くという問題のようだ。非常に興味深いのでちょっと考えてみる事とする | + | 論理や算術演算を自動生成して目的に合わせ解く問題。非常に興味深いのでこの問題を解いてみる |
| | + | |
| | + | 資料：[[MSXマガジン_バックナンバーアーカイブ:https://archive.org/details/msxmagazinejp]] |
| | | | |
| | ***問題 [#cf6bd2ed] | | ***問題 [#cf6bd2ed] |
| | | | |
| | ＜ルール＞ | | ＜ルール＞ |
| - | ①＋－×÷の記号のみ使用できる事とする。ルートやべき乗は使用不可 | + | +＋－×÷の記号のみ使用できる事とする。ルートやべき乗は使用不可 |
| - | ②計算は一般の式と同じ順序で行う（×÷が優先、左から右に計算する） | + | +計算は一般の式と同じ順序で行う（×÷が優先、左から右に計算する） |
| - | ③（）は使用できる | + | +（）は使用できる |
| - | ④最初の数字の頭に－を付けて負の数にすることは出来る | + | +最初の数字の頭に－を付けて負の数にすることは出来る |
| - | ⑤数字の並べ替えは出来ない | + | +数字の並べ替えは出来ない |
| - | ⑥二つ以上の連続する数字をまとめて2桁以上の数として扱うことは出来ない | + | +二つ以上の連続する数字をまとめて2桁以上の数として扱うことは出来ない |
| | | | |
| | + | **問題解決の履歴 [#p24e82e6] |
| | | | |
| - | ***①と②について [#f61c996d] | + | この問題をエレガントに解く方法があるかもしれないが、筆者には全く思いつかない |
| - | -算術演算処理（calculate）には二項演算の二分岐、式木の仕組みを利用してプログラム処理する | + | なので一般的に[[ブルートフォース:https://ja.wikipedia.org/wiki/%E7%B7%8F%E5%BD%93%E3%81%9F%E3%82%8A%E6%94%BB%E6%92%83]]と呼ばれる総当たり、力技で強引に問題を解決する手法を選択する |
| | + | この章では問題の各ルールに対して、どう対処するかの基本方針を固める |
| | | | |
| - | ***③について [#uc05ee4d] | + | ***1.と2.について [#f61c996d] |
| - | -括弧を使ったネストのある数式を解析処理（Parse）する必要がある | + | -算術演算処理（calculate）には二項演算の二分木、式木の仕組みを利用してプログラム処理する |
| - | -全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧が多いという式は成立できないので処理しない | + | -四則演算の優先順位に従って式木を組むコードを作る |
| - | -考えられる括弧式を抽出してリスト化。式木をあらかじめ組んで個別に処理する方針で行く | + | |
| | | | |
| - | ***④⑤⑥について [#sf2a74f5] | + | 資料： |
| | + | -[[二分木を使った数式の逆ポーランド記法化と計算:http://smdn.jp/programming/tips/polish/]] |
| | + | -[[C#のコード:http://smdn.jp/programming/tips/polish/impl_cs/]] |
| | + | |
| | + | ***3.について [#uc05ee4d] |
| | + | -括弧を使ったネストのある数式を解析処理（Parse）する必要がある。文字列として数式を受け取り解析する処理は上記の資料内にあるが、括弧の処理に関しては詳しくは書かれていない。またこの問題に合わせた改良が必要。具体的には４桁の数字に対する括弧の作り方を適切に出力する必要がある |
| | + | -全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧が多いという式は成立できないので、そういうものはエラーとして処理を省く |
| | + | -考えられる括弧式を抽出してリスト化。式木をあらかじめ組んで、そのひな形に対し変化部分をはめ込んで個別に処理する方針で行く |
| | + | |
| | + | ***4.5.6.ついて [#sf2a74f5] |
| | -四則演算子＋－×÷は算術演算子でもあり二項演算子である。A×BやA+Bのように二項の演算を扱う | | -四則演算子＋－×÷は算術演算子でもあり二項演算子である。A×BやA+Bのように二項の演算を扱う |
| - | -＋－は単項演算子でもある。－xは単項で負符号を表す。x－yは二項演算。－x－yはこれら機能が複合している | + | -＋－は単項演算子でもある。－xは単項で負符号を表す。x－yは二項演算。－x－yはこれら機能が複合していると考える |
| | -＋は省略できるが、－は省略できない | | -＋は省略できるが、－は省略できない |
| | | | |
| | 解決方法 | | 解決方法 |
| - | 最初の数字を整数Z。２番目以降を自然数として扱い処理することで解決する | + | \(a\cdot b\cdot c\cdot d\) の四則演算に対して \(-a\cdot b\cdot c\cdot d\) のケースの為に最初の数字を整数\(\mathbb{Z}\)。２番目以降を自然数\(\mathbb{N}\)として扱い処理することで解決する |
| - | | + | |
| - | \(a\cdot b\cdot c\cdot d\)の四則演算に対して\(-a\cdot b\cdot c\cdot d\)のケースの為に | + | |
| - | \(a=\left\{ \quad k\quad |\quad -9\le k\le -1\quad ,\quad 1\le k\le 9\quad \right\} \\ b,c,d=\left\{ \quad k\quad |\quad 1\le k\le 9\quad \right\} \) | + | |
| - | とする | + | |
| | | | |
| | **掘り下げて考える [#d975c324] | | **掘り下げて考える [#d975c324] |
| | | | |
| - | 難しいのは「①と②について」と「③について」の問題となっている。 | + | 仕組みを掘り下げて考えてみる。まず４桁の四則演算を以下のように考えるとする |
| | + | |
| | + | \(a①b②c③d\) |
| | + | |
| | + | \(a=\left\{ k|-9\le k\le -1,1\le k\le 9 \right\} \\ b,c,d=\left\{ k|1\le k\le 9 \right\} \\ ①,②,③=\left\{ +,-,\times ,\div \right\} \) |
| | + | |
| | + | つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9～9までの数。b,c,dは1～9までの数となる |
| | + | ルール1.2.の処理に関しては式木で対応する事で解決する。具体例を書くと・・・ |
| | + | |
| | + | |
| | + | |
| | + | 次にルール3.の括弧の処理を考える。例えば二項結合子と左右の二項を一ブロックに考えて \(a①b\) という式があった場合、これに括弧を付けると \((a①b)\) になる。\(a①b②c\) の場合に括弧を付ける場合、一番外側の括弧を省いて表すなら \((a①b)②c\) か \(a①(b②c)\) となる。このことから、二項結合子を挟んだ２項に対して左右に括弧で囲めば式を生成できる。そこで①をtrue,falseを持つフラグだと考える |
| | + | |
| | + | ①がfalseの時は |
| | + | \(a①b②c③d\) |
| | + | |
| | + | ①がtrueの時は |
| | + | \((a①b)②c③d\) |
| | + | |
| | + | このルールに従って表を作ると以下のようになる |
| | + | |
| | + | |①②③| | | | |
| | + | |000|a①b②c③d| | | |
| | + | |001|a①b②(c③d)| | | |
| | + | |010|a①(b②c)③d| | | |
| | + | |100|(a①b)②c③d| | | |
| | + | |101|(a①b)②(c③d)| | | |
| | + | |011|a①(b②(c③d))|a①((b②c)③d)| | |
| | + | |110|((a①b)②c)③d|(a①(b②c))③d| | |
| | + | |111|(a①(b)②(c)③d)| |表記不能| |
![[PukiWiki]](http://unitylabo.s601.xrea.com/xoops/modules/xpwiki/image/pukiwiki.png "[PukiWiki]")
