caspar1 发表于 2022-5-23 19:55:34

寫不出來的題目！！求救

這台機器有四顆功能鍵跟數字小鍵盤
功能鈕上分別寫著
1.Insert
2.Query MAX
3.Query MIN
4.Print Sorted Array
旁邊寫著一行粗字: 極值經查詢後將會刪除
題目看到這各位也明瞭了吧
請你寫出這台機器的程式可以插入數字並且查詢其中的最大值與最小值注意：
本題不可使用Max、Min、Sort()函式
輸入說明
每行輸入開頭有四種情形
1: 插入操作，其後會跟著一數字 N 代表插入的數字 (0 ≤ N ≤ 231-1)
2: 查詢最大值
3: 查詢最小值
4: 列印出排序好的陣列
同一時間內最多有 100,000 個數字
輸出說明
每筆查詢輸出一行
每行只有一個數字
範例輸入
1 3
1 100
2
1 4
3
範例輸出
100
3

求助 謝謝各位大佬了

傻眼貓咪 发表于 2022-5-23 20:02:46

最多有 100,000 個數字? N <= 2^31 - 1?

caspar1 发表于 2022-5-23 20:22:38

傻眼貓咪 发表于 2022-5-23 20:02
最多有 100,000 個數字? N

應該是總共儲存的數字數量

傻眼貓咪 发表于 2022-5-23 20:32:21

caspar1 发表于 2022-5-23 20:22
應該是總共儲存的數字數量

题目问题不难，根本就是初学者等级也称不上，难是最大值，这才是重点。
目前我所知道的所有排序法，其最优的最坏时间复杂度也都要 O(n + k)，但你的 n 最大是 100000，k 最大是 2^31-1 = 2147483647，如何排序呢？

caspar1 发表于 2022-5-23 20:40:25

傻眼貓咪 发表于 2022-5-23 20:32
题目问题不难，根本就是初学者等级也称不上，难是最大值，这才是重点。
目前我所知道的所有排序法，其最 ...

我的想法是使用 linked list 去做 stack ， 在使用 insertion sort 去排序我所放入的數字，假設忽略掉最大值得問題。這樣是可行的嗎

傻眼貓咪 发表于 2022-5-23 20:46:56

caspar1 发表于 2022-5-23 20:40
我的想法是使用 linked list 去做 stack ， 在使用 insertion sort 去排序我所放入的數字，假設忽略掉最 ...

可以

caspar1 发表于 2022-5-25 15:59:11

傻眼貓咪 发表于 2022-5-23 20:46
可以

//S10350106 陳柏宇
#include <iostream>
using namespace std;

int ch ,num ,i = 0;
int ary;

void insertionSort()
{
    int temp;
    for(int k = 0;k < i;k++)
    {
      for(int n = 0;n < i-k-1;n++)
      {
            if(ary >= ary)
            {
                temp = ary;
                ary = ary;
                ary = temp;
            }
      }
    }
}

int main()
{
    cout << "Enter 1 : push value to ary" << endl;
    cout << "Enter 2 : search max value" << endl;
    cout << "Enter 3 : search min value" << endl;
    cout << "Enter 4 : display ary" << endl;
    while(1)
    {
      cout << "Enter your choice: " << endl;
      cin >> ch;
      switch(ch)
      {
            case 1:
            {
                cout << "Enter value to ary : " << endl;
                cin >> num;
                ary = num;
                i = i + 1;
                insertionSort();
                break;
            }
            case 2:
            {
                cout << "max value is : " << ary << endl;
                break;
            }
            case 3:
            {
                cout << "min value is : " << ary << endl;
                break;
            }
            case 4:
            {
                for(int j = 0;j < i;j++)
                {
                  cout << ary << " " << endl;
                }
                break;
            }
      }
    }
    return 0;
}

最後改成用陣列了，請問要如何達到查詢後刪除極值的效果，我試過很多種方式，但沒辦法刪除，只能將它變成ＮＵＬＬ

傻眼貓咪 发表于 2022-5-25 16:29:51

你都已经用 C++ 了，为什么不用 vertor？
#include <iostream>
#include <vector>

using std::vector;
vector<int> Ver;

void sort() {
        int N = Ver.size();
        for (int i = 0; i < N - 1; ++i) {
                for (int j = i + 1, t; j < N; ++j) {
                        if (Ver < Ver) {
                                t = Ver;
                                Ver = Ver;
                                Ver = t;
                        }
                }
        }
}

using std::cout, std::endl;
int main(void) {
        int arr[] = { 13, 7, 96, 58, 32 };
        for (const int &num: arr) {
                Ver.push_back(num);
        }
       
        sort();
       
        for (const int&num: Ver) {
                cout << num << " ";
        }
        cout << endl;
        cout
                << "最大值：" << Ver.back() << endl
                << "最小值：" << Ver << endl;
}7 13 32 58 96
最大值：96
最小值：7

caspar1 发表于 2022-5-25 16:41:59

傻眼貓咪 发表于 2022-5-25 16:29
你都已经用 C++ 了，为什么不用 vertor？

小弟還是新手，很多不懂哈哈哈 感謝您！

jhq999 发表于 2022-5-25 16:56:45

本帖最后由 jhq999 于 2022-5-25 16:59 编辑

傻眼貓咪 发表于 2022-5-25 16:29
你都已经用 C++ 了，为什么不用 vertor？

借阁下的代码一用
#include <iostream>
using namespace std;

int ch ,num ,i = 0;
int ary={0};

void insertionSort()
{
        int temp, k = 0;
        for(;k < i;k++)if(ary<ary)break;

        for(;k < i-1;k++)
        {
                temp=ary;
                ary=ary;
                ary=temp;
        }

}
int main(void) {
       int a=0;
           while (scanf("%d",&a))
           {
                   ary=a;
                   i++;
                   insertionSort();
           }
               
      for (int num: ary) {
                cout << num << " ";
      }
      cout << endl;
      cout
                << "最大值：" << ary << endl
                << "最小值：" << ary << endl;
                return 0;
}
13 7 96 58 32 a
7 13 32 58 96 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
最大值：96
最小值：7
页: [1]
查看完整版本: 寫不出來的題目！！求救