式木、二項演算、括弧のネスト処理
のバックアップソース(No.3)
Unity学習帳2冊目
式木、二項演算、括弧のネスト処理
のバックアップソース(No.3)
[
トップ
] [
差分
|
バックアップ
|
リロード
] [
新規
|
一覧
|
検索
|
最新
|
ヘルプ
]
[ ]
差分
を表示
現在との差分
を表示
式木、二項演算、括弧のネスト処理
へ行く。
« Prev
Next »
TITLE:式木、二項演算、括弧のネスト処理 #jsmath **式木、二項演算、括弧のネスト処理 [#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マガジン_バックナンバーアーカイブ:https://archive.org/details/msxmagazinejp]] ***問題 [#cf6bd2ed] 0000~9999までの4桁の数の間に四則演算を入れて10が作れないものはいくつあるか?プログラムで求めよ <ルール> ++-×÷の記号のみ使用できる事とする。ルートやべき乗は使用不可 +計算は一般の式と同じ順序で行う(×÷が優先、左から右に計算する) +()は使用できる +最初の数字の頭に-を付けて負の数にすることは出来る +数字の並べ替えは出来ない +二つ以上の連続する数字をまとめて2桁以上の数として扱うことは出来ない **問題解決の履歴 [#p24e82e6] この問題をエレガントに解く方法があるかもしれないが、筆者には全く思いつかない なので一般的に[[ブルートフォース:https://ja.wikipedia.org/wiki/%E7%B7%8F%E5%BD%93%E3%81%9F%E3%82%8A%E6%94%BB%E6%92%83]]と呼ばれる総当たり、力技で強引に問題を解決する手法を選択する この章では問題の各ルールに対して、どう対処するかの基本方針を固める ***1.と2.について [#f61c996d] -算術演算処理(calculate)には二項演算の二分木、式木の仕組みを利用してプログラム処理する -四則演算の優先順位に従って式木を組むコードを作る 資料: -[[二分木を使った数式の逆ポーランド記法化と計算:http://smdn.jp/programming/tips/polish/]] -[[C#のコード:http://smdn.jp/programming/tips/polish/impl_cs/]] ***3.について [#uc05ee4d] -括弧を使ったネストのある数式を文字列として受け取り解析処理(Parse)する必要がある。処理のサンプルは上記の資料内にある。しかし括弧の処理に関しては詳しくは書かれていない。この問題に合わせた改良が必要。具体的には4桁の数字に対する括弧の作り方を適切に出力する必要がある。文字列でなく式木の形で渡しても良いかもしれない -全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧が多いという式は成立できないので、そういうものはエラーとして処理を省く ***4.5.6.ついて [#sf2a74f5] -四則演算子+-×÷は算術演算子でもあり二項演算子である。A×BやA+Bのように二項の演算を扱う -+-は単項演算子でもある。-xは単項で負符号を表す。x-yは二項演算。-x-yはこれら機能が複合していると考える -+は省略できるが、-は省略できない 解決方法 \(a\cdot b\cdot c\cdot d\) の四則演算に対して \(-a\cdot b\cdot c\cdot d\) のケースの為に最初の数字を整数\(\mathbb{Z}\)。2番目以降を自然数\(\mathbb{N}\)として扱い処理することで解決する **掘り下げて考える [#d975c324] 仕組みを掘り下げて考えてみる。まず4桁の四則演算を以下のように考えるとする \(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)\) となる。このことから、二項結合子を挟んだ2項に対して左右に括弧で囲めば式を生成できる。そこで①を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)| |表記不能|
« Prev
Next »
式木、二項演算、括弧のネスト処理 のバックアップ一覧
式木、二項演算、括弧のネスト処理 のバックアップソース(No. All)
1: 2016-07-26 (火) 21:14:22
osinko
2: 2016-07-27 (水) 00:11:21
osinko
3: 2016-07-27 (水) 00:56:03
osinko
4: 2016-07-27 (水) 10:19:56
osinko
5: 2016-07-27 (水) 23:38:31
osinko
6: 2016-07-28 (木) 23:15:24
osinko
7: 2016-07-29 (金) 09:12:30
osinko
8: 2016-08-03 (水) 21:36:13
osinko
9: 2016-08-04 (木) 01:03:53
osinko
現: 2016-08-04 (木) 11:20:26
osinko