c言語プログラミングについて for文をつかって漸化式 数列anがある。 an+2=3an+1 +2

c言語プログラミングについて


for文をつかって漸化式

数列anがある。
an+2=3an+1 +2a

a0=1
a1=2
のときa10の値を求めるプログラミング

もうひとつは
3つのa b c
に値を入力させてaからbの間にcの約数はいくつあるか？？を求めるプログラム

これもscanfで入力させるまではわかりますが
それからよくわかりません。

これらのプログラミングにはいずれもfor文を用いると思いますがどうしてもわかりません。

ヒント
もしくは
解説よろしくお願いします。

No.3 回答者： cametan_42 回答日時： 2018/07/08 14:29

あ、すみません、#1のコード書き写す際に写し間違えてたですね。

漸化式の

int a(n) { ....

って書いたトコは

int a(int n) { ....

の記述ミスです。

No.2 回答者： usa3usa 回答日時： 2018/07/08 07:09

漸化式　のヒントです

＞an+2=3an+1 +2a
an+2=3an+1 +2an の誤記ですよね。
「2つ前のanから今のanが求まる」ということですよね。

つまり、2つ前のanを、変数A,Bに記憶しておけばよいので、
int A,B,C;
として、今のanをCとして、C = 3*B + A; とでもすればよいでしょう。
具体的には、
A=a0
B=a1
とすればCとして、a2が計算できますよね。

a3を計算したいならば、
A=a1
B=a2
とすれば計算できますよね。

なんと「a1,a2はすでに計算されていて変数B,Cに入っている」ではないですか！

これを利用すればa3が計算できます。
a4 についても同じことができます。

＞これらのプログラミングにはいずれもfor文を用いると思いますが
その通りです。繰り返し同じことをするのはfor文を用いてできます。
ヒントを頼りにプログラムしてください。
わからなければ、再度質問されたらよいと思います。

No.1 回答者： cametan_42 回答日時： 2018/07/08 03:10

まずは

> 3つのa b cに値を入力させてaからbの間にcの約数はいくつあるか？？を求めるプログラム

から、です。

考え方としては、始点がa、終点がbとして、

for (i = a, i <= b, i++) {
　　///ここに何かが入る
}

ってのがフォーマットになりますね。要するにaからbまで「繰り返し」をすれば良い。
では、約数の判定がどうなるか、って事ですが、約数とは

> 整数（整式）Ａが他の整数（整式）Ｂで割り切れる時の、Ａに対するＢのこと。

との事です。言い換えると、AをBで割った時の余りがゼロになれば良い。
そうすると、条件文を使ってモジュロ(剰余)演算を行って、その解がゼロになった時にカウントしていけば良い、って事です。
従って、

int foo(int a, int b, int c) {
　int count = 0;
　int i = 0;
　for (i = a; i <= b; i++){
　　if (i%c == 0){
　　　count += 1;
　　}
　}
　return count;
}

ってのが答えになります。
main関数からどうやってこいつを呼び出すか、ってのは任せましょう。

では、次は....ですが、

>漸化式
>
>数列a_{n}がある。
>a_{n+2}=3a_{n+1} +2a_{n}
>
>a_{0}=1
>a_{1}=2
>のときa_{10}の値を求めるプログラミング

でしょうねぇ。なかなかWebページで「添字」を表現するのは厄介です。
それと、加えると、

> これらのプログラミングにはいずれもfor文を用いると思いますがどうしてもわかりません。

結論から言うと「ここでは使いません」。
漸化式をプログラミングする際にはfor文なんか使うとややこしくなってシャレにならなくなります。
じゃあどうするか?
漸化式をプログラムする際には漸化式をそのまま使えば良いのです。
こういうのを「再帰(recursive)」プログラミングと言います。

英語では漸化式をRecurrence relationと呼ぶようですが、最初の単語は再帰(recursive)と同じですね。つまり漸化式、ってのは「再帰関係式」と呼んでも良いわけですが、「数学的表現をそのままプログラムしてしまう」のが吉だ、と言う等価性を示しているわけです。下手にfor文なんて使えば関係性を壊してしまいます。
重要なのは終了条件(Baseケースと言いますが)ですが、これも考える必要がなく、問題文に書いてますね。

n = 0の時 => 1を返す
n = 1の時 => 2を返す

つまり、条件文を用いて

if (n == 0) {
　return 1;
} else (n == 1) {
　return 2;
} else {
　// ここに何か入る
}

ってのが骨格になります。
「何が入るのか」ってのもぶっちゃけ問題文に書いてるんで、そのまま書けば良いのですが、注意点としては、問題文ではa_{n + 2}がどう定義されてるのか、って表現されてますが、これをa_{n}をどう表現されてるのか、に変えないといけません。
まあ、簡単ですよね。添字を2づつズラセば良いだけですんで。
従ってプログラムされる漸化式は次の通りです。

a_{n}=3a_{n-1} +2a_{n-2}

これを「何のヒネりもなく」そのままプログラムすると次のようになります。

int a(n) {
　if (n == 0) {
　　return 1;
　} else if (n == 1) {
　　return 2;
　} else {
　　return 3 * a(n-1) + 2 * a(n-2);
　}
}

これで終了、です。aを「aを使って」定義してますが、数学が「これは動く」と保証してくれてるんで、あとは知ったこっちゃないですね。
あとは、main関数を自分で作って、関数aを引数10を与えて呼び出せば題意は満たせるでしょう。