プログラマ専用SNS ミクプラ

はじめまして、いちこといいます。
プログラム初心者です。よろしくおねがいします。

再帰呼び出しの練習のためのプログラムを作成しているのですが、うまくゆきません。
配列tの各要素を木構造のようなかたちで表示させたいです。（詳しくは画像を見てください）
配列の各要素には0から100までのランダムな値を代入します。
配列の要素数はキーボードから入力して指定します。
結果：　よりも下の木構造の部分は、関数としてモジュール化し、自分自身を再帰的に呼び出す処理を行いたいです。

自分で考えて、なんとかエラーを出さずに実行するところまできたのですが、自作関数resultの中がおかしいのは自分でもわかります。
ですが、どこで再帰呼び出しをすればよいのか、特に画像の赤いやじるし部分で、処理をまた木構造の上のほうに戻す再帰呼び出しを、どうすればよいのかわかりません。
どのように処理を行えばよいのでしょう。
初心者がさぞ場違いな質問をしているとは思いますが、どうかよろしくおねがいします。

コード:

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

void result(int);
int t[100];
int N;

int main(void)
{	
	int i=0;

	srand(time(NULL));
	
	printf("Nを入力してください。\n");
	scanf("%d",&N);

	printf("t[%d] : ",N);
	while(1){
		t[i]=rand()%1000;
		printf("%d",t[i]);
		i++;
		if(i<N) printf(",");
		else break;
	}
	printf("\n");
	
	i=0;
	result(i);

	return EXIT_SUCCESS;
}

void result(int i)
{

	if(i<N){
		printf("\t");
		i=i+1;
		result(i);
		printf("%d\n",tree[i+1]);
		if(i+2<N)	printf("%d\n",tree[i+2]);
		else	return;
	
	}
	else return;
}

ちなみに、使用しているOSはWindows7、コンパイラはborlandです。
よろしくおねがいします。

現在の数値が木構造の先端（葉）であるか否かはどうやって判断するつもりですか？

こんにちは、ookamiです。
良くない回答ですがごめんなさい。

「ツリー構造と再帰」は相性がいいと思いますが、
「配列をあたかもツリー構造のような形で(しかも縦に並べて)表示する」というのは、再帰の練習問題としては微妙かなと思います。

>h2co5さん
返信ありがとうございます。
現在の添え字に、現在の添え字+1を加算した値が、Nより大きいか否かで判断できるのではないかと思ったのですが、どうでしょうか。

>ookamiさん
返信ありがとうございます。
確かにわたしもどうかと思ったのですが、再帰呼び出しのところの練習課題として出された問題のひとつなのです。ごめんなさい。

h2so5 さんが書きました:現在の数値が木構造の先端（葉）であるか否かはどうやって判断するつもりですか？

今回、質問者さんがなさろうとしていることは、ちゃんとした二分木とかではなく、
単純に、配列の添字によって、何段目にデータを格納するかを決めているだけのような気がします。
例題の画像を見る限りでは、

0段目（=根っこ）
[0]の1個（2の0乗）

1段目
[1][2]の2個（2の1乗）

2段目
[3][4][5][6]の4個（2の2乗）

3段目
[7]～[14]の8個（2の3乗）

となっているようですので、（便宜上ゼロから数えた）段数と、
その段に配列のどこからどこまでが来るのか、数学的に表現できそうな気がします。

【注】段数の数え方を見直しました。
ゼロから数える方が、段数の値とその段に来る数値の個数とが一致するからです。

いちこさんが書きました:>h2co5さん
返信ありがとうございます。
現在の添え字に、現在の添え字+1を加算した値が、Nより大きいか否かで判断できるのではないかと思ったのですが、どうでしょうか。

例えば、図の中では15が木構造の先端にありますね。
しかし、配列の中で15は8番目にありますから添え字は7です。

N = 15 ですからこれでは判定できないことになります。

>boxさん
返信ありがとうございます。
ookamiさんもおっしゃるとおり、木構造が関係しているのは形だけなのですね。
たしかに法則がありそうです。
しかし、表示順は[7][3][8][1]...となると思うので、苦戦している次第であります。

>h2so5さん
返信ありがとうございます。
なるほどです！たしかにそうですね。
それでは添え字+2を加算した値が、Nより大きいか否かで判断すればよいでしょうか。
すこし考えてきます。

何となくですけど、再帰関数には2個の引数が必要な気がします。
１）今、何番目のデータを処理しているか（例題では0～14の範囲を動く）
２）全部で何個のデータがあるか（例題では15）

最初の引数によって、何段目であるかが一意に決まります。
そこで、再帰関数を最初に呼び出すときには、引数を（何番目を処理中, データの個数）で呼び出して、
再帰関数の中では、
１）最初の引数の値が2番目の引数の値以上であれば、何もしない。これが、再帰から抜け出す条件。
２）処理中のデータを出力する。出力時には、何段目であるかを意識する。
３）処理中のデータが何番目かはわかっているので、その親が何番目のデータであるかもわかるはず。
　　　再帰関数を（親の番号, データの個数）という引数で呼び出す。
４）２）項で出力した、次のデータを出力する。出力時には、何段目であるかを意識する。
というような流れで、
自分を出力→親を出力→次を出力
という手順を再帰的にくり返せばいいのではないか、と勝手に思っています。
実験するコードを書いたわけではなく、頭で考えただけですので、
的外れな回答になっているかもしれません。

>boxさん
返信ありがとうございます。
なるほどです。
自分→親→次というながれはなんとなく理解できたのですが、

box さんが書きました: １）最初の引数の値が2番目の引数の値以上であれば、何もしない。これが、再帰から抜け出す条件。

こちらの部分がよくわかりませんでした。わたしは、初めに再帰を抜け出すのはこの問題でいう15(添え字7)のときかと思ったのですが、どうでしょう。至らなくてすみません。

また、みなさんの返信をもとに、処理の流れをかんがえてみました。

このような流れでいいのでしょうか。
プログラムに落とす際のアドバイスをいただけるとうれしいです。
よろしくおねがいします。

t[0] の子供は t[1] と t[2] です。
t[1] の子供は t[3] と t[4] です。
t[2] の子供は t[5] と t[6] です
すなわち、 t の子供は t[2*i+1] と t[2*i+2] です。、

コード:

int 段数 = 0;

void result(int i)
{
    if (i < N) {
        段数を増やす;
        子供1 (t[2*i+1]) 以下を出力;  // 再帰
        タブを段数の数だけ出力し、自分(t[i])を出力;
        子供2 (t[2*i+2]) 以下を出力;  // 再帰
        段数を減らす;                 // 元に戻す
    }
}

配列 t も個数 N もグローバルなので、段数もグローバルでいいでしょう。

>かずまさん
返信ありがとうございます。
だんだんと理解できてきたような気がします！
かずまさんのご説明を参考にプログラムをつくりかえてみました。

コード:

void result(int i)
{
	int j=0;
	int k;

	if(i<N){
		j++;
		result(2*i+1); //子ども1（tree[2*i+1]）以下を出力（再帰！）

		for(k=0;k<=j;k++){
			printf("\t");
		}
		printf("%d\n",tree[i]); //自分(tree[i])を出力

		result(2*i+2); //子ども2（tree[2*i+1]）以下を出力（再帰！）
		j--;
	}
	else return;

これはどうでしょうか。
縦の並べ替えはうまくできました！ありがとうございます。
しかし、タブを表示する処理が正しく理解ず、いろいろ試してみたのですが、これでは毎段2つのタブが表示されてしまいます。
処理の流れを想像して紙に落としてみても、原因がわかりません。
ヒントをくださるとうれしいです。

ここに、似たような質問があって、回答がついています。参考になるかもしれません。
http://okwave.jp/qa/q7579902.html

かずまさんが書きました:配列 t も個数 N もグローバルなので、段数もグローバルでいいでしょう。

と書いてありますが、いちこさんのプログラムでは段数jはローカル変数であり、毎回0に初期化されますので、毎回2つのタブが表示されるのは正常な動作ですね。

>boxさん
返信ありがとうございます。
ありがとうございます。同じ質問ですね。
参考にさせていただきます。

>beatleさん
返信ありがとうございます。
なぜ2になってしまうのかようやくわかりました。
ですが、このように変更してみたのですが、微妙に違うかんじになってしまいます。
すこし考えてきます。
何か決定的な勘違いをしているようなら教えてくださるとありがたいです。

コード:

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

void result(int);
int tree[100];
int N;
int i,j;

int main(void)
{	
	int k=0;

	srand(time(NULL));
	
	printf("Nを入力してください。\n");
	scanf("%d",&N);

	printf("tree[%d] : ",N);
	while(1){
		tree[k]=rand()%1000;
		printf("%d",tree[k]);
		k++;
		if(k<N) printf(",");
		else break;
	}
	printf("\n");

	result(i);

	return EXIT_SUCCESS;
}

void result(int i)
{
	
	int k;

	if(i<N){
		j++;
		result(2*i+1); //子ども1（tree[2*i+1]）以下を出力（再帰！）

		for(k=0;k<=j;k++){
			printf("\t");
		}
		printf("%d\n",tree[i]); //自分(tree[i])を出力

		result(2*i+2); //子ども2（tree[2*i+1]）以下を出力（再帰！）
		j=j-2;
	}
	else return;

		

}

なぜ、段数を 1増やして、元に戻すところで、2減らしているのですか？
for (k = 0; k <= j; k++) { では、j 回ではなく、(j+1) 回ループを実行します。
問題には、「0から100までのランダムな値」とあるのに、そのそのプログラムでは
0から 999 までのランダムな値になっています。

>かずまさん
返信ありがとうございます。

かずまさんが書きました:なぜ、段数を 1増やして、元に戻すところで、2減らしているのですか？

すみません、おかしいですね。直しました。

かずまさんが書きました:for (k = 0; k <= j; k++) { では、j 回ではなく、(j+1) 回ループを実行します。

わたしも自分で気になっていたところなので、自分なりに直してみました。

かずまさんが書きました:問題には、「0から100までのランダムな値」とあるのに、そのそのプログラムでは
0から 999 までのランダムな値になっています。　

すみません！問題の記述のほうがミスです。
正しくは「0から1000までのランダムな値」です。ごめんなさい。

たくさん指摘してくださってありがとうございます。
かずまさんのアドバイスをもとに自作関数の部分を修正してみました。
これで、実行結果は正しくなりました！ありがとうございます。
なにか変なところがありましたらよろしくおねがいします。

コード:

void result(int i)
{	
	int k;
	if(i<N){
		j++;
		result(2*i+1); //子ども1（tree[2*i+1]）以下を出力（再帰！）

		for(k=1;k<j;k++){
			printf("\t");
		}
		printf("%d\n",tree[i]); //自分(tree[i])を出力

		result(2*i+2); //子ども2（tree[2*i+1]）以下を出力（再帰！）
		j--;
	}
	else return;
}

プログラマ専用SNS ミクプラ

自作関数と再帰呼び出しを使ったプログラムについて。

自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。

Re: 自作関数と再帰呼び出しを使ったプログラムについて。