Board logo

標題: 資料結構 303 找關聯商品(難) [打印本頁]
作者: may    時間: 2025-3-28 12:43     標題: 資料結構 303 找關聯商品(難)

資料結構 303 找關聯商品
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 水果行賣五種水果，分別為「apple」、「watermelon」、「pawpaw」、「banana」和「pineapple」，今天有 N（3 ≤ N ≤ 10）位顧客來買水果。

(2) 請撰寫一程式，讓使用者輸入 N 位顧客買的水果名稱，找出任兩種水果最常被顧客一起購買的前三名組合與購買次數。

提示：五種水果兩兩一組，共有十種組合。

3. 輸入輸出：
輸入說明
第 1 列：正整數 N（3 ≤ N ≤ 10），為顧客人數。
第 2~N+1 列：N 位顧客買水果的資料，資料間以一個半形空白間隔。

輸出說明
請依照購買次數「由多到少」，輸出前三名最常被顧客一起購買的水果組合（任兩種）與購買次數，中間以一個半形空白間隔。

註：
　- 水果組合，請依照水果名稱的字典「由小到大」排序。
　- 若購買次數相同，請依序按照水果名稱的字典「由大到小」排序。

範例輸入1
5
apple watermelon pawpaw
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
範例輸出1
apple pawpaw 3
banana pineapple 2
pineapple watermelon 1
範例輸入2
7
apple watermelon pawpaw banana
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
apple watermelon pineapple
apple watermelon
範例輸出2
apple watermelon 3
apple pawpaw 3
pineapple watermelon 2
作者: may    時間: 2025-4-20 15:31

回復 1# may
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. map<string, int> mp;
  5. vector<pair<string, int>> v;
  6. string s;
  7. /*
  8. n：顧客人數。
  9. mp：紀錄每個水果組合出現的次數，鍵為「水果1 水果2」的字串。
  10. v：存放最終要排序用的 pair（水果組合，次數）。
  11. s：輔助字串，讀入用。*/

  13. void putIn(vector<string> v)
  14. {
  15.     int len=v.size();
  16.     for(int i=0; i<len-1; i++)
  17.     {
  18.         for(int j=i+1; j<len; j++)
  19.         {
  20.             string s1=v[i], s2=v[j];
  21.             if(s1>s2)
  22.                 swap(s1, s2);
  23.             mp[s1+" "+s2]++;
  24.         }
  25.     }
  26. }
  27. /*
  28. 這段程式的目的是：
  29. 每位顧客買的水果中，兩兩列出所有可能組合，並按照字典序（小→大）做字串組合作為鍵值，對應的值為出現次數。
  30. */
  31. bool compare(pair<string, int> p1, pair<string, int> p2)
  32. {
  33.     if(p1.second==p2.second)
  34.         return p1.first>p2.first;
  35.     else
  36.         return p1.second>p2.second;
  37. }
  38. /*
  39. 符合題目排序規則：
  40. 優先依照購買次數多排在前面。
  41. 如果次數相同，則依水果組合的字典序由大到小排。
  42. */
  43. int main()
  44. {
  45.     cin>>n;
  46.     getline(cin, s);
  47.     for(int i=0; i<n; i++)
  48.     {
  49.         getline(cin, s);
  50.         stringstream ss;
  51.         ss<<s;
  52.         vector<string> v;
  53.         string str;
  54.         while(ss>>str)
  55.             v.push_back(str);
  56.         putIn(v);
  57.     }
  58. /*
  59. 這段程式碼會
  60. 將每一行（顧客的水果清單）拆分成字串陣列，
  61. 然後丟到 putIn 裡處理所有可能的水果組合。
  62. */
  63.     for(auto p: mp)
  64.         v.push_back({p.first, p.second});
  65. /*
  66. 將 map 裡的資料轉成 vector<pair<string, int>> 好進行排序。
  67. */
  68.     sort(v.begin(), v.end(), compare);
  69. /*
  70. 使用自定義的 compare 進行排序。
  71. */
  72.     for(int i=0; i<3; i++)
  73.         cout<<v[i].first<<" "<<v[i].second<<endl;

  75.     return 0;
  76. }
複製代碼
作者: may    時間: 2025-4-20 15:55     標題: RE: 題目重點解析

回復 1# may
題目重點解析
有五種水果：apple、watermelon、pawpaw、banana、pineapple

有 N 位顧客（3 ≤ N ≤ 10），每位顧客都會買幾種水果。

你要統計這些顧客中，每兩種水果一起被買到的次數。

最後輸出購買次數最多的前三組水果組合與對應次數。

同組水果名稱要照字典順序由小到大排列。

若次數相同，要照水果組合的字典序由大到小排（例如：pineapple watermelon > banana pineapple）。
作者: may    時間: 2025-4-20 16:00

回復 3# may
測資:
測資00（基本測資）
5
apple banana
banana pineapple
apple pineapple
apple banana pineapple
pawpaw watermelon
預期輸出（可能順序如下）：

apple banana 2
apple pineapple 2
banana pineapple 2

測資 01（完全不同組合，沒有重複）
3
apple banana
pawpaw pineapple
watermelon banana
預期輸出：
apple banana 1
banana watermelon 1
pawpaw pineapple 1

測資 02（所有人都買相同兩樣）
4
apple banana
apple banana
apple banana
apple banana
預期輸出：
apple banana 4
（其他組合出現次數是 0，不列出）

測資 03（測試字典序處理）
5
watermelon banana apple
pawpaw apple
banana pawpaw
pineapple watermelon banana
apple pineapple pawpaw
預期輸出：
apple pawpaw 2
banana watermelon 2
pawpaw pineapple 1

測資 04
7
apple watermelon pawpaw banana
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
apple watermelon pineapple
apple watermelon
範例輸出
apple watermelon 3
apple pawpaw 3
pineapple watermelon 2



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://www.istak.org.tw/seed/) Powered by Discuz! 7.2