C言語の数列の問題を配列を使って解きたいです

Question

C言語初学者です。
C言語の数列の問題で配列を使って解こうとするといつもエラーが出てしまい、自分で調べても何が間違えているのかわからなかったので質問させていただきました。
以下は与えられた問題です。

2つの数a0 = 0 a1 = 1が与えられたとき、an+2 = an +an+1 (n ≥ 0)で定義され る数列をフィボナッチ数列という。非負整数 n を入力すると 0 番目から n 番目ま でのフィボナッチ数列を表示するプログラムを作成せよ。

配列を利用して解くという問題指定もついていました。
最初に配列を指定するときの要素数をどうすればいいのかを特に教えてほしいです。
自分の能力不足は重々承知しているつもりですので優しく教えてほしいです。よろしくお願いします。
以下、エラーのコードです。

int main(){
    int n,i,Fn;
    int a[];
    printf("Enter the number:");
    scanf("%d",&n);
    printf("0\n");
    printf("1\n");
    if (n>=2) {
        for (i=2; i<=n; i++) {
            a[i]=a[i-1]+a[i-2];
            Fn=a[i];
            printf("%d\n",Fn);
            }
    }
    return 0;
}

Comments

[Zuishin]

> 最初に配列を指定するときの要素数をどうすればいいのかを特に教えてほしいです。

配列は不要です。
どのように配列を使えという指示があるなら、それによって数が変わってくるでしょう。

[maisumakun]

エラーが出た状態のコードと、実際に発生したエラーをご提示いただけませんでしょうか？

[MaridaCruz]

どのように配列を使えという指示はありませんでした。
ただ、「配列を使用する」と記述してありました。

[hoshi-takanori]

n の入力後に int a[n]; とか…。

[Zuishin]

2 要素でデータをスライドしながら使うのも手ですが、3 要素のリングバッファを使いたいところです。
n 個の要素を確保するのであれば、int の最大値から、値がオーバーフローしない最大の n を求めるのが良いと思います。
そこまでしなくても、適当に大きい数を指定すれば、使いきれず終わると思います。

[fana]

> 調べても何が間違えているのかわからなかった

「調べる」とは？
何が間違いなのかはエラーメッセージとして出ているのでは．

[jimbe]

>最初に配列を指定するときの要素数をどうすれば
hoshi-takanori さんのコメントで十分な気がします。(出来る処理系か分かりませんが。)

[Zuishin]

可変長配列は C11 でオプションに格下げになったので(つまり方言扱いなので)、学習時に使用していいかは微妙かと。中学英語のテストで you のことを u と書くと不正解になるような。

[hoshi-takanori]

C11 で可変長配列が削除されたのは知りませんでした。となると、選択肢は
・n の最大値を決めておく
・malloc などで動的に確保する
・処理系依存を承知で可変長配列
・長さ 3 の配列を使い回す
ってことになるでしょうか。

どれがいいかは出題者の意図を確認する必要があるかと…。

[BeatStar]

一つ目。「いつもエラーが出てしまい」とありますがどのようなエラーでしょうか?
エラーの種類によって対処が全く変わってきます。
http://blog.livedoor.jp/crackstars/archives/17846001.html

二つ目。「自分で調べても」とありますが、どのように調べ、どのように試したのでしょうか?
プログラマやSEは単に決まったコードを打つだけ…ではありません。不具合の原因を調査し修正することも含みます。デバッガで潜るとか、OS周りの調査とか。
質問者さんとしては何かしらの調査をしたのかもしれませんが、他のユーザは所詮赤の他人なのでどんな風に何をしたのかさえ言われないとわかりません。

三つ目。授業ではどこまで習ったか書きましょう。書かない場合は「実装できればいい」と考えられてしまいます。他の方も仰っているように教師が考えた答え以外は認めない場合もありますよ。

Answer 1

十分おおきな配列を最初に確保しておけば良いです。
４7回目でint型（３２ビット整数）の上限を超えます。
９５回目でlong long int 型（６４ビット整数）の上限を超えます。
なので１００程度確保しておけば十分です。
４7以上の数値の場合、オーバーフローがおこり正しい結果が表示されませんが、そのままにしてあります。

#include <stdio.h>
int main(){
    int n,i,Fn;
    int a[100];
    printf("Enter the number:");
    scanf("%d",&n);
    if (n < 0 || n > 99){
		printf("number is wrong!\n");
		return 0;
	}
	a[0] = 0;
	a[1] = 1;
	for (i = 0; i < 2; i++){
		Fn = a[i];
        printf("i=%d Fn=%d\n",i,Fn);
	}
    for (i=2; i<=n; i++) {
        a[i]=a[i-1]+a[i-2];
        Fn=a[i];
        printf("i=%d Fn=%d\n",i,Fn);
    }
    return 0;
}

Comments

[MaridaCruz]

皆さんの回答本当にわかりやすかったのですが、この方の回答が一番シンプルでわかりやすかったのでこの方をベストアンサーにさせていただきました。
本当にありがとうございました。

Answer 2

コードを大雑把に読んでみましたが、大体の方向性はあっています。(実際には全く違うのだが、見当違いとまでは言えない気がするので)

まず、フィボナッチ数列の定義を確認してください。によると、

フィボナッチ数列は、「2つ前の項と1つ前の項を足し合わせていくことでできる数列」のことです。

とある。

つまり、初項と第二項の和が第三項、第二項と第三項の和が第四項…となっている数列のことですね。これをプログラミングとかは置いといて今回のルール(nまでのフィボナッチ数列とか)を用いて現実世界で考えてみてください。手作業でノートかなんかにフィボナッチ数列を書いていくのです。

今回は初項(= a0 ) と第二項(= a1 )が決められています。第三項つまりa2から a(n-1)までをやる。と。

漸化式an+2 = an +an+1 (n ≥ 0) を用いて考えると、現在の項を i とすると i = 0 (= 初項) を代入してみると
a2 = a0 + a1 となりますね。つまり第三項は初項と第二項の和になっています。
i = 1 も同様に考えると a3 = a1 + a2 となり、第四項 = 第三項 + 第二項 となっています。これをnまで繰り返すと考えるとどうでしょうか?(厳密には n-1 までですが)

そうすると初項から考えても i = 0～(n-1)で、その中を　a[i+2] = a[i] + a[i+1] が漸化式(をそれっぽくしたもの)になる。

a0 = 0, a1 = 1 だとわかっているのだから最初から a[0] = 0, a[1] = 1 と入れておけば後はfor文とかで 0～(n-1)までの範囲をループさせながら上記の漸化式(もどき)を使って配列に突っ込んでいけばいいはずです。

後はそれをN個分ループしながら表示するだけです。

ただし、条件としてn ≥ 0があるのでこれも満たす必要があります。これは今回の質問みたいに

if( n >= 2 ){
    // 実際にフィボナッチ数列を求めて配列に入れる
}

というようなやり方でもいいですが、ちょっと待ってください。フィボナッチ数列の定義ってなんでしたっけ?

2つ前の項と1つ前の項を足し合わせていくことでできる数列

でしたよね。

ということはNは2以上でないならそもそも求めることが不可能と言えるはずです。
ただし、フィボナッチ数列の定義はWikipediaによると

F0 = 0,
F1 = 1,
Fn+2 = Fn + Fn+1 (n ≥ 0)

という漸化式なので n が 0 未満なのは認めないということです。

でもユーザは何を入力するかわからないってことで nに何を入れてもバグらないように「nが0未満のとき」とかみたいにやる・やらないを分岐させる必要がありますね。

やる: nの値が0以上
やらない: nの値が0未満

となると、

if( /* nの値が0以上 */ ){
    // フィボナッチ数列を求める
}else{ // nの値が0未満
    // 何もしない
}

となるはずです。でも「nの値が0未満」のときの処理が「何もしない」ってもったいないですよね。余計なものですね。なので省きましょう。すると

if( /* nの値が0以上のとき */ ){
    // フィボナッチ数列を求める
}

となりますがちょっとくどいと思いませんか? 処理内容から考えて「0未満はイレギュラーな状況」と言えるはずです。ということは「0未満 -> 何もせずに終了」と言えるはずです。

つまり、

1. nの値を決める
2. nの値が0未満なら何もせずに終了
3. フィボナッチ数列を生成する
4. (3)の数列を表示する

みたいにすれば、(1)で n = -1 だったら (2)で条件を満たすのでここで終了。そうすると(3)に行くことができないですよね。

n = 1 なら (2)では条件を満たさないため(3)に。そしてそのままフィボナッチ数列を求めて表示。

こうすれば可読性が高まるはずです。

そして今回の問題での「エラーが出た(泣」ではおそらく「配列の要素数が指定されていない」系のエラーメッセージが出ているのではないかと妄想しています。

C言語の配列では要素数が指定されていないと使えません。必ず inrt arr[10];のような感じで要素数を指定します。でも今回の場合は要素数が不明瞭。条件として 100<N≦0 となっているのなら 最大の項数は100なので100-1 = 99 あれば十分だと思いますが不定なのででたらめにデカい数字でいいかと。

あるいは動的配列を学んだのであればmalloc/freeを使って動的配列で確保するとかでもいいです。

Answer 3

配列だけを使ってみました。

#include <stdio.h>

int main(void)
{
	int a[3] = { 0, 1 };
	scanf("%d", a);
	while (a[0]-- >= 0)
		if (a[1] < a[2])
			printf("%d\n", a[1]), a[1] += a[2];
		else
			printf("%d\n", a[2]), a[2] += a[1];
}

別解

#include <stdio.h>

int main(void)
{
	int n, a[2] = { 0 };
	scanf("%d", &n);
	for (a[n & 1] = 1; n-- >= 0; a[n & 1] = a[0] + a[1])
		printf("%d\n", a[n & 1]); 
}

Answer 4

a(n+2) = a(n) +a(n+1) を言い換えれば
a(n) = a(n-1) + a(n-2) なのだから

0 番目から n 番目ま でのフィボナッチ数列であるなら
総素数 N+1 の配列があれば十分です。

[追記] 配列を再帰で埋めてみた:

#include <stdio.h>
#include <stdlib.h>

int Fn(int table[], int n) {
  if ( table[n] < 0 )
    table[n]  = n <= 2 ? n : Fn(table,n-1) + Fn(table, n-2);
  return table[n];
}

int main(){
  int n;
  printf("Enter the number:");
  scanf("%d",&n);

  int* table = malloc((n+1)*sizeof(int));
  for ( int i = 0; i <= n; ++i ) table[i] = -1;

  Fn(table,n);
  for ( int i = 0; i <= n; ++i ) {
    printf("%d\n", table[i]);
  }

  free(table);
  return 0;
}

Answer 5

数列を配列にすべて詰め込む必要がないなら3つの要素をを使いまわせばいい気がしました。

#include <stdio.h>
int main(void){
    
    int a[3];
    int n = 13;
    
    if (n < 0) {
        return -1;
    }
    
    if (n >= 0) {
        printf("0\n");
    }
    if (n >= 1) {
        printf("1\n");
    }
    a[0] = 0;
    a[1] = 1;
    
    for (int i = 0; i <= n - 2; i++) {
        a[(i+2)%3] = a[(i+1)%3] + a[i%3];
        printf("%d\n", a[(i+2)%3]);
    }
    return 0;
}

Answer 6

何かしらの処理に必要な値を「とりあえず配列という形で持つ」ように実装すれば良いのでは．

//※数値の型として何がよいのかわからんので…
typedef unsigned int ValType;

int main()
{
	const unsigned int n = 8;	//※nの入力処理は面倒なので省略
	ValType Buff[2] = { 0, 1 };	//配列
	unsigned char idx = 0;
	
	//a0, a1 の表示
	printf( "0\n1\n" );
	//a2以降の表示
	for( unsigned int i=2; i<=n; ++i )
	{
		Buff[idx] = Buff[0] + Buff[1];
		printf( "%u\n", Buff[idx] );	//※ここの書式指定については数値の型次第か
		idx = (idx+1)&0x01;
	}
	return 0;
}

Comments

[fana]

> 最初に配列を指定するときの要素数をどうすればいいのか

「必要な個数」にすればよい．

で，必要な個数とはいくつなのか？というのを考えることは　その問題を解く　ということに含まれているのではあるまいか．
「X個あれば済むような処理方法（アルゴリズム）を考えて実装せよ」って話なのだろうから．

[fana]

k番目の値を求めるのに k-1番目 と k-2番目 の値が必要，って話なら，
とりあえず覚えておけば良さそうな値の個数は２個だ．
k-3 番目とかそれよりも昔のデータは覚えていても使う機会が無いのだから，覚えておく必要は無い．

で，必要な値を配列という形で持つというのなら，配列の必要な要素数は２だ．それだけの話．
（まぁ，別に要素数が3個とか4個とかの配列にしておいても間違いとは言わないが，使わない要素を持つ意味は無いよね）