0

私の algo2() 関数の何が問題なのかを見つけるのを手伝ってください。アルゴリズム 2 のプロセスは次のとおりです。

  • N 個の数値をベクトルに読み込む
  • ベクトル要素を降順に並べ替える
  • 残りの各要素は 1 つずつ読み取られます
  • 新しい要素が到着すると、ベクトルの k 番目の要素よりも小さい場合は無視されます
  • それ以外の場合は、配列内の正しい場所に配置され、ベクトルから 1 つの要素が突き出されます
  • 最後に、k番目の位置にある要素が出力されます

できることはすべて試しました。しかし、algo2() 関数を実行するたびに、単に実行が停止します。どうぞよろしくお願いいたします。ありがとうございました。

    #include <iostream>
    #include <stdlib.h>
    #include <math.h>
    #include <vector>

    using namespace std;

    vector<int> input()
    {
        vector<int> nums;
        int input;

        cout << "Please enter some integers (type 12345 to end):\n";
        do 
        {
            cin >> input;
            nums.push_back(input);
        }
        while(input!=12345);
        nums.pop_back(); //omits terminator value from the vector

        return nums;
    }

    vector<int> sorter(vector<int> nums,int ilan)
    {
        int index,ctr;
        for(ctr=1;ctr<=pow((ilan-1),2);ctr++)
        {
            for(index=1;index<ilan;index++)
            {
                if(nums[index]>nums[index-1])
                {
                    nums[index]+=nums[index-1];
                    nums[index-1]=nums[index]-nums[index-1];
                    nums[index]-=nums[index-1];
                }
            }
        }
        return nums;
    }

    void cardinal(int k)
    {
        if(k==11||k==12||k==13)
            cout << "th";
        else
        {
            while(k>10)
            {
                k=k%10;
            }
            switch(k)
            {
                case 1: {cout << "st"; break;}
                case 2: {cout << "nd"; break;}
                case 3: {cout << "rd"; break;}
                default: cout << "th";
            }
        }
    }

    void output(vector<int> nums,int k)
    {
        cout << "The " << k;
        cardinal(k);
        cout << " largest number is " << nums[k-1];
    }

    void algo2(vector<int> nums,int k)
    {
        int index;
        int cursor;
        nums = sorter(nums,k);
        for(cursor=k;cursor+1<nums.size();)
        {
            if(nums[k-1]<nums[cursor])
            {
                for(index=0;index<(k-1);index++)
                {
                    if(nums[cursor]>nums[index])
                    {
                        nums.insert(nums.begin()+index,nums[cursor]);
                        if(k+2==nums.size())
                            nums.erase(nums.begin()+k+1);
                        else
                            nums.erase(nums.begin()+k,nums.begin()+k+1);
                        break;
                    }   
                }
            }
            else
            {
                nums.erase(nums.begin()+cursor);
                break;
            }
        }
        output(nums,k);
    }

    int main()
    {
        vector<int> nums;
        int choice=0, k=0;

        cout << "Type the algorithm number you'll use (1 or 2): ";
        cin >> choice;
        cout << "Input k: ";
        cin >> k;

        //Algorithm 1
        if(choice==1)
        {
            nums = input();
            nums = sorter(nums,nums.size());
            output(nums,k);
        }
        //Algorithm 2
        else if(choice==2)
        {
            nums = input();
            algo2(nums,k);
        }

        cout << endl << endl;
        system("pause");
        return 0;
    }
4

3 に答える 3

1

OK、問題が見つかりました：

より大きな要素が見つかった場合は、それをベクターの適切な場所に挿入し、最初の から最小の要素を削除します。kこれは現在位置 にありkます。これまでのところ、問題ありません。ただし、最初に挿入した要素をベクトルの残りの部分から削除するわけではありません。したがって、次の反復では、まったく同じ要素が再び検出されます。要素が見つかった要素と等しい場合にもそれを行うため、結果は無限ループになります。

とにかく、修正後に本質的にあなたのものと同じことを行うアルゴリズムがありますが、標準ライブラリ機能を利用しています（もちろん、事前に作成されたnth_elementアルゴリズムを利用することは別として:-)）。もう 1 つの変更点は、エラー チェックを追加したことです。私が変更しなかったのは、アルゴリズムが出力を行うという事実です。通常、アルゴリズムは結果を返すだけで、それをどうするかは呼び出し元に任せるべきです。

void algo2_improved(std::vector<int> num, int k)
{
  if (num.size() < k)
  {
    std::cout << "there are too few elements in the vector!\n";
    return;
  }

  std::sort(num.begin(), num.begin()+k, std::greater<int>());

  while (num.size() > k)
  {
    if (num[k] >= num[k-1])
      std::rotate(std::upper_bound(num.begin(),
                                   num_begin()+k,
                                   num[k],
                                   std::greater<int>()),
                  num.begin()+k,
                  num.begin()+k+1);
    num.erase(num.begin()+k);
  }
  output(num, k);
}
于 2013-06-23T09:33:06.933 に答える
0

これは、K 番目に大きい数を見つけるための最良の方法だと思います。

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;

int partion(int arr[], int left, int right)
{
    int i = left;
    int j = right;
    int target = arr[i];

    while (i < j)
    {
        if (arr[j] > target)
            j--;
        arr[i] = arr[j];

        if (arr[i] <= target)
            i++;
        arr[j] = arr[i];
    }
    arr[j] = target;
    return j;
}


void quickSort(int arr[], int start, int end)
{
    if(start >= end)
        return;

    int pos = partion(arr, start, end);

    quickSort(arr, start, pos);
    quickSort(arr, pos+1, end);
}

int kth_element(int arr[], int start, int end, int k)
{
    int pos = partion(arr, start, end);
    if (pos == k)
        return arr[pos];
    else if (pos < k)
        kth_element(arr, pos + 1, end, k);
    else
        kth_element(arr, start, pos, k);
}
struct print
{
    void operator()(int a)
    {
        cout<<a<<" ";
    }
};
int main()
{
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(*arr);

    quickSort(arr, 0, len - 1);

    for_each(arr, arr + len, print());
    cout<<endl;

    cout<<"k = 2:  "<<kth_element(arr, 0, len - 1, len - 2)<<endl;
}
于 2013-06-23T09:31:20.300 に答える