Board logo

標題: 710 FIFO分頁替換演算法 [打印本頁]
作者: 鄭又綸    時間: 2024-9-21 09:19     標題: 710 FIFO分頁替換演算法

本帖最後由 鄭又綸 於 2024-10-26 10:46 編輯

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
請撰寫一程式，實作FIFO（First in First out）分頁替換演算法，讓使用者輸入十個小於10的正整數，要儲存在四個記憶體空間中，請依序輸出每次經過FIFO演算法後的結果。輸出的每個值請給予兩個欄位寬並靠左對齊，若記憶體空間為Null時，以數字「0」表示。
FIFO規則：先進先出法，當記憶體空間滿的時候，會淘汰掉最先進入記憶體的資料。
分頁替換規則：輸入的資料若存在於記憶體空間中，則不動作；反之，則執行 FIFO規則。
提示：若使用 Java 語言答題，請以「JP」開頭命名包含 main 靜態方法的 class，評測系統才能正確評分。

3. 輸入輸出：
輸入說明
十個小於10的正整數

輸出說明
每次經過FIFO分頁替換演算法後的結果

範例輸入
7
5
1
2
5
3
5
4
2
3
範例輸出
7 0 0 0
7 5 0 0
7 5 1 0
7 5 1 2
7 5 1 2
3 5 1 2
3 5 1 2
3 4 1 2
3 4 1 2
3 4 1 2

程式輸出擷圖
下圖中的 黃色點 為 空格


本帖隱藏的內容需要回復才可以瀏覽
作者: 鄭又綸    時間: 2024-9-21 09:26

本帖最後由 鄭又綸 於 2024-9-21 09:28 編輯

Queue 的概念

queue（佇列）是一種資料結構，用來模擬生活中的「排隊」情境。在 queue 中，元素遵循「先進先出」（FIFO, First In First Out）的規則。這意味著，最先加入 queue 的元素會最先被取出，而新加入的元素會排在最後

你可以想像 queue 就像是一列排隊等候的人：

排隊加入（enqueue）：當一個新的人來排隊時，他會站到隊伍的最後面。
前面離開（dequeue）：當服務窗口處理排隊的人時，最前面的人先被服務並離開隊伍。
隊伍中的順序：隊伍中的順序是固定的，按照人們進來的先後順序排列，不會有人插隊到中間或前面。

以下是 queue 的一些特性：

FIFO（First In First Out）：最先加入的元素最先被取出。
只能從一端插入（尾端），另一端取出（前端）：這與「堆疊（stack）」不同，堆疊是「後進先出」（LIFO, Last In First Out），只能從一端進行操作。

基本語法和操作
要使用 queue，需要包含標頭檔 <queue> 。以下是 queue 的基本操作和用法：

引入 queue 標頭檔：
  1. #include <queue>  // 引入 queue 標頭檔
複製代碼
宣告 queue：

queue<資料型別> 變數名稱;
宣告一個資料型別為 int 的 queue：
  1. queue<int> q;  // 宣告一個空的整數佇列
複製代碼
基本操作（常用函式）：

push(x)：將元素 x 加入佇列的尾端。
pop()：移除佇列最前端的元素（FIFO 的原理）。
front()：取得佇列最前端的元素（即將被取出的元素）。
back()：取得佇列尾端的元素（最近加入的元素）。
empty()：檢查佇列是否為空。為空則回傳 true。
size()：回傳佇列中元素的個數。
操作範例：
  1. #include <iostream>
  2. #include <queue>  // 引入 queue 標頭檔

  4. using namespace std;

  6. int main() {
  7.     queue<int> q;  // 宣告一個整數型別的 queue

  9.     // 加入元素到佇列中
  10.     q.push(10);  // 佇列中有 10
  11.     q.push(20);  // 佇列中有 10, 20
  12.     q.push(30);  // 佇列中有 10, 20, 30

  14.     // 取出並顯示佇列中的元素
  15.     cout << "最前面的元素是: " << q.front() << endl;  // 輸出 10
  16.     cout << "尾端的元素是: " << q.back() << endl;    // 輸出 30
  17.    
  18.     // 移除最前面的元素
  19.     q.pop();  // 移除 10，佇列剩下 20, 30

  21.     cout << "最前面的元素是: " << q.front() << endl;  // 輸出 20
  22.     cout << "目前佇列的大小: " << q.size() << endl;  // 輸出 2

  24.     return 0;
  25. }
複製代碼
程式的運作流程

記憶體空間初始化：

程式中有四個記憶體空間，用來儲存輸入的數字。一開始這四個記憶體空間全都是「0」，表示它們是空的（用字串 "0000" 表示）。
輸入資料：

讓使用者輸入十個小於 10 的正整數。
如果當前記憶體空間還沒滿，就依序放進去。
當記憶體空間滿的時候（即已經有四個數字），每當有新的數字要進來時，就要使用 FIFO 規則來替換掉最早進入記憶體的數字。

FIFO 規則：

當記憶體空間已滿且新的數字不在記憶體中時，會先將最先進入記憶體的數字「淘汰」掉，然後再把新的數字放進去。
比如，假設記憶體空間中目前有 7 5 1 2，如果要放入新的數字 3，那麼 7 會被替換掉，變成 3 5 1 2。
輸出結果：

每次輸入或替換完畢後，都會輸出當前記憶體空間中的內容。
每個數字用兩個欄位寬顯示，左對齊。如果記憶體中有空位，則顯示為 0。
範例說明
假設輸入以下十個數字：7 5 1 2 5 3 5 4 2 3

前四次輸入（記憶體未滿）：

7 -> 7 0 0 0
5 -> 7 5 0 0
1 -> 7 5 1 0
2 -> 7 5 1 2
第五次輸入：

5 已經在記憶體中，所以記憶體不變：7 5 1 2
第六次輸入：

3 不在記憶體中，使用 FIFO 規則將 7 淘汰：3 5 1 2
第七次輸入：

5 已經在記憶體中，記憶體不變：3 5 1 2
第八次輸入：

4 不在記憶體中，使用 FIFO 規則將 5 淘汰：3 4 1 2
第九次輸入：

2 已經在記憶體中，記憶體不變：3 4 1 2
第十次輸入：

3 已經在記憶體中，記憶體不變：3 4 1 2
逐步解析程式碼
  1. #include<bits/stdc++.h>
  2. using namespace std;

  4. string s="0000"; // 初始記憶體空間，四個位置都是 0，表示空的。
  5. queue<char> q; // FIFO 用的佇列，來追蹤先進來的數字。

  7. int main() {
  8.     for(int i = 0; i < 10; i++) { // 要輸入 10 個數字
  9.         if(i < 4) { // 前四個數字直接放進記憶體
  10.             cin >> s[i]; // 依序放到字串 s 的位置
  11.             q.push(s[i]); // 加入佇列中
  12.         } else { // 超過四個數字之後，需要判斷是否替換
  13.             char in, ot;
  14.             cin >> in; // 輸入新的數字
  15.             if(s.find(in) == -1) { // 如果新的數字不在記憶體中
  16.                 q.push(in); // 加入佇列
  17.                 ot = q.front(); // 取出最先進來的數字（要被淘汰的）
  18.                 q.pop(); // 從佇列中移除最先進來的數字
  19.                 int idx = s.find(ot); // 找到這個數字在記憶體的位置
  20.                 s[idx] = in; // 替換成新的數字
  21.             }
  22.         }
  23.         // 輸出目前記憶體的狀態
  24.         printf("%c %c %c %c \n", s[0], s[1], s[2], s[3]);
  25.     }
  26.     return 0;
  27. }
複製代碼
作者: 柳侑辰    時間: 2024-9-21 11:52

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. queue<char> q;
  4. char in;
  5. string s="0000";
  6. int main()
  7. {
  8.     cin.tie(0);
  9.     cin.sync_with_stdio(0);
  10.     for(int i=0;i<10;i++)
  11.     {
  12.        if(i<4)
  13.        {
  14.            cin>>s[i];
  15.            q.push(s[i]);
  16.            cout<<s<<endl;
  17.        }else
  18.        {
  19.            cin>>in;
  20.            if(s.find(in)==-1)
  21.            {
  22.                s[s.find(q.front())]=in;
  23.                q.pop();
  24.                q.push(in);
  25.            }
  26.            cout<<s<<endl;
  27.        }
  28.     }
  29.     return 0;
  30. }
複製代碼
作者: 張駿霖    時間: 2024-9-21 11:53

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s="0000";
  4. queue<int> q;
  5. int main()
  6. {
  7.    for(int i=0; i<10; i++)
  8.    {
  9.        if(i<4)
  10.        {
  11.            cin>>s[i];
  12.            q.push(s[i]);
  13.        }else{
  14.        char in, ot;
  15.        cin>>in;
  16.        if(s.find(in)==-1){
  17.             q.push(in);
  18.        ot=q.front();
  19.        q.pop();
  20.        int idx=s.find(ot);
  21.        s[idx]=in;
  22.        }
  23.        }
  24.         printf("%c %c %c %c \n", s[0], s[1], s[2], s[3]);
  25.    }

  27.     return 0;
  28. }
複製代碼
作者: 洪承廷    時間: 2024-9-21 11:59

本帖最後由 洪承廷 於 2024-9-21 12:03 編輯
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s="0000";
  4. queue<char> q;
  5. int main()
  6. {
  7.     for(int i=0; i<10; i++)
  8.     {
  9.         if(i<4)
  10.         {
  11.             cin>>s[i];
  12.             q.push(s[i]);
  13.         }
  14.         else{
  15.             char in,out;
  16.             cin>>in;
  17.             if(s.find(in)==-1)
  18.             {
  19.                 q.push(in);
  20.                 out=q.front();
  21.                 q.pop();
  22.                 int idx=s.find(out);
  23.                 s[idx]=in;
  24.             }
  25.         }
  26.         printf("%c %c %c %c \n",s[0],s[1],s[2],s[3]);
  27.     }
  28.     return 0;
  29. }
複製代碼
作者: 高昀昊    時間: 2024-9-21 12:05

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s="0000";
  4. queue<char> q;
  5. int x;
  6. int main()
  7. {
  8.     for(int i=0; i<10; i++)
  9.     {
  10.         if(i<4)
  11.         {
  12.             cin>>s[i];
  13.             q.push(s[i]);
  14.         }else
  15.         {
  16.             char b, c;
  17.             cin>>b;
  18.             if(s.find(b) == -1)
  19.             {
  20.                 q.push(b);
  21.                 c=q.front();
  22.                 q.pop();
  23.                 x=s.find(c);
  24.                 s[x]=b;
  25.             }
  26.         }
  27.         cout<<s[0]<<" "<<s[1]<<" "<<s[2]<<" "<<s[3]<<" "<<endl;
  28.     }
  29.     return 0;
  30. }
複製代碼
作者: 徐啟祐    時間: 2024-9-22 21:43

本帖最後由 徐啟祐 於 2024-9-22 22:00 編輯
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s="0000";
  4. int main()
  5. {
  6.     queue<char> q;
  7.     for(int i=0;i<10;i++)
  8.     {
  9.         if(i<4)
  10.         {
  11.             cin>>s[i];
  12.             q.push(s[i]);
  13.         }
  14.         else
  15.         {
  16.             char in,op;
  17.             cin>>in;
  18.             if(s.find(in)==-1)
  19.             {
  20.                 q.push(in);
  21.                 op=q.front();
  22.                 q.pop();
  23.                 int idx=s.find(op);
  24.                 s[idx]=in;
  25.             }
  26.         }
  27.         printf("%c %c %c %c \n",s[0],s[1],s[2],s[3]);
  28.     }
  29.     return 0;
  30. }
複製代碼
作者: 高鋐鈞    時間: 2024-9-25 18:45

本帖最後由 高鋐鈞 於 2024-9-25 18:46 編輯
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. queue<char> q;
  4. int main()
  5. {
  6.     string s="0000";
  7.     for(int i=0; i<10; i++)
  8.     {
  9.         if(i<4)
  10.         {
  11.             cin>>s[i];
  12.             q.push(s[i]);
  13.         }else
  14.         {
  15.             char in, ot;
  16.             cin>>in;
  17.             if(s.find(in)==-1)
  18.             {
  19.                 q.push(in);
  20.                 ot=q.front();
  21.                 q.pop();
  22.                 int x=s.find(ot);
  23.                 s[x]=in;
  24.             }
  25.         }
  26.         printf("%c %c %c %c \n", s[0], s[1], s[2], s[3]);
  27.     }
  28.     return 0;
  29. }
複製代碼
作者: 陳宣廷    時間: 2024-10-23 00:19

本帖最後由 陳宣廷 於 2024-10-23 00:43 編輯

  1. #include<bits/stdc++.h>
  2. using namespace std;

  4. int main()
  5. {
  6.     string s="0000";
  7.     queue<char> q;

  9.     for(int i=0;i<10;i++)
  10.     {
  11.         if(i<4)
  12.         {
  13.             cin>>s[i];
  14.             q.push(s[i]);
  15.         }
  16.         else
  17.         {
  18.             char in,out;
  19.             cin>>in;
  20.             if(s.find(in)==-1)//不在記憶體中
  21.             {
  22.                 q.push(in);
  23.                 out=q.front();
  24.                 q.pop();
  25.                 int idx=s.find(out);
  26.                 s[idx]=in;
  27.             }
  28.         }
  29.         printf("%c %c %c %c \n",s[0],s[1],s[2],s[3]);
  30.     }

  32.     return 0;
  33. }
複製代碼
作者: 洪承廷    時間: 2024-10-26 23:01

  1. aaa
複製代碼




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