0

過去のコンテストの問題を解決して、コンピュータサイエンスコンテストに参加する準備をしています。それらのほとんどは非常に簡単ですが、これは私を悩ませています...それは単純に見えますが、私はそれを行うことができません。

1と0の文字列がある場合：

100111010001111100101010

それを入力として受け取り、これを出力するコードは何でしょうか。

1:1 2:0 3:1 1:0 1:1 3:0 5:1 2:0 1:1 1:0 1:1 1:0

ここで、各コロンの左側の数字は、コロンの後の数字が表示された回数です。

だから、別の例...入力：

1100011

出力します：

2:1 3:0 2:1

問題によると、これはファックス送信を圧縮するために使用されるアルゴリズムに似ています。

Javaでの答えが最善ですが、私が本当に探しているのは、擬似コードまたはそれを行う方法についての考えです。

前もって感謝します。

4

3 に答える 3

5

This is called Run-Length-Encoding (RLE) and is used in a number of things (such as the Windows Bitmap file-format) to provide very basic compression (especially if the original includes lots of repeated values (like a bitmap or fax) containing a long run of the same colour).

int[] array = { ........ }; // your values...
for ( int i=0; i < array.Length; i++ )
{
   int count = 1;
   int value = array[i];

   // Consume until different..
   while ( i+1 < array.Length && array[i] == array[i+1] )
   { 
       count++; 
       i++ 
   }

   Console.WriteLine("{0}:{1}", count, value);
}

// OR, as suggested by @jon  [done in my head, so could probably be improved a lot...]
int count = 0;
int oldValue = -1;
for ( int i=0; i<array.Length; i++ )
{
   int newValue = array[i];
   count = ( newValue != oldValue ) ? 1 : count+1;

   if ( i+1 >= array.Length || array[i+1] != newValue)
   {
      Console.WriteLine("{0}:{1}", count, newValue);
   }

   oldValue = newValue;
}
于 2009-01-18T16:41:20.690 に答える
2

Just as a thought: why would you bother with the number on the right? It will always alternate between 1 and 0 won't it, so just assume it starts with 1 and encode an initial 0 if the actual sequence starts with 0. In other words, you'd end up with:

1 2 3 1 1 3 5 2 1 1 1 1

But basically you need to keep track of "what am I currently looking at?" and "how many of them have I seen"? If it changes, write out what you've been looking at and the count, and then update "what I'm looking at" to the new value and the count to 1, then keep going. Don't forget to write out the last value at the end of the data as well.

(I haven't given pseudocode or Java as I think you'll learn more by taking small hints than being presented with working code. If you need further hints though, just say.)

于 2009-01-18T16:40:59.117 に答える
0

私が本当に探しているのは、疑似コードまたはそれを行う方法についての考えです。

ここにいくつかの考えがあります：

  • バイト内のビットが 1 か 0 かをテストする方法: 「ビットごとの AND」演算を使用して、他のビットをマスクします。
  • バイト内の異なるビットが 1 か 0 かをテストする方法:
    • または、別のビットマスクを使用してください
    • または、マスクする前にバイト内のビットをシフトまたはローテーションします。

上記のメソッドを使用して、最初のバイトの 8 ビットを処理します。次に、これを繰り返して、次のバイトで次の 8 ビットを処理します。

一部の疑似コードは、次のようなものです。

main()
{
  Encoder encoder = new Encoder;
  foreach (byte b in inputStream)
  {
    encoder.input(b);
  }
  //tell the encoder that the stream is finished
  //that there will be no subsequent bytes
  ///and that the final bits should be flushed now
  encoder.finished();
}

class Encoder
{
  //member data
  bool m_b; //value of the most-recently-processed bit
  int m_n; //number of the most-recently-processed bits

  //public methods
  void finished()
  {
    //TODO format and write the {m_n}:{m_b} value to output
    //and reset m_n to zero
  }

  void input(byte b)
  {
    for int (i = 0; i < 8; ++i)
    {
      //get the bit value
      bool bit = getbit(b, i);
      //see whether we can append it
      bool canAppend =
        (bit == m_b) || //new bit is same as previous bit
        (0 == m_n); //no previous bit
      //flush previous bits if can't append
      if (!canAppend)
        finished();
      //append current bit
      m_b = bit;
      ++m_n;
    }
  }

  //private helper method
  bool getbit(byte b, int i)
  {
    //TODO return the bit value using a mask
  }
}

コードを記述するときは、特殊なケース (たとえば、同じ値を持つバイト内のすべてのビットを含む) を含め、さまざまな入力データを使用してテストすることも忘れないでください。

于 2009-01-18T17:14:46.817 に答える