7

サイズが4、9、16、または25（入力による）の配列があり、配列内の数値は同じですが1つ少なくなっています（配列サイズが9の場合、配列内の最大の要素は次のようになります） 8）数値は0で始まり 、配列全体をループして各要素を1つずつチェックすることなく、2つの配列が等しいことを比較できるように、配列のある種のチェックサムを生成するアルゴリズムを実行したいと思います。

この種の情報はどこで入手できますか？できるだけシンプルなものが必要です。ありがとうございました。

編集：私が欲しいものを明確にするために：

-配列内のすべての数値が異なるため、繰り返し要素（1）があるため、[0,1,1,2]は無効です。

-数字の位置が重要であるため、[0,1,2,3]は[3,2,1,0]と同じではありません

-配列には数値0が含まれるため、これも考慮に入れる必要があります。

編集：

さて、ここでフレッチャーのアルゴリズムを実装しようとしました：http: //en.wikipedia.org/wiki/Fletcher%27s_checksum#Straightforward

int fletcher(int array[], int size){
  int i;
  int sum1=0;
  int sum2=0;
  for(i=0;i<size;i++){
    sum1=(sum1+array[i])%255;
    sum2=(sum2+sum1)%255;
  }
  return (sum2 << 8) | sum1;
}

正直なところ、リターンラインが何をするのかわかりませんが、残念ながらアルゴリズムは機能しません。配列[2,1,3,0]と[1,3,2,0]の場合、同じチェックサムを取得します。

EDIT2：

もう1つ、Adlerチェックサム http://en.wikipedia.org/wiki/Adler-32#Example_implementationです。

#define MOD 65521;

unsigned long adler(int array[], int size){
  int i;
  unsigned long a=1;
  unsigned long b=0;
  for(i=0;i<size;i++){
    a=(a+array[i])%MOD;
    b=(b+a)%MOD;
  }
  return (b <<16) | a;
}

これも機能しません。配列[2,0,3,1]と[1,3,0,2]は同じチェックサムを生成します。私はここで希望を失っています、何かアイデアはありますか？

4

5 に答える 5

5

25個の整数の配列を考えてみましょう。あなたはそれが0から24までのユニークな整数の順列を含むことができると説明します。このページによると、25があります！（25階乗）可能な順列、つまり15511210043330985984000000。32ビット整数よりはるかに多くを含めることができます。

結論は、どんなに頑張っても衝突するということです。

さて、これが位置を説明する簡単なアルゴリズムです：

int checksum(int[] array, int size) {
  int c = 0;
  for(int i = 0; i < size; i++) {
    c += array[i];
    c = c << 3 | c >> (32 - 3); // rotate a little
    c ^= 0xFFFFFFFF; // invert just for fun
  }
  return c;
}
于 2012-06-05T10:17:15.783 に答える
1

私はあなたが望むものは次のスレッドの答えにあると思います：

高速順列->数値->順列マッピングアルゴリズム

順列がマップされている番号を取得し、それをチェックサムとして取得します。順列ごとにチェックサムが1つしかないため、衝突のない小さなチェックサムはあり得ません。

于 2012-06-05T08:10:36.130 に答える
1

加重和のチェックサムはどうですか？[0,1,2,3]の例を見てみましょう。最初にシードと制限を選択し、シードを7として選択し、10000007として制限しましょう。

a[4] = {0, 1, 2, 3}
limit = 10000007, seed = 7
result = 0
result = ((result + a[0]) * seed) % limit = ((0 + 0) * 7)) % 10000007 = 0
result = ((result + a[1]) * seed) % limit = ((0 + 1) * 7)) % 10000007 = 7
result = ((result + a[2]) * seed) % limit = ((7 + 2) * 7)) % 10000007 = 63
result = ((result + a[3]) * seed) % limit = ((63 + 3) * 7)) % 10000007 = 462

その[0、1、2、3]のチェックサムは462です。参照はhttp://www.codeabbey.com/index/wiki/checksumです

于 2015-05-15T08:21:43.100 に答える
0

1からNまでのN個の一意の整数の配列の場合、要素を合計するだけで常にN *（N + 1）/2になります。したがって、唯一の違いは順序にあります。「チェックサム」によって、いくつかの衝突を許容することを意味する場合、1つの方法は、連続する数値間の差を合計することです。したがって、たとえば、{1,2,3,4}のデルタチェックサムは1 + 1 + 1 = 3ですが、{1,3,2,1}のデルタチェックサムは-1 + -1 +-1=です。 -3。

衝突率や計算の複雑さに関する要件はありませんが、上記が適切でない場合は、位置に依存するチェックサムをお勧めします

于 2012-06-05T06:39:01.773 に答える
0

私が理解していることから、あなたの配列には0からまでの数の順列が含まれていますN-1。役立つチェックサムの1つは、辞書式順序での配列のランクです。どういう意味ですか ？与えられ0, 1, 2 たあなたは可能な順列を持っています

  1: 0, 1, 2
  2: 0, 2, 1
  3: 1, 0, 2
  4: 1, 2, 0
  5: 2, 0, 1
  6: 2, 1, 0

チェックサムは最初の数値になり、配列の作成時に計算されます。で提案された解決策があります

辞書式順序の順列のリストで、特定の順列のインデックスを見つけます

これは役立つ場合がありますが、最良のアルゴリズムは2次の複雑さであるように思われます。線形の複雑さに改善するには、階乗の値を事前にキャッシュする必要があります。

利点？ゼロ衝突。

編集：計算 値は、累乗の代わりに単項式に階乗が使用される多項式の評価のようなものです。したがって、関数は

f(x0,....,xn-1) = X0 * (0!) + X1 * (1!) + X2 * (2!) +...+ Xn-1 * (n-1!)

アイデアは、各値を使用して順列のサブ範囲を取得し、十分な値を使用して一意の順列を特定することです。

次に、（多項式の実装のように）実装します。

  1. 事前計算0！....からn-1！プログラムの開始時に
  2. 配列を設定するたびに、f（elements）を使用してチェックサムを計算します
  3. このチェックサムを使用してO（1）で比較します
于 2012-06-05T08:47:55.803 に答える