• ベストアンサー

木構造の前置形と行きがけ順について

はじめまして。今データ構造とアルゴリズムを勉強しているのですが、前置形でつまずいてしまいました。以下の問題を解くのですが、いまいち自分で出した答えに自身がないのです。 問題　式((a+b)+c*(d+e)+f)*(g+h)を前置形に変換せよ。 自分は、与えられた式を元に木を再現して、それから行きがけ順に並べたのですが。自信がないところは、ずばり、最初の項で和が３つあるところなんです。考え方の一つとして、枝分かれを３つという考え（すなわち、*++ab*c+def+gh）と、３つを一つの和ともう２つの和と分けて考える（すなわち*++ab+*c+def+gh）のと、どちらが正解なのでしょうか？といいますのも、defのところで、今度は逆に前置形からもとの式を作り直すときに違う式ができるのでは、と思うからです。 よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.5

2番の補足です。 　　　　　　　　　　＊ 　　　　　　　　／　　　＼ 　　　　　　　＋　　　　　＋ 　　　　　　／　＼　　　／　＼ 　　　　　＋　　　ｆ　　ｇ　　　　　ｈ 　　　／　　　＼ 　　＋　　　　　＊ 　／　＼　　　／　＼ ａ　　　　ｂ　ｃ　　　　　＋ 　　　　　　　　　　　／　＼ 　　　　　　　　　　ｄ　　　　ｅ ですよね？

ikecchi
質問者

お礼

はいありがとうございます。図まで載せてもらいありがとうございます。感謝です☆

全文を見る
すると、全ての回答が全文表示されます。

その他の回答 (4)

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.4

式((a+b)+c*(d+e)+f)*(g+h)を前置形に変換せよ。 これを前置系に変換すると *+++ab*c+def+gh これを元に戻すと ((a+b)+c*(d+e)+f)*(g+h) となってきちんと戻り何の問題もありません。

全文を見る
すると、全ての回答が全文表示されます。
  • BLUEPIXY
  • ベストアンサー率50% (3003/5914)
回答No.3

＃１は、勘違いしていました Ａ＋Ｂ＋Ｃを ＋ＡＢＣとするか ＋＋ＡＢＣまたは＋Ａ＋ＢＣとするかって話ですね。 （私は後者の話だと思っていました。） ＋は普通に考えたら２項演算子ですので、 ＋ＡＢＣとは出来ません ＋（ＡＢＣ）と表記するとか拡張が必要だと思います。 でないと質問者も言っている通り元には戻りません。

全文を見る
すると、全ての回答が全文表示されます。
回答No.2

普通は２分木で考えるので　*++ab*c+def+gh　はありえないと思います。(+が１個少ないですよね？)

ikecchi
質問者

お礼

ありがとうございます。普通は２分木を考えるのですか？

全文を見る
すると、全ての回答が全文表示されます。
  • BLUEPIXY
  • ベストアンサー率50% (3003/5914)
回答No.1

どっちでも数式としての評価は同じだと思いますが、 要は A+B+C を (A+B)+Cとするか A+(B+C)とするか って意味の様に思えます。 数学的には、 (A+B)+C=A+(B+C)だと思いますので、どちらでもいいのでしょうが プログラム的には ＋の優先順位は同等なのでどちらでもいいですけど 基本的には、左から評価するという規則が使われることが多いと思います。 その場合は、 (A+B)+C ってことになりますね。 元の式が作り出せるかどうかというのは、 要は（）のくくりが戻せるかということでもあると思いますが （Ａ＋Ｂ＋Ｃ）の部分は、（）が使われていないので、厳密には同じ式に戻らない（どこに（）が使われてあるいは使われていないかという情報が失われている）と思います。 いずれにしても、式全体としては、正しいものに戻せるとは思いますが。

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 高速な和積形命題論理式の含意関係判定法

    ２つの和積形命題論理式が与えられています。 この２つの式に含意関係が成り立つか判定したいのです。 この問題はco-NP完全問題でまともにやるととても時間がかかります。そこで次のような条件を満たすアルゴリズムを考えてください。 １．アルゴリズムが含意関係がなりたつと答えたときは必ず含意関係が成り立つ。 ２．アルゴリズムが含意関係が成り立たないと答えたときは含意関係が成り立ってても成り立たなくてもよい。 ３．入力の多項式時間で停止する。 この条件だけだと常に含意関係が成り立たないと 答えるアルゴリズムでもOKになってしまいますが もちろん本当に含意関係が成り立つときはなるたけ含意関係が成り立つと答えてほしいわけです。 私が考えたのは和積形の論理式ｆ、ｇがあたえられたとしてfのすべての和項に対してgにそれを含意する和項があったらgはｆを含意するというものです。 これよりもよい方法を考えてください。 よろしくお願いします。

  • 数列の和の一般項について　テスト前！！

    今回の問題）１,１+３,１+３+９，１+３+９+２７ という数列の初項から第n項までの和なんですが、 なんか基本的な 1・２・３ + ２・３・５ + ３・４・７ よってΣk(k+1)(k+2) みたいなのとは違って 最初の一般項の出し方が特殊みたいですが その式が理解できないです。 一般項＝１+３+９+・・・+３^(k-1) ＝３^k－１/３-1＝　１/２・（３^k－１） 一般項が等比数列になってるみたいですが、この一般項って問題の式の一つ一つの項の一番右の値だけとってつくってるみたいですが なんでこうなるのかわかりません。 Σ1/2・(３^k-1)

  • 数列の問題です（SPI)

    SPIの問題です。 数が次のように並んでいます。 　３、９、２７、８１、２４３、… (1)第６項はいくらか (2)第１項から第６項までの和はいくらか この問題でしたら計算で何とか解けるのですが、もっと高度（例えば第１５項を求めよ、とか、第１項から１５項までの和といった問題）になると、やり方がわかりません。３の累乗の数列ですが、どなたか、この数列の一般項やｎ項までの和を求める式や効率のよいやり方をご教示頂けますでしょうか。宜しくお願いします。

  • BNF記法について

    最近質問させていただいたものですが、また分からな いことがあり、質問させてください。 ある、アルゴリズムの問題集をやっていて、BNF記法に 従った数式を解析して計算するというものでした。 BNFの定義として、 式＝項 | 式 加法演算子 項 項＝因子| 項　乗法演算子　因子 因子＝数 加法演算子＝'+'|'-' 乗法演算子＝'＊'|'/' となっています。 そのテキストで、例として、 項＝3*4/5 というのがありました。これは理解できました。しかし、 式＝1+2+3*4/5-6 というのが理解できません。 式＝式 加法演算子 項　と、項＝項　乗法演算子 　因子 というのを再帰的に当てはめていくのだと思うのです が、式として成立させるのは定義からして無理だと 思うのですが。1+2+3*4/5-6を式として解釈するには どのようにしたらよいかお教えください。よろしく お願いいたします。 ちなみに、1+2+3*4/5-6は、問題集に載っているアルゴリズムで問題なく解けました。 　

  • 数学Ｂの数列の問題です。

    【問題】 等比数列{1,25,25^2,25^3,25^4,……}の初項から第n項までの和は,等比数列{1/3,2/3,3/3,4/3,5/3,……}の初項から第何項までの和に等しいか。nの式で答えよ。 [自分なりの解答] まず等比数列の一般項をan=25^(n-1)と表す。 次に等差数列の一般項をbm=（1/3）mと表す。 そして和の公式で それぞれSn（和）,Sm（和）を出してイコールで結んでみたのですが…＾＾； できないんですよ＾＾； これでいいのか？という答えになってしまって…。 たぶんやり方が間違っているので 解き方を教えてください。 よろしくお願いします。

  • 数学の問題教えてください。

    以下の問題を途中式も含めて教えていただきたいです。よろしくお願いします。 初項-21、公差2の等差数列{an}に対して: (1)初項から第5項までの数値を求めよ、更に第n項anをnの式で表せ。 (2)初項から第n項までの和をnの式で表せ。 (3)初項から第n項までの和が48となるようなnの値を求めよ。

  • nCm が偶数

    n=2^k(k≧1)とすると、　nCm (1≦m≦n-1)は偶数であることをしるせ。 証明では (A+B+C+・・・・Y+Z)^2 =A^2+B^2+C^2+・・・Y^2+Z^2+2(AB+AC・・・+AY+AZ・・・+YZ)・・・(1) を使って 例えばn=4のとき、(a+b)^4=a^4+(係数が偶数の項)+b^4がわかれば、n=8のとき、 (a+b)^8={(a+b)^4}^2={a^4+(偶数係数項の和)+b^4}^2=a^8+(偶数係数項の平方和)+b^8 +2(異なる２項の積全体の和) =a^8+(係数が偶数の項)+b^8　となるので、n=8でも成り立つことがわかる。 と書いてあります。 (1)を使って具体的に計算したら、 (a+b)^2=a^2+2ab+b^2を2乗して(a+b)^4を表すと、 a^4+4a^2b^2+b^4+2(2a^3b+a^2b^2+2ab^3) また上記の結果を２乗して(a+b)^8を表すと、 a^8+16a^4b^4+b^8+4(2a^3b+2ab^3+a^2b^2)^2+2{4a^6b^2+a^4b^4 +a^4*2(2a^3b+2ab^3+a^2b^2) +4a^2b^6+4a^2b^2*2(2a^3b+2ab^3+a^2b^2) +b^4*2(2a^3b+2ab^3+a^2b^2)} どこが、係数が偶数の項、偶数係数項の和、偶数係数項の平方和であるかがわかりません。 次に、a^4・・・を２乗するときに(係数が偶数の項)は(偶数係数項の和)に書かれていて、 どっちが正しいかわかりません。 どなたか２つの質問に説明をください。お願いします。 本では、このあと数学的帰納法を使って、条件が成り立つとき、nCmが偶数であることをしるしています。

  • 数列

    自然数nがn＾2個ずつ続く数列 1,2,2,2,2,3,3,3,3,3,3,3,3,3,4…… において、第400項を求める。 また、初項から第400項までの項の和を求める。 1/6(N-1)N("N-1)<400≦1/6N(N＋1)(2N＋1) N=11となることは流れで理解できたのですが 初項から第400項までの項の和を求める方法がわかりません。 Sk=K＾3なのですか？ 問題は2乗なのに、求める式は3乗なのですか？ Σ(k=1～10)k^3 ＋ 11×15 式の11×15は理解でしたが k＾3の由来が でもこれは第1群から第10群までの和なんですよね。 　

  • 夏休み課題…

    以下の問題を妹に質問されたのですが、答えは出るのですが良い教え方、式の立て方が出来ずにいます。 (1)第４項が２/９、第８項が１８である等比数列の第６項を求めよ。 (2)３で割れば２余り、尚且つ、４で割れば３余るような二桁の自然数の和を求めよ。 (3)第２項が２で、初項から第３項までの和が７である等比数列の初項と公比を求めよ。 宜しくお願い致します。

  • 数列

    ｛１｝，｛１，４｝，｛１，４，９｝，｛１，４，９，１６｝・・・ がある。この数列の第１００項および初稿から第１００項までの和を求めよ。 前者は、第１００は第１４群の９番目なので、９の２乗で８１とわかりました。（ｎ群の一般項がn^2より。） 後者ですが、第ｎ群の中での和を求めて問題の数列の一般項【1/6(n+1)(2n+1)】・・・(1)をもとめて、問題の数列の和は【1/12n(n+1)^2(n+2)】・・・(2)とだして、 １３群までの和は３１８５、１４群の９番目までの和が２８５で足して答えは３４７０。 と導いたのですが、遠回りの解答になってないでしょうか・・・？ というのも、(2)式にｎ＝１３を代入して計算するのが結構複雑だからです。。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する