0

受講しているアルゴリズムのクラスのコーディングを始めたばかりで、Scala の基礎をまだかなり学んでいます (そして頻繁に失敗しています)。課題は、配列の i 次統計量を計算するプログラムを作成することです。私の問題は、以下に書いたものをコンパイルして実行し、「値 [Array] の中から要素 "+which+" を選択しています」と出力し、失速することです。エラー メッセージはありません。以下のコードにはいくつかのエラーがあると確信しています。完全な開示のために、これは宿題です。助けていただければ幸いです。

編集：ヒントをありがとう、いくつか編集しました。select は配列のより小さな部分を見ていると思いますが、コードはまだ機能しません。25% の確率で正しい答えを吐き出し、残りの時間は同じことを行います。

object hw3v2 { 

  // 
  // partition 
  // 
  // this is the code that partitions 
  // our array, rearranging it in place 
  // 

  def partition(a: Array[Int], b: Int, c: Int): Int = { 

    val x:Int = a(c) 
    var i:Int = b

    for (j <- b to c-1)
      if (a(j) <= x) {
        i += 1
        a(i) = a(j)
        a(j) = a(i)

      }

    a(i+1) = a(c)
    a(c) = a(i+1)
    i + 1
  }

  def select(a: Array[Int], p: Int, r: Int, i: Int): Int = {

    if (p == r)
      a(0)

    else {
      val q = partition(a, p, r)
      val j = q - p + 1
      if (i <= j)
        select(a, p, q, i)
      else
        select(a, q+1, r, i-j)
    }
  }

  def main(args: Array[String]) {

    val which = args(0).toInt

    val values: Array[Int] = new Array[Int](args.length-1);
    print("Selecting element "+which+" from amongst the values ")
    for (i <- 1 until args.length) {
      print(args(i) + (if (i<args.length-1) {","} else {""}));
      values(i-1) = args(i).toInt;
    }
    println();

    println("==> "+select(values, 0, values.length-1, which))
  }
}
4

2 に答える 2

1

私はあなたに懇願します、このようにもっと書いてみてください：

def partition(a: Array[Int], b: Int, c: Int): Int = {
  val x: Int = a(c)
  var i: Int = b - 1

  for (j <- b to c - 1)
    if (a(j) <= x) {
      i += 1
      val hold = a(i)
      a(i) = a(j)
      a(j) = hold
    }

  a(i + 1) = a(c)
  a(c) = a(i + 1)
  i + 1
}

def select(i: Int, a: Array[Int]): Int =
  if (a.length <= 1)
    a(0)
  else {
    val q = partition(a, 0, a.length - 1)
    if (i <= q)
      select(i, a)
    else
      select(i - q, a)
  }

def main(args: Array[String]) {
  val which = args(0).toInt

  printf("Selecting element %s from amongst the values %s%n".format(which, args.mkString(", ")))

  val values = args map(_.toInt)
  printf("%nb ==> %d%n", select(which, values))
}

私の知る限り、これは元のコードと同等です。

于 2013-02-22T04:59:53.350 に答える
1

あなたの終了条件selectは、配列aの長さが 1 以下でなければならないということです。したがって、再帰呼び出しはselect無限にループします。私は推測することができます:あなたの目標はselect毎回異なる配列で動作することであるように思われるので、変更された配列を入力として渡す必要があります。したがって、私の推測では、 anと modified のpartition両方を返す必要があります。IntArray

アップデート

「i 次統計」が配列内の「i 番目」の最小要素を参照する場合、次のようにしてみませんか?

a.sorted.apply(i)
于 2013-02-22T07:48:15.313 に答える