0

課題に少し問題があります。私は、パンケーキの問題に対する独自の解決策を考え出すという課題を与えられました。

この 1 つの部分を除いて、ほとんどのコードを書き留めました (以下は疑似コードです)。

//assuming input is an array of [0...n-1] size
int maxValue = -infinity
for int i <- 0 to n-1 do
{
    for int j <-i to n-1 do
    {
       if A[j] > maxValue
       {
          maxValue <- A[j]
          maxPos <- j
    if ((maxPos == n-1) && (maxPos > i))
    {
        flip(i) //flipping starting from index i
    }
    /*the following is the bit i'm stuck on
    i know that should be able to flip the max value IN the array 
    (but not the end) to the n-1 term. 
    On the next iteration of the loop, i flip the maxValue (now held in the last 
    element) into the slot that is either at the beginning of the array, or at the
    element closest to the elements already sorted */
    maxValue <- -infinity

ランダムな短いコードで申し訳ありませんが、=(.

4

2 に答える 2

0

パンケーキの並べ替え:

パンケーキの並べ替えは、スパチュラをスタックの任意のポイントに挿入して、その上のすべてのパンケーキをひっくり返すために使用できる場合に、パンケーキの無秩序なスタックをサイズ順に並べ替える数学的問題の口語用語です。

パンケーキ数は、特定の数のパンケーキに必要なフリップの最大数です。

flip(array, i): 配列を 0 から i に反転します。

疑似コード パンケーキの並べ替え:

1) iMax = ソートされていない配列の最大要素のインデックス。

arr[0..unsorted_array_size -1] で最大要素インデックスのインデックスを検索します。

2) Flip(array, iMax) を呼び出す

配列のすべての要素を 0 から iMax インデックスに反転します。最大の要素が配列の最初の要素になります。

3) Flip(array, unsorted_array_size -1) を呼び出す

ソートされていない配列の最後に最大の要素を配置する完全なソートされていない配列を反転します。

複雑さ : 合計 O(n) フリップ操作が実行され、各フリップには O(n) 時間がかかります。したがって、複雑さは O(n^2) です。

http://javaexplorer03.blogspot.in/2015/11/pancake-sort-in-java.html

于 2015-11-22T10:46:00.577 に答える
0

私はあなたが立ち往生していると思いますinfinity。としてそのまま受け取ることができますlarge integer or long number。

于 2013-01-26T07:47:38.453 に答える