ヒープの探索の再帰

前へ 次へ
このQ&Aのポイント
  • A[N]を利用したヒープのプログラムを作りました。ヒープ内から指定した値を検索するfind関数を作成しましたが、正常に動作しません。再帰の部分で問題が発生しているようです。
  • find関数を作成しましたが、指定した値を正常に検索できません。再帰の処理の中で問題が発生しているようです。
  • A[N]を利用したヒープのプログラムを作成し、指定した値を検索するfind関数を実装しましたが、期待した結果が得られません。再帰の部分で何か問題があるようです。
回答を見る
  • ベストアンサー

ヒープの探索の再帰

A[N]を利用したヒープのプログラムを作りました。 A[i]の親は、A[(i-1)/2]であるヒープです。 （上に行くほど小さい整数を格納） そしていまある整列されたヒープのなかからキーボードから入力した値ｘを検索する関数findを、 x ←検索する値 A[]←ヒープソートされた配列 n ←格納されているA[]の最後の添え字 として、 int find(int x, int *A, int i, int n) { if(A[i]==x){ printf("*\n"); /* ここの作業が行われているかを確認 */ return 1; } if(i>n)return 0; if(A[i]>x){ return 0; } else if (A[i]<x){ i = 2*i + 1; find(x, A, i, n); i++; find(x, A, i, n); } return 0; } というものを作ってみました。汚いかもしれませんが、とりあえず今はこれでいっぱいいっぱいです。 それで、当然のごとくうまくいきませんでした。 /**/内に書いたように、入力したｘがヒープ内にある場合は「*」が一応表示されるのですが、どうもfindは１を返してくれません。0を返してしまいます。見つけた後もまだ再帰をくりかえしえしているようです。 どこがいけないのでしょうか。

  • rousei
  • お礼率56% (111/196)

質問者が選んだベストアンサー

  • ベストアンサー
  • gatyan
  • ベストアンサー率41% (160/385)
回答No.1

findを再帰呼び出しする部分で、findの戻り値が１だったら return 1; としないと駄目なのでは？ （第一印象なので、テストしてません）

rousei
質問者

お礼

すいません説明不足でしたｍ(＿　＿)ｍ 全部調べて見つからなかった場合のみは0を返すようにしたいんです。 それで、見つかった場合は1を返してすぐにfind自体を抜け出したいってわけなんです。goto文は極力使いたくないので避けたいのですが・・ なぜ 関数自体を丸ごとかえてしまってもかまいません。何かいい方法はないでしょうか

rousei
質問者

補足

↓の「なぜ」　は無いことに

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • ヒープの探索の再帰　改め

    前回の質問は↓ http://oshiete1.goo.ne.jp/kotaeru.php3?q=658496 です。 前回の質問は何とか自己解決できました。 int find(int x, int *A, int i, int n) { if(A[i] == x)return 1; if(i>n)return 0; if(A[i]>x)return 0; if(A[i]<x){ i = i*2 + 1; if(find(x, A, i, n))return 1; i++; if(find(x, A, i, n))return 1; } return 0; } そして関数呼び出しの際に、 find(x, A, 0, n); とすることにより、探索が可能になりました。ただやはりもっと簡単にできそうな気がするのですが、思いつきません。もっと綺麗に書けるのならその書き方を教えて欲しいです。

  • ヒープ　deleteminの関数作成がわかりません

    問題文：ヒープの最小値を取り除く、deletemin関数を作成せよ。空の配列にinsertを複数実行することでヒープ条件を満たすヒープを構成する。これにdeleteminを実行することで最小値を抽出せよ。最小値を抽出した後、一次元配列がヒープ条件を満たすように再構成せねばならない。プロトタイプ宣言は以下とする。 int deletemin(int a[], int *n); 質問：関数deleteminについて調べてはみたんですが何をしているのか分からないものばかりだったので質問させてください。ヒープの最後のノードを根に持ってきて、右のノードと左のノードを比べて小さい値のノードの方と比較して最後から持ってきたノードの値の方が大きければ交換するというの繰り返して最小ヒープを再構成したいのですが、どうすればいいのかわかりません。サイトなどみても分からなかったのでど素人でも分かるように説明お願いします。 以下自分のソース #include<stdio.h> #include<stdlib.h> #include<time.h> int check_heap(int a[], int n); void insert(int val, int a[], int *n); int deletemin(int a[],int *n); int main(void) { int a[12] = {1,13,71,14,15,80,91,24,60,63}; int n; int i; int b,c; srandom(time(NULL)); b = random() % 100 + 1; n = 10; insert(b, a, &n); n = 11; c = random() % 100 + 1; insert(c, a, &n); printf("%d\n", check_heap(a, 12)); deletemin(a, &n); return 0; } int check_heap(int a[], int n) { int i; int m; m = (n - 1) / 2; for(i = 0; i < m; i++) { if(a[i] >= a[i * 2 + 1]) { return 0; } if(a[i] >= a[i * 2 + 2]){ return 0; } } if(n % 2 == 0){ if(a[(n - 1)/2] > a[n - 1]){ return 0; } } return 1; } void insert(int val, int a[], int *n) { int temp; int i; a[*n] = val; i = *n; while( 0 < i){ if(a[(i-1)/2] <= a[i]) { break; } temp = a[(i-1) / 2]; a[(i-1) / 2] = a[i]; a[i] = temp; i = (i - 1)/2; } } int deletemin(int a[],int *n){ int b; int i,j,k; b = a[0]; return b; }

  • 一次元配列で表現された最小ヒープの値挿入

    問題文：ヒープに新たなデータを挿入する関数insertを作成せよ。空の配列に複数回insertを行うことで 構成したヒープがヒープ条件を満たしていることをcheck_heapを用いることで確認せよ。プロトタイプ宣言は以下とする。 void insert(int val, int a[],int *n); 質問：　 複数回はおいといてとりあえず1回insertしようと思って書いたんですが、ヒープの最後に新しいノードを 作って親より小さければ親の値と交換を繰り返してヒープを完成させようとしてるんですが、1回しか交換されません。 どうすればいいですか？check_heapは最小ヒープ条件が満たされていれば１を満たされていなければ０を返す関数です。 自分のソース #include<stdio.h> #include<stdlib.h> #include<time.h> int check_heap(int a[], int n); void insert(int val, int a[], int *n); int main(void) { int a[11] = {1,13,71,14,15,80,91,24,60,63}; int n; int i; int b,c; srandom(time(NULL)); b = random() % 100 + 1; n = 10; insert(b, a, &n); printf("%d\n", check_heap(a, 11)); for(i = 0; i < 11; i++){ printf("%3d", a[i]); } return 0; } int check_heap(int a[], int n) { int i; int m; m = (n - 1) / 2; for(i = 0; i < m; i++) { if(a[i] >= a[i * 2 + 1]) { return 0; } if(a[i] >= a[i * 2 + 2]){ return 0; } } if(n % 2 == 0){ if(a[(n - 1)/2] > a[n - 1]){ return 0; } } return 1; } void insert(int val, int a[], int *n) { int temp; a[*n] = val; while(a[(*n-1) / 2] >= a[*n]){ temp = a[(*n-1) / 2]; a[(*n-1) / 2] = a[*n]; a[*n] = temp; } }

  • 線形探索について

    C言語の線形探索の課題なんですが ５つの整数を入力して その入力した値からみつけたい値を探索する課題なのですが #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) return (-1); /* 探索失敗 */ if (a[i] == key) return (i); /* 探索成功 */ i++; } } int main(void) { int i, ky, idx; int x[4]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); } printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); } ここまではわかるのですが、 x[0]=99 x[1]=99 x[2]=88 x[3]=99 x[4]=22 と入力したときに 99は 1番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？

  • c言語の再帰で(関数呼び出し)+1がわからない

    再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }

  • 再帰呼び出しの計算量

    再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { 　　if(n == 0){ 　　　　return 1; 　　}else{ 　　　　return x * exponent(x, n-1); 　　} } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？

  • 再帰の問題です。

    AOJの問題で、C言語で書いています。 ある解答者様のコードが自分の理解に深まると思い、見ているのですが、解答者様の作った関数のところの動作がよくわかりません。 問題です。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp 解答例です。分かるところ、分からないところを書いていきます。 #include<stdio.h> int n,s,a;//グローバル変数。 void dfs(int i,int sum,int m){//ここでいう、i,sum,mが何を指しているのか分かりません。 if(m==0 && sum==s){a++;return;} if(i==10 || m==0)return; dfs(i+1,sum+i,m-1);/*再帰をしています。しかし、どうしてここに自分と同じ関数を２つ、入れている　　　のか、分かりません。あと、どうしてiを足したり、１引いた数を代入しているのでしょうか?*/ */ dfs(i+1,sum,m);　　 } int main(){ while(scanf("%d%d",&n,&s)!=EOF){//Ctrl+zを押さない限り、無限ループします。 if(n==0 && s==0)break;//問題文通り、２つとも０だったらループを表すwhileから抜けます。 a=0; dfs(0,0,n);//ここもわからないです。ただ、関数dfsの動きが分かれば、分かると思います。 printf("%d\n",a); } return 0; } 再帰は今苦戦していますので、ここでもっと理解を深め、自作関数で使えるようになりたいです。 長文失礼しました。 よろしくお願いします。

  • 線形探索法のプログラムについて

    配列Aに格納されている数字を検索するプログラムより、 Aのプログラムでは配列Aに格納されている数字を検索(scanf("%d" , j)で入力)した にもかかわらず、「該当するデータがありませんでした」と表示されてしまいます。 Bのプログラムでは、配列Bに格納されている数字を検索(scanf("%d" , j)で入力)すると 「該当するデータがありました」と表示されます。 Aのプログラムで、------でかこってある部分に問題があると思われ、 いろいろと試してみましたが、未だにその理由をつかむことができません。 その理由を知りたく、書き込みを致しました。 ご教授の程宜しくお願い致します。 A. main(){ int i , j; int k = 0; int A[5] = {4 , 1 , 3 , 4 , 5}; printf("検索する数値を入力してください > "); scanf("%d" , j); --------------------------------------------------------------- for(i=0 ; i<5 ; i++){ if(A[i] == j){ printf("該当するデータはあります"); k++; } } --------------------------------------------------------------- if(k <= 0){ printf("該当するデータがありませんでした\n"); } return; } B #include<stdio.h> main(){ int i , j , k; int A[5] = {4 , 1 , 3 , 4 , 5}; printf("検索する数値を入力してください > "); scanf("%d" , j); for(i=0 ; i<5 ; i++){ if(A[i] == j){ k++; } } if(k>0){ printf("該当するデータはありました"); }else{ printf("該当するデータはありませんでした"); } return; }

  • 深さ優先探索について・・・

    ↓の文を参考にして、深さ優先探索のプログラムを書いてみました。 が、自分（初心者）ではできてるように思えたんですが、全然ダメみたいです。 再帰の使い方がよく分かってないというのもあるのですが（すみません）。 もしよろしければアドバイスを頂けませんか？お願いします！ 『・始点(ここでは「1」)を出発して、番号が小さい順に進む位置を調べていき 　行けるところ(辺でつながっていて、まだ未訪問の節点)まで進む。 ・行き場所が無くなったら、行けるところがある節点まで戻っ(再帰をリターンし)　て再び進めるだけ進む。 ・行き場所がなくなったなら終了(再帰からリターン) プログラムの際に節点iから節点jへ進めるか否かは節点と枝の関係を表すテーブル(これを隣接行列と言う)の要素a[i][j]の値が1であり、かつ訪問フラグv[j]が0であった時です。 訪問フラグは初期値に0を入れ(未訪問を表す)、 節点jが訪問されたならv[j]に1を入れます』 #include<stdio.h> int recurse(int i,int j); int main(void){ int recurse(int i,int j); return 0; } int recurse(int i,int j){ int v[j]; int a[i][j]; v[j]=0; v[0]=0; a[i][j]={{0,1,1,0,0,0,0,0}, {1,0,0,1,0,0,0,0}, {1,0,0,1,0,0,0,0}, {0,1,1,0,1,0,0,0}, {0,0,0,1,0,1,0,1}, {0,0,0,0,1,0,1,0}, {0,0,0,0,0,1,0,1}, {0,0,0,0,1,0,1,0}}; for(i=0;i<8;i++){ for(j=0;j<8;j++){ if(a[i][j] == 1 && v[j] == 0){ v[j]=1; printf("%d->%d ",i,j); break; } else return 0; } } return 0; }

  • 再帰呼び出し

    アッカーマン関数の値を出力するプログラム #include void main(void); int ack(int,int); void main(void) { int x,y,i; printf(" data(x) = "); scanf("%d",&x); printf(" data(y) = "); scanf("%d",&y); i = ack(x,y); printf("Ackerman = %d\n",i); } int ack(int a,int b) { int k; if (a == 0) k = b+1; else if (b == 0) k = ack(a-1,1); else k = ack(a-1,ack(a,b-1)); return (k); } この関数を呼び出した回数も出力するようにしたいのですが、どうしたらいいのでしょうか？

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する