0

ここにアルゴリズムhttp://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.htmlが あり、これが私のコードです

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans,counter=0,a,temp=0,time=0;
    while(temp<n){
        cin>>a;
        if(counter==0)
        {
            counter=1;
            ans=a;
        }
        else if(counter>0){
            if(ans==a)
                ++counter;
            else
                --counter;
        }
        ++temp;
    }
    cout<<"The number "<<ans<<" is in the more majority ";
}

そして私の問題は、あなたが6 6 1 2 3を与えるとき、3がより多数派であると言うことです

私の問題はどこですか？ありがとう

4

2 に答える 2

2

アルゴリズムを正しく実装しましたが、正しく解釈しませんでした。

アルゴリズムは、過半数の要素 (要素の半分以上がその特定の要素) があると想定し、それを返します。仮定が間違っている場合は、シーケンス全体を 2 回実行して、実際に過半数があるかどうかを確認する必要があります。

あなたの例では過半数がないため、アルゴリズムは機能しません。

于 2013-10-28T19:48:48.943 に答える
1

与えられたデータに対して期待される答えが得られたと思います。重要なのは、リンクされたページからのこの引用です。

「私たちが終わったとき、過半数があれば、現在の候補者が多数派の要素です。」

この場合、過半数がないため、アルゴリズムは無効な結果を返します。入力して再試行してください6 6 6 1 2

以下は、教授が受け入れる可能性が低い配列を使用しない実装です。

#include <iostream>
using namespace std;
int majority(int n,int &ans,int counter){
  int a,i;
  if (!n) return 0;
  cin>>a;
  if (!counter) ans=a;
  counter+=2*(ans==a)-1;
  i=majority(n-1,ans,counter);
  return i+(ans==a);
}
int main(){
  int n,ans;
    cin>>n;
     if (n/2 < majority(n,ans,0))
        cout<<"The number "<<ans<<" is in the more majority "<<endl;
     else 
        cout<<"No majority"<<endl;
}
于 2013-10-28T19:47:47.567 に答える