ホーム » 「再帰」タグがついた投稿

タグアーカイブ: 再帰

2019年3月
« 2月    
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

JavaScriptでマージソート

配列のマージソートを、難しいテクニックを使わないスタンダードな書き方でのサンプル。

function merge_sort( a , start , end ) {
   if ( start + 1 == end ) {
      // a[start]の1件だけなので並び替える必用なし
   } else {
      // 真ん中
      var mid = Math.floor( (start + end) / 2 ) ;
      // 左半分を並べ替え
      merge_sort( a , start , mid ) ;
      // 右半分を並べ替え
      merge_sort( a , mid , end ) ;

      // 2つの山をマージする。
      var temp = new Array() ;          // マージ結果の一時的保存用
      var lt = start ;                  // 左の山の先頭
      var rt = mid ;                    // 右の山の先頭
      // ここがまだダサい。
      for( i = 0 ; i < end - start ; i++ ) {
         var w ;
         if ( lt >= mid ) {        // 左の山が空、右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         } else if ( rt >= end ) { // 右の山が空、左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else if ( a[lt] > a[rt] ) {  // 左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else {                       // 右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         }
         temp[ i ] = w ;
      }
      // マージした結果を、a[]のstart..endに戻す
      for( var i = 0 ; i < end - start ; i++ ) {
         a[ start + i ] = temp[ i ] ;
         console.log( "a["+(start+i)+"]="+a[start+i]) ;
      }
   }
}

array = new Array( 11 , 45 , 22 , 33 , 77 , 88 , 44 , 55 ) ;
merge_sort( array , 0 , array.length ) ;
for( var i = 0 ; i < array.length ; i++ )
   console.log( "a["+i+"]=" + array[i] ) ;

JavaScriptの再帰の例題

再帰呼び出しで分割統治法の考え方のプログラムをJavaScriptで書いたサンプル

単純に、配列の指定範囲の合計を求める関数を、再帰を用いて記述する。

<html>
<head>
</head>
<body>
 <p>
  このプログラムは、実行結果を console.log() で出力するので、
  Ctrl+Shift+I で、JavaScript の console を表示させてね。
 </p>
 <script type="text/javascript">
   // a : 配列
   // start : 合計を計算する範囲の戦闘
   // end : 合計を計算する範囲の最後+1
   // 配列の合計は、配列の先頭 + 残りの合計
   function array_sum( a , start , end ) {
     console.log( "array_sum:" + start + "," + end ) ;
     if ( start == end ) {
       console.log( "array_sum(" + start + "," + end + ")=0" ) ;
       return 0 ;
     } else {
       var ans = a[ start ] + array_sum( a , start + 1 , end ) ;
       console.log( "array_sum("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   var array = new Array( 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 ) ;
   console.log( array_sum( array , 0 , array.length ) ) ;

   // 配列の合計は、データが1個ならその値。
   // そうでなければ、配列の前半の合計 + 配列の後半の合計
   function array_sum2( a , start , end ) {
     console.log( "array_sum2:" + start + "," + end ) ;
     if ( start + 1 == end ) {
       var ans = a[ start ] ;
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     } else {
       var mid = Math.floor( ( start + end ) / 2 ) ;
       var ans = array_sum2( a , start , mid ) // 配列前半の合計を求める
               + array_sum2( a , mid , end ) ; // 配列後半の合計を求める
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   console.log( array_sum2( array , 0 , array.length ) ) ;
  </script>
</body>
</html>