代数方程式

質問

一汎にn次方程式(n=1,2,3,4)を解くために昇巾又は降巾の順に整理する必要があると思いますがこの整理するまでのアルゴリズムはどのように記述できるでしょうか？

回答No.4

uyama33 · ベストアンサー

０．式をメモリーにしまう
１．字句解析を行う
２．構文解析を行う（正しい式であることの確認）
３．多項式のためのメモリー配列を各項ごとに用意する
４．各項の次数を調べて適当な場所に格納
５．次数を考えて配列を足し算する。
こんなところでしょうか。
コンパイラ作成の本を読めば
作れます。
構文解析
や
コンパイラコンパイラ
で検索してください。
．．
方程式については
数値解析の本を調べると
複素係数のn次方程式の近似解方が載っています。

お礼

ありがとうございます.
お礼が遅れてすみませんでした.

０．式をメモリーにしまう
１．字句解析を行う
２．構文解析を行う（正しい式であることの確認）
３．多項式のためのメモリー配列を各項ごとに用意する
４．各項の次数を調べて適当な場所に格納
５．次数を考えて配列を足し算する。

を詳細に適用してアルゴリズムを完成させたいと思っています.主に2.についてですが、私は次のようなテーブルデータを作るのがいいと思います.

3x^3+(x+1)^3-(2x+5)^2+(6x^2-3x+7) を例にすると
式ID　　　　　式　　　　式のクラス
　1　　　　　3x^3　　　　単項式
　2　　　　　+:3,4,5　　　結合子
　3　　　　　x　　　　　　単項式
　4　　　　　1　　　　　　単項式
　5　　　　　3:2,+,3　　　　指数
　6　　　　　2x　　　　　　単項式
　7　　　　　5　　　　　　単項式
　8　　　　　2:5,6　　　　指数
…
多項式に指数があれば展開して指数をなくす

回答No.6

uyama33

正しい式でも
ｘ＾２＾３＾４
の様なものを考えると
これは
ｘ＾（２＾（３＾４））
となり、右から計算します。
この扱いが面倒なので
私なら、構文解析ルーチンを作って
処理します。
私は、ＬＬ（１）文法を使っています。
LALRのほうが一般的かも知れません。

お礼

ご回答して下さった皆様、ありがとうございます.
まだ、解決していませんが、いったん打ち切って、整理して再度質問したいと思います.

回答No.5

rabbit_cat

１． 積を展開
２． 和・差を計算
を単純な降巾の形になるまで繰り返せばいいだけでは。

１の積の展開は、単純に分配則を使って、
(ax^2+bx+c)g(x) = ax^2f(x) + bxf(x) + cg(x)
みたいに、一方の多項式を展開していけばいいです。

２の和・差の計算は、単にxの次数が同じ項の係数同士を足し算・引き算するだけですね。

１、２、を可能な間は繰り返せば、自然に降巾（昇巾）になります。

回答No.3

oyaoya65

質問者さんが自分で解くつもりで対象とする式を定義して、アルゴリズム案を示して質問してください。

式の対象は質問者さんが定義しないと回答者は回答できません。

すべての係数の定義について
実数の範囲
複素数の範囲
整数の範囲
有理数の範囲
無理数の範囲
などを明らかにしないと
アルゴリズムが変わってきます。

質問者さんがご自分でアルゴリズム案を作成されればこのような定義がないといけないことは分かると思います。

整数係数なら、係数の共通因数で割ることが必要になりますし、実数係数なら最高次の係数ですべての係数を割ることをして根の公式を適用することになります。
有理数係数、無理数係数の場合は最高次の係数で割ったとして解を厳密解（有理数や無理数交じりの形式）解で求めるならば、係数の計算が有理数計算や無理数の計算や有理化計算をするアルゴリズムが必要となってきます。
小数点を使った実数解（数値解＝近似解）を求めるのであれば有理数や無理数の計算アルゴリズムも不要になります。

まず、以上のようなことを整理して、どのような係数の方程式を対象にするかを明確にし、それに基づいてアルゴリズムを考えれば、自ずとアルゴリズムが考えられると思いますが....。

お礼

ありがとうございます.
>対象とする式を定義して
No2のお礼でも書きましたが要するに任意の形をした多項式で係数に文字が使われる場合もありうる（なしで考えてもいいですが）.指数は具体的な自然数が与えられている.
そのような形の式を降巾または昇巾の順に整理するアルゴリズムです.

ご指摘のように係数の範囲についても実際にプログラムを作る段階になれば区別する必要があると思いますが、それを考えてしまうと本質が見えなくなりそうなので、係数は具体的な数か文字で表されているかだけを計算機が区別できるものと仮定しておきます.もっと言うと計算機は処理において文字を係数かx（未知数）か指数かだけを区別するものと仮定して考えてもいいと思います.

回答No.2

graphaffine

プログラムに関する話でしたら、多項式をどのような形式で扱うかがはっきりしてないとだめですよね。
その形式によっては、ご質問のアルゴリズム云々は意味がなくなると思います。
それとも、方程式を解く以前の多項式の入力方法等にかかわる話ですか。

お礼

ありがとうございます.

>多項式をどのような形式で扱うかがはっきりしてないとだめですよね。
多項式の表記の仕方を決めたいと思います.
まず、計算機に多項式は
(1)　xの多項式と認識させます.
　　それ以外に使われている文字は係数とみなします.
(2)　f(x)はax^n の形の単項式が任意個、和または差で
　　つながった形で表記されている多項式とします.
(3)　g(x)は(2)のf(x)の形で表される多項式が任意個
　　和または差または積または自然数乗の組合わせで
　　表された形の多項式だとします
このとき入力されたg(x)の形の多項式を降巾または昇巾の順に整理するアルゴリズムを知りたいのです.なお自然数乗の指数は文字でなく必ず具体的に自然数が当てられるものとして考えておくことにします.

よろしくお願いします.

回答No.1

quantum2000

ご質問の内容がいまいち良く判らないのですが、具体的な例で説明していただくと、どうなりますか？

お礼

ありがとうございます.
　例えば
　2x+3-3(6x+4)=1　という方程式を解くときに
式変形して　
　-10x-10=0 －(1)
として解の公式より
　x=-(-10)/(-10)=-1
とプログラムを作って自動的に求めるようにしたいのです.
ですから与えられたn次方程式(n=1から4)に対して(1)のように変形するプログラムをどう記述したらよいか悩んでいます.ちなみに多項式環の理論で多項式の意味はきちんと説明されてますが、それをどう活かせばいいのかなとか思っています.