5

こんばんは、人々！

私はかなり単純な問題を解決しようとしていますが..まあ、私にはできないようです。:)

アイデアは、n 個の要素を持つ FIFO リスト (FIFO キュー) があり、値 k (k < n) が与えられているということです。私の小さなプログラムは、要素を k 個の要素で左に移動する必要があります。(たとえば、n=4、k=3、a[]=(1, 2, 3, 4) の場合、結果は 4 1 2 3 になります)。

しかし、まあ、私はそれに近づくことはできません。

これは私がこれまでに書いたものです：

#include <iostream>
using namespace std;

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=0; i<=n-1; i++) t[i]=a[i];
        for (i=0; i<=k-1; i++) a[i]=a[i+k-1];
        for (i=k; i<=n-1; i++) a[i]=t[i+1];
}

int main () {
        int a[100];
        unsigned k, n, i;
        cout<<"n; k= "; cin>>n>>k;
        for (i=0; i<=n-1; i++) cin>>a[i];
        move (a, n, k);
        for (i=0; i<=n-1; i++) cout<<a[i]<<" ";
}

どんな助けでも大歓迎です。前もって感謝します。

4

6 に答える 6

2

あなたの質問を完全に理解したかどうかわかりません。しかし、配列の内容を効果的に回転させたいようです。

配列の内容を左に k 回回転します。次のことができます。

  • 最初の K 要素を反転します。
  • 残りの NK 要素を逆にします。
  • 配列全体を反転します。

例：

N = 5、K = 3、配列 = [1 2 3 4 5]

  • ステップ 1: 最初の 3 つの要素を逆にする: [3 2 1 4 5]
  • ステップ 2: 残りの 2 つの要素を反転: [3 2 1 5 4]
  • ステップ 3: 配列全体を反転: [4 5 1 2 3]

同じことを行う C++ 関数:

void move (int a[100], int n, int k) {
        int t[100];
        int i,j;
        for (i=k-1,j=0; i>=0; i--,j++) t[j]=a[i];
        for (i=n-1; i>=k; i--,j++) t[j]=a[i];
        for (i=n-1,j=0; i>=0; i--,j++) a[j]=t[i];
}

一定のスペースでそれを行うより良い方法は、その場で反転を行うことです:

void arr_rev(int a[100], int start, int end) {
        int temp;

        for(;start<end;start++,end--) {
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
        }
}

void move2 (int a[100], int n, int k) {
        arr_rev(a,0,k-1);
        arr_rev(a,k,n-1);
        arr_rev(a,0,n-1);
}
于 2010-02-03T18:23:15.727 に答える
1

左回転が必要なようですか？それはそれほど難しいことではないはずです。最初のk要素をキューから取り出し、残りの要素を左にシフトしn-k(おそらく一時配列の先頭に配置することにより)、k最後に最初の要素を順番に追加します。

この方法でコードを変更すると、次のようになります。

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=k; i<=n-1; i++) t[i-k]=a[i];
        for (int x=0; x<=k-1; x++) t[i++-k]=a[x];
}

これはまだ見苦しいので、ロジックをより明確にするために書き直すこともできますが、それは演習として残します。

これは、STL データ構造の使用が許可されていないことも前提としています。そうでない場合は、Jerry Coffin の回答を参照してください。

于 2010-02-03T18:02:59.960 に答える
1

これを C++ とタグ付けしたので、それを使用していると思います。その場合、ほとんどの場合、std::dequeデータを格納するために配列ではなく を使用する必要があります。また、キューには通常「前」と「後」があるため、「左」はあまり意味がありません。

(議論のためだけに) キューの後ろから k 個の要素を取得して前に移動することが必要であると仮定すると、次のようにすることができます。

typedef std::deque<your_type> data;

void push_to_front(data &d, int k) { 
    if (k > d.size())
        return;
    for (int i=0; i<k; i++) {
        data::value_type v = d.pop_back();
        d.erase(d.back());
        d.push_front(v);
    }
}

反対方向に回転させたい場合は、表と裏の役割を交換するだけです。

于 2010-02-03T18:03:19.120 に答える
0

「k 番目の要素をキューの先頭に移動する」という意味であれば、これが 1 つの方法です。

void move( int *a, unsigned n, unsigned k )
{ 
    int t; // To store the temporary for the k'th element 

    t = a[ k ];

    // Shift all the elements to the right by one.
    for( unsigned i = k; i > 0; --i )
        a[ i ] = a[ i - 1 ];

    // Put the k'th element at the left of the queue.
    a[ 0 ] = t;
}
于 2010-02-03T18:08:06.940 に答える
0 
#include <iostream>
#include <list>
template <typename T>
void Rotate(std::list<T>& list, int k){
    for(int i=0; i<k; ++i){
        T tmp(list.back());
        list.pop_back();
        list.push_front(tmp);
    }
}
int main(){
    std::list<int> ints;
    ints.push_back(1); ints.push_back(2);
    ints.push_back(3); ints.push_back(4);
    Rotate(ints,2);
    for(std::list<int>::const_iterator i = ints.begin(); i!=ints.end(); ++i)
        std::cout << *i << std::endl;
    return 0;
}

出力します:

3
4
1
2
于 2010-02-03T18:19:37.643 に答える