- ベストアンサー
再帰を非再帰に実装しなおしたいです。
odd-even merge ソートを、再帰を用いずに実装したいです。 再帰有りの処理は以下のとおりの実装となります。 http://ideone.com/mAYt61 これを再帰無しの処理に実装し直したいのですが、（odd_even_mergesort関数一つにまとめたい） 上手く書けません。良い書き方を教えていただけますでしょうか？？
- rxjrythy
- お礼率100% (1/1)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
「odd_even_mergesort関数一つにまとめたい」との関連はさっぱりわからんけど, 「再帰を非再帰に実装しなおしたい」というときの鉄板はスタック. 「アルゴリズムそのものを変更する」という手もある.
関連するQ&A
- 22年春 基本情報処理試験 問8 マージソート
22年春の基本情報処理試験 、問8のマージソートが解らないでいます。 設問2で与えられている、3、8、2、7、5、1という値を関数Sortに渡し、 これを実行すると、 一番最初に関数Mergeが実行される時に、関数Mergeに渡される引数は、 slist1 = 8、num1 = 1、slist2 = 2、num2 = 1になりますよね？ それで、関数Mergeを実行して、list[] = {2,8} が返却されるところまでは、 理解できるのですが、その後の動きがわかりません。 僕はいくら考えても、ここで終わっちゃうんです。 どの関数に、どの引数を渡してあげればよいのでしょうか… どなたか教えて下さい。 よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- 非再帰のマージソートについて
非再帰のマージソートを作成しているのですが、 上手いこと出来なくて困っています。 条件として配列の開始と終了のインデックスを指定して、 その間の要素だけをソートしたいのです。 ex： int array[10] = { 9,8,7,6,5,4,3,2,1,0 }; MergeSort( array, 2, 6 ); // array[2]～array[6]をソート for( int i=0; i<10; i++ ) printf( "%d, ", array[i] ); 出力） 9, 8, 3, 4, 5, 6, 7, 2, 1, 0, 以下のサイトで公開されているマージソートを元に 私なりに弄ってはいるのですが、 メモリを壊してしまうようなエラーが頻発して、 どうもうまくいかないのです・・・。 http://besky-works.spaces.live.com/Blog/cns!555CF2E2F9E31C71!557.entry どなたがおわかりの方がいらっしゃれば、 その方法を教えていただければ助かります。
- ベストアンサー
- C・C++・C#
- 再帰的(リカーシブ)プログラムの説明について。
以下は、再帰的(リカーシブ)プログラムの説明を記載しました。 この説明文でおかしい箇所の添削をお願い出来ないでしょうか？ 宜しくお願い致します。 以下からになります。 再帰的(リカーシブ)プログラムとは、プログラムの中から自分自身を呼び出して実行することを再帰的(リカーシブ)アルゴリズムといい、この形式で再帰呼び出しを行うプログラムのこと。 まずは、再帰的アルゴリズムについて、例を使って説明を行いたい。 主プログラムとサブルーチンaがある。 主プログラムは、文字通り、主(メイン)となるプログラム。 サブルーチンは、主プログラムが呼び出して利用する処理をひとまとめにしたもの。 文字通り、サブとなる処理を行う。 主プログラムには、CALL aという命令が記述されている。 これはサブルーチンaを読み出すという命令。 この再帰的プログラムは、処理が終わったら、読み出された場所に帰っていく。 このため、戻り場所を記憶しておかないと帰る事が出来ない。 この戻り場所を記憶するのが、LIFO方式による記憶領域になる。 LIFO方式の記憶領域だから、スタック領域になる。 スタック領域だから、後入れ先出しで戻り場所を記憶していく。 まずは、1回目の呼び出しとして、主プログラムがサブルーチンaを呼び出している。 1回目の戻り場所を記憶しておく。 次にサブルーチンaを見ると、CALL a、つまり自分自身を読み出している。 これが2回目の読み出し。 このように自分自身を呼び出すことを再帰呼び出しという。 同じプログラムの中で自分自身を読み出しているのだが、コンピューターは、あたかも別のサブルーチンがあるように処理が行われている。 この場合、それぞれの処理で、別の変数を用意しながら処理を行う。 このサブルーチンで処理が終わった場合にも、もとに戻る必要がある。 これは2回目の呼び出しになるため、2回目の戻り場所を記憶しておく。 更に、3回目として再びサブルーチンaを呼び出す。 3回目の戻り場所を記憶し、また別の変数を用意しながら処理を行う。 ここで最後のサブルーチンで処理が終わったとする。 処理が終わったら、呼び出された場所に戻る。 戻り場所の記憶を見てみると、上から戻る順番に記録されていることがわかる。 戻り場所はLIFO方式、後入先出しで記録されているから、最後に呼び出した3回目の戻り場所が1番上に記録され、次に2、最後に1が記録されている。 最初は戻り場所を記憶した記憶領域を参照して、3回目に呼び出された場所に戻る。 ここで3の戻り場所が消える。 そして引き続き処理が行われる。 次に、2回目に呼び出した処理が終わり、2回目に呼び出された場所に戻り、2の戻り場所が消える。 また引き続き処理が行われ、1回目に呼び出した処理が終わり、1回目に呼び出された場所(主プログラム)に戻り、1の戻り場所が消える。 そして処理が行われ、プログラム全体が終了する。 このように、プログラムの中で自分自身を呼び出し、戻り場所を記憶しながら実行するようなプログラムを再帰的(リカーシブ)プログラムという。
- ベストアンサー
- その他（プログラミング・開発）
- pl/pgsqlで再帰呼び出しは可能でしょうか。
pl/pgsqlで再帰呼び出しは可能でしょうか。 PostgreSQLのバージョンは9.2.3です。 作成しているファンクションは正方形の中心座標を求めてInsertするものです。 指定した回数だけ、再帰的に正方形を４分割にどんどん細分化していき、 それぞれの正方形の中心座標をInsertします。 ４分割にした正方形をそれぞれ以下のように番号を振って説明します。 左上・・・(1) 右上・・・(2) 左下・・・(3) 右下・・・(4) 元の正方形を求めた後、(1)→(2)→(3)→(4)の順に再帰的にファンクションを呼び出します。 パラメータを「３回」以上にした場合は、(1)についてもまた４分割していきます。 ここで、パラメータを「１回」とした場合は、元の正方形の中心座標は当然Insertできます。 パラメータを「２回」とした場合、(1)の正方形の中心座標も求まりますが、 (1)の正方形については再帰の最終処理のため、Insert後にRETURNすることで エラーとなっているのか、１つ目の正方形のレコードも(2)の正方形のレコードも Insertされていません。 さらにはその「RETURN句」が元のファンクションすら「終了」させているようで、 (2)、(3)、(4)の正方形の処理が行われません。 このように再帰呼び出しをしたいと思っても、再帰中の処理を終わらせ、 呼び出し元に戻らせるはずのRETURN句が、一番最初のファンクションの「終了」と 理解されてしまい、pl/pgsqlでは再帰呼び出しは実現できないのでしょうか。 ファンクションのイメージは以下の通りです。 CREATE OR REPLACE FUNCTION Insert_squre( IN kaisuu INT, --再帰的に呼び出す回数 IN count INT, --再帰回数をカウント IN X1 INT, --正方形の左上の頂点のX座標 IN Y1 INT, --正方形の左上の頂点のY座標 IN X2 INT, --正方形の右下の頂点のX座標 IN Y2 INT --正方形の右下の頂点のY座標 ) RETURNS void AS $$ DECLARE /* 変数定義 */ ・・・・・ BEGIN /* 中心座標を求める */ ・・・・・ /* 中心座標をInsert */ ・・・・・ /* kaisuu=countならばRETURN */ ・・・・・ /* (1)の正方形について再帰処理 */ select Insert_squre( IN kaisuu INT, --再帰的に呼び出す回数 IN count+1 INT, --再帰回数をカウント IN X1 INT, --正方形の左上の頂点のX座標 IN Y1 INT, --正方形の左上の頂点のY座標 IN X3 INT, --正方形の右下の頂点のX座標 IN Y3 INT --正方形の右下の頂点のY座標 ); /* (2)の正方形について再帰処理 */ ・・・・・ /* (3)の正方形について再帰処理 */ ・・・・・ /* (4)の正方形について再帰処理 */ ・・・・・ RETURN; END; $$ LANGUAGE PLpgSQL;
- 締切済み
- PostgreSQL
- マージソート内の再帰処理にすいて
#include<stdio.h> #define MAX 4 int temp[MAX]; void marge(int num[],int left,int right) { int i,j,mid,k if(left>=right)return; mid=(left+right)/2; marge(num,left,mid);//(1) maege(num,mid+1,right);//(2) for(i=left;i<=mid;i++) temp[i]=num[i]; for(i=mid+1,j=right;i<=right;i++,j--) temp[i]=num]j]; i=left; j=right; for(k=left;k<=right;k++) if(temp[i]<=temp[j]) num[k]=temp[i++]; else num[k]=temp[j--] } マージソート内はこういった関数を記述してエラーもでないのですが、(1)と(2)の処理がよくわかりません。 (1)は再帰的に処理していってif(left>=right)return;の条件を満たした場合に(2)の処理に入っていきますよね？ その場合、(2)の処理を行う際に(1)が(2)の再帰より前に記述されているので(1)がまた処理されるのでしょうか？ 一連の流れを(1)、(2)を使って表してほしいです。
- 締切済み
- C・C++・C#
- PHP初心者 再帰処理について
あるフォルダ以下に含まれる全てのフォルダ名をフルパスですべて列挙するという処理を描こうと下記のブログを参考にして自分で少し書き換えたのですが、うまくいきません。 http://blog.asial.co.jp/12 <参考にした部分> function getFileList($dir) { $files = scandir($dir); $files = array_filter($files, function ($file) { // 注(1) return !in_array($file, array('.', '..')); }); $list = array(); foreach ($files as $file) { $fullpath = rtrim($dir, '/') . '/' . $file; // 注(2) if (is_file($fullpath)) { $list[] = $fullpath; } if (is_dir($fullpath)) { $list = array_merge($list, getFileList($fullpath)); } } return $list; } </参考にした部分> <自分で変更したコード> function getFileList($dir) { $files = scandir($dir); $files = array_filter($files, function ($file) { // 注(1) return !in_array($file, array('.', '..')); }); $list = array(); foreach ($files as $file) { $fullpath = rtrim($dir, '/') . '/' . $file; if (is_dir($fullpath)) { $list[] = $fullpath; $list[] = array_merge($list, getFileList($fullpath)); } } return $list; } </自分で変更したコード> 変更といってもis_fileの部分の削除と$list[] = $fullpath;を追加しただけなのですが、「～ bytes exhausted」というエラーになってしまいます。 再帰関数が内部的にどういう処理をしているのかよくわかってないので、正直変更したコードがどういう動きをしているのかいまいち理解できません。参考書にある再帰関数は腑に落ちないながらも結果としてはそうなるということは理解しました。 あとそれ以前に $files = array_filter($files, function ($file) { return !in_array($file, array('.', '..')); の部分がわかりません。 scandirの戻り値には要素の最初の方に「.」と「..」が付くのでそれを削除する目的だとブログにはありますが、in_arrayはただ第一引数のものを第二引数から検索するだけのはずなのに、$filesの中身をarray_filtersの処理後に確認してみるとちゃんと「.」と「..」が削除されていて不思議です。あとin_arrayは第一引数のものを第二引数の中から検索するという関数だと思いますが、なぜそれをわざわざ反転させて（(array('.', '..'), $file);じゃなく($file, array('.', '..'));）!in_arrayとしてるんでしょうか？ ＊ちなみに引用したブログのコードの動作は確認済みで元のコードは完全に正しいです。引用したコードに文句をつけているわけではなく自分がわかっていないだけです。(^^ゞ 以上です。よろしくお願いします。
- ベストアンサー
- PHP
- MFC VC++6.0 DestroyWindowの実装場所について
[開発環境]：Visual C++ 6.0 現在、Visual C++ 6.0を使ったプログラミングの勉強をしています。 MFC AppWizard (exe)でSDIプログラムのtest1プロジェクト作成後、メインフレームにボタンを実装し、そのボタンを押下するとモードレスダイアログを表示するというアプリケーションを作っているのですが、ダイアログを終了させる時のDestroyWindowの実装場所と実装方法が分かりません。 ダイアログ用のクラスはCmyDialogとしていますが、ダイアログの終了ボタンを実装した場合、そのボタン処理の中すなわちCmyDialogクラスのなかの関数で行うべきなのでしょうか？それともダイアログの作成と同様にメインフレームがわの処理(CTest1Viewクラスでの処理？)として行うべきなのでしょうか？この場合にはどのような場所でどのようなタイミングで実装すればよいのか分かりません。 ご存じの方、これらについて御教授お願いします。 以下プログラムの一部を記載します。 -test1view.cppの一部-(ここでダイアログの作成と表示をしています) void CTest1View::OnButton1() { CmyDialog* myDLG = new CmyDialog; myDLG->Create(IDD_DIALOG1,this); myDLG->ShowWindow(SW_SHOW); }
- ベストアンサー
- C・C++・C#
- PHPでの再帰を用いたツリー構造について
PHPを勉強中の初心者です。PHPで、ツリー構造を再帰関数を用いて実装するプログラムを作成し、そのツリーを表示しようとているのですが、どうもよくわかりません。 このプログラムの挙動としては、以下でクリエイトしたTreeオブジェクトを、preorder（トップダウン、左側から）で出力させるもので、期待値は以下のとおりです。 （期待値） preorder: 1 2 4 5 3 6 7 （クリエイトされたオブジェクト） $myTree = new Tree(1, new Tree(2, new Tree(4), new Tree(5)), new Tree(3, new Tree(6), new Tree(7))); =========サンプルプログラム================================ #!/usr/bin/env php <?php class Tree { var $top; var $left; var $right; #コンストラクタを定義はこれであっているでしょうか。 function Tree($top, $left, $right){ $this ->top = $top; $this ->left = $left; $this ->right= $right; }; function preorder( ){ #preorder() メソッドを実装方法がよくわかりません。 } } $myTree = new Tree(1, new Tree(2, new Tree(4), new Tree(5)), new Tree(3, new Tree(6), new Tree(7))); function printPreorder($tree) { echo "preorder:\n"; $tree->preorder(create_function('$v', 'echo "$v\n";')); } printPreorder($myTree); ?>
- 締切済み
- PHP
- JSFで最初のリクエストで動く処理を実装するには？
近日、JSF(ver 1.2)でWebシステムを実装することになりJSFの勉強中のものです。 ASP.NET や PHP(Smarty) でWebシステム実装経験があります。 JSFでどう実装すれば良いのかわからないことがあり、詳しい方にお教え頂きたいと考えています・・・！ 【質問概要】 JSFで最初のリクエスト時のみに動く処理はどのように実装すればよいのでしょうか？ ASP.NETでは Page_Load イベントで Page#IsPostBack を以下の例のように使用すると 最初のリクエスト時のみに動く処理を実装することができました。 ---- 例 ここから ------------------------------------------- void Page_Load() { // 毎リクエスト時に行う処理 if (!IsPostBack) { // 最初のリクエスト時にのみ行う処理 } } ---- 例 ここまで ------------------------------------------- JSFではこれに相当するものが無いでしょうか？ 【試してみたこと】 管理Beanのコンストラクタで最初のリクエスト時にのみ行う処理ができるかと思い、 以下のtest.jspを実行し、コンソールにどのように表示されるか試してみました。 ---- test.jsp ここから ------------------------------------- <%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding="UTF-8"%> <%@ taglib prefix="f" uri="http://java.sun.com/jsf/core"%> <%@ taglib prefix="h" uri="http://java.sun.com/jsf/html"%> <%@ taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core"%> （中略） <body> <f:view> <h:form> <h:commandButton action="#{Test.clickTest}" value="テストボタン"></h:commandButton><br /> </h:form> </f:view> </body> </html> ---- test.jsp ここまで ------------------------------------- ※Test は 下記 Test.java で実装した管理Bean。スコープはrequest。 ---- Test.java ここから ------------------------------------- public class Test { public Test(){ System.out.println("コンストラクタを通っている。"); } public String clickTest() { System.out.println("ボタンが押された。"); return "clickTest"; } } ---- Test.java ここまで ------------------------------------- ＜コンソール出力結果＞ 最初のリクエスト時： コンストラクタを通っている。 テストボタン押下後： コンストラクタを通っている。 ボタンが押された。 このことから、リクエストのたびにコンストラクタが処理されていることが分かりました。 ASP.NETの Page#IsPostBack の様なものがあれば、最初のリクエストかどうかを判別できるのですが・・・！ 以上です。 上記のようなコンストラクタを使用する以外でも、なにか良い方法は無いでしょうか？ お詳しい方、何卒よろしくお願い申し上げます・・・！
- 締切済み
- Java
お礼
ご回答を踏まえてもう一度考えてみたいと思います。 ありがとうございました。