再帰

質問

x=2のときの4次多項式 f(x) = 1x^4 + 2x^3 + 3x^2 + 4x + 5の解を
ホーナー法、再帰を用いて計算せよ

という問題(C言語)があるんですけど、よくわかりません。

ホーナー法を用いるということで、そこは自分で調べて
(((1x+2)x+3)x+4)x+5となることはわかりました。

でもC言語で書けと言われてもどこをどう再帰で書けばいいのかわかりません。
わかる人だれか教えてください。お願いします。

回答No.3

yama5140

＞(((1x+2)x+3)x+4)x+5となることはわかりました。

　・トップの 1 は、(0x+1) の結果として考えると、

　　　　((((0x+1)x+2)x+3)x+4)x+5 となり、

★プログラム的に《考え易く》なります ← ◆◆◆重要。

（参考ＵＲＬを下敷きに）
#include <stdio.h>

int　igKeisu[5] = { 1, 2, 3, 4, 5 };

int　Horner( int iVal, int iX, int iKou )
{
　if( iKou >= 5 )　return( iVal );

　iVal *= iX;

　iVal += igKeisu[ iKou ];

　printf( "%d [%d]\n", iKou, iVal );

　iVal = Horner( iVal, iX, ++iKou );　// 再帰呼出

　return( iVal );
}
void　main()
{
　printf( "%d\n", Horner( 0, 2, 0 ) );
}
注：インデントに全角空白を用いています。
　　タブに一括変換して下さい。
------------（コッソリト）------------
＞突っ込み受け付けます。

★中程の } else { は、あってもなくても結果が同じだから、
　「ない方」がいいと思います（冗長）。

　　・ソースは、

　　int　func( int x, int i )
　　{
　　　　if( i < 3 )　return( x + i );

　　　　return( iX * func( x, i - 1 ) + i );
　　}となろうかと。

☆だめ押し（教室から男女分けて廊下に出すとき）

・「女子から廊下に出て」と言った後、「《女子でない》ものも廊下に出て」
　の《女子でない》に相当しますよね？。

--- else のキライな年寄りは、---

　「女子から廊下に出てね」と言った後は、教室内は男ばっかだから、
　「とっとと廊下に出ろ」なんだけど・・。

（予想外のところに「突っ込み」が入って・・）

＞あってるかなぁ・・・。

　結果は同じでした。

参考URL：

http://www.u-aizu.ac.jp/course/alg1/ex/jp/ex04/

回答No.2

POTATO_XP

再帰は勘を掴むまで苦労した経験があるので答え書きます。
わかんなかったら状態遷移を書いてみる事です。
あってるかなぁ・・・。(＿はインデント)

int func(int x,int i){
＿＿if(i<3){
＿＿＿＿return x+i;
＿＿} else {
＿＿＿＿return x*func(x,i-1)+i;
＿＿}
}

void main(void){
＿＿int x=～;
＿＿func(x,5);
}

突っ込み受け付けます。参考まで。

回答No.1

asuncion

> (((1x+2)x+3)x+4)x+5となる

「何か（１）」にxを掛けて5を加えると、「最終結果」
「何か（２）」にxを掛けて4を加えると、「何か（１）」
「何か（３）」にxを掛けて3を加えると、「何か（２）」
「何か（４）」にxを掛けて2を加えると、「何か（３）」
「何か（４）」は1

上記のロジックを再帰呼び出しで表現します。
関数名は、仮にhornerとでもしますか。
引数は２つ、x（=2）とnum（加える数）でよいでしょう。
horner関数の仕様は下記のとおりです。
numが2以上ならば、一つ前の結果（つまり、horner(x, num-1)）にxを掛けてnumを加えた値をreturnします。
numが2以上でなければ、初期値の1をreturnします。

そして、horner関数を呼ぶ側で horner(2, 5) の結果を出力すればOKです。