0

请帮助我找出我的 algo2() 函数出了什么问题。算法2的过程如下：

  • 将 N 个数字读入向量
  • 按降序对向量元素进行排序
  • 一个一个地读取每个剩余的元素
  • 当一个新元素到达时，如果它小于向量中的第 k 个元素，则将其忽略
  • 否则，它将被放置在数组中的正确位置，从向量中弹出一个元素
  • 最后，将打印第 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

这是工作代码。您需要删除您现在正在考虑的元素。

要点：您的排序工作正常，但我将其更改为我喜欢的方式。忽略排序器功能中的更改。专注于 algo2 函数。

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include<conio.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=0;ctr<ilan;ctr++)
    {
        for(index=ctr+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];
            }
        }
    }
    cout<<"\n";
    for(int i=0;i<ilan;i++)
     cout<<nums[i]<<" ";
    getch(); 
    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);
    while(k<nums.size())
    {
        int t=nums[k];
        nums.erase(nums.begin()+k);                
        if(nums[k-1]<t)
        {
            for(index=0;index<=(k-1);index++)
            {
                if(t>nums[index])
                {
                    nums.insert(nums.begin()+index,t);
                    nums.erase(nums.begin()+k);
                    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;
}
于 2013-06-23T08:54:43.140 回答
1

好的，我现在发现了问题：

如果你找到了一个更大的元素，你将它插入到适当位置的向量中，然后从第一个元素中移除最小的元素k，它现在位于位置k。到目前为止，还好。但是，您不会从向量的其余部分中删除刚在开头插入的元素。因此，在下一次迭代中，它会再次找到相同的元素。由于如果元素等于找到的元素，您也会这样做，因此结果是无限循环。

无论如何，这里有一个算法，它在更正后基本上和你的算法一样，但利用了标准库设施（当然，除了利用预制nth_element算法:-)）。另一个变化是我添加了一些错误检查。我没有改变的是您的算法执行输出这一事实。通常，算法应该只返回它的发现并将其留给调用者如何处理它。

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 回答