HOME»基本情報技術者試験掲示板»平成21年秋期午後問8

基本情報技術者試験掲示板

掲示板検索:

[3599]平成21年秋期午後問8

 オームさん(No.1) 
午後・アルゴリズムの問題で質問です。
ニュートン法に関する問題で空欄CとDがよくわかりません。
具体的には
>演算回数を減らす工夫をしている
抽象的にはどんな工夫をしているのですか?
どんなプログラムであるかの説明をお願いします。
他のスレッドを参照しましたが飲み込みが悪くてすみません。
お願いします。
https://www.fe-siken.com/kakomon/21_aki/pm08.html
2021.09.15 00:11
名無しさん(No.2) 
> どんなプログラムであるか
方程式の解を求めるアルゴリズム、と問題文に記載がありますが。
2021.09.15 09:13
 オームさん(No.3) 
聞き方が悪かったです。すみませんでした。
単純に空欄Cと空欄Dの行は何の処理をしているのかという
C、Dの解説をしていただければ嬉しいです。
2021.09.16 23:28
かなさん(No.4) 
FE・ブロンズエキスパート
まず、空欄CDは変数dに代入する処理なので、〔アルゴリズム2の説明〕(3)Aの処理に関係するのだと気づけないといけません。

---------------------------

>  また,行番号13〜18は,アルゴリズム2の手順(3)の@とAの処理である。
>  プログラム1では,例えばfの値a3x3+a2x2+a1x+a0を求める式を,
>  
>      f←((a3×x+a2)×x+a1)×x+a0
>  
>  と変形して,演算回数を減らす工夫をしている。

〔プログラム1〕10行目は、変数fに代入する処理なので、〔アルゴリズム1の説明〕(3)@に対応します。
素直に書けば、
> a_3 * x * x * x + a_2 * x * x + a_1 * x + a_0
となり、掛け算が6回、足し算が3回です。
しかし、プログラム1の10行目を
> ((a_3 * x+a_2) * x+a_1) * x+a_0
とすることで、掛け算を3回に減らすことができます。

ここで、
> ((a_3 * x+a_2) * x+a_1) * x+a_0

> A ← a_3 * x+a_2
> A ← A * x a_1
> A ← A * x a_0
と書くこともできます。

また、
> A ← a_3
> A ← A * x+a_2
> A ← A * x a_1
> A ← A * x a_0
と書くこともできます。

最初のAへの代入が「種」になって、あとは「A * x a_n」(nを1ずつ下げていく)を繰り返せば計算できるということです。

---------------------------

上の「工夫」を見て気づきませんか?

そうです、〔プログラム2の一部〕14行目が「種」で17行目が繰り返し部です。

〔アルゴリズム2の説明〕(3)Aを改めて振り返ると、dに入るのは
> b_(n-1) * x^(n-1)+b_(n-2) * x^(n-2)+…+b_1 * x+b_0

これを変形すれば、
> B ← b_(n-1) * x + b_(n-2)
> B ← B * x + b_(n-3)
> ……
> B ← B * x + b_1
> B ← B * x + b_0
または
> B ← b_(n-1)
> B ← B * x + b_(n-2)
> B ← B * x + b_(n-3)
> ……
> B ← B * x + b_1
> B ← B * x + b_0

---------------------------

あとは、dの方程式の次数(xのかける回数)がfよりも1小さいことに注意しつつ
> B ← b_(n-1) * x + b_(n-2)
> B ← B * x + b_(n-3)
> ……
> B ← B * x + b_1
> B ← B * x + b_0

> B ← b_(n-1)
> B ← B * x + b_(n-2)
> B ← B * x + b_(n-3)
> ……
> B ← B * x + b_1
> B ← B * x + b_0
のどちらを使えばよいかを考えれば答えが出せます。
2021.09.21 23:06

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2,000文字以内)

投稿削除用のパスワード(20文字以内)

プレビュー
※CBT方式においては出題内容の公開は禁止されているため、出題内容を尋ねたり、出題内容を特定できる類の投稿を禁止します。
※宣伝や迷惑行為を防止するため、当サイトとIPAサイト以外のURLを含む文章の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop