# 北軟107 problemD

###### tags: `北軟107`

## 競賽題目：

簡易最適配置法之記憶體管理 (Memory Management---Best fit)程式
說明：在作業系統中，最適配置法之記憶體管理單元能依需求分配夠大而且最接
近需求的閒置空間來放置程序 (Process) 程式。

例如：有 3 個程序(如下左圖)所需佔用的記憶體空間分別為 5、6、8 個單位。
閒置的記憶體空間如下右圖，有 3 個區塊、大小分別為 7、5、9 個單位，一個記
憶體單位大小等同 2 個等號。


程序配置前的記憶體空間是空白的 (如上右圖上半部分)，程序配置後的記憶體
空間是顯示程序號碼及數個等號 (如上右圖下半部分)。因採用最適配置法，P1
程序需要 5 個單位所以被配置到 >=5 單位的區塊 2，並用\=\=號填滿整區塊。P2 程
序需要 6 個單位所以被配置到 >=6 單位且最接近 6 個單位的區塊 1，並用\=\=號填
入該區塊，只留下 1 單位空間。P3 程序需要 8 個單位所以被配置到 >=8 單位且最
接近 8 個單位的區塊 3，並用\=\=號填入該區塊，只留下 1 單位空間。

目標：
1. 請寫一支程式如下圖所示，區塊數<6 和程序數<6，顯示相關訊息 (2 分)。
2. 可輸入記憶體區塊數量及程序數量(2分)。
3. 接著輸入每個記憶體區塊的大小，最後一個區塊輸入後才換行(4 分)。
4. 接著輸入每個程序所需的區塊大小，最後一個程序輸入後才換行(4 分)。
5. 接著採最適配置法依程序順序將相關資訊顯示出來(13 分)。

注意：不用處理資料輸入錯誤問題。


另一例子如下圖：
因採用最適配置法，
P1 程序需要 8個單位所以被配置到 >=8 單位的區塊2，並用\=\=號填滿整區塊。
P2 程序需要 7 個單位，因沒有 >=7 單位的空間，所以未被配置。
P3 程序需要 6個單位所以被配置到 >=6 單位的區塊1，並用\=\=號填滿整區塊。
P4 程序需要 6 個單位，因沒有 >=6 單位的空間，所以未被配置。


## 解題想法

由於這題給的記憶體區塊數與程序數非常少，所以這題我們可以直接暴力破解。
開6個迴圈，每個迴圈從0開始，運行條件為變數數值小於記憶體區塊數，且變數數值遞增。

接下來，我們就能夠將變數數值當成該程序選擇哪個記憶體區塊，判斷是否放得進去。
由於我們要求最適配置，所以我們要盡可能的讓記憶體區塊的記憶體剩餘最少。

所以，在我們做上一個步驟時，
我們要設一個變數count來記錄剩餘的記憶體數量，且這個變數的初始值非常大。
再設一個陣列select來記錄第i個程序放置在哪個記憶體區塊。
和一個紀錄整數的List**陣列**group來紀錄在第i個記憶體區塊內有哪些程序。

在六個迴圈的內部程式碼，我們開一個vec來複製紀錄區塊數的陣列，和一個item來複製紀錄程序大小的陣列，和一個put來記錄該程序是否有放進去記憶體內。

接下來開一個迴圈來記錄記憶體的剩餘數量，假設剩餘數量小於count，就將count設為目前剩餘的數量，然後更新陣列select和group。

接下來設計界面(最麻煩的部分)，這邊由於很直觀所以不多做講解。

## 程式碼(C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace problemD
{
    class Program
    {
        static String fixedString(string str)
        {
            return str.PadRight(16, ' ');
        }
        static void printPart1(int n,int[] spaceArray)
        {
            Console.Write("　　　　　█");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j <= spaceArray[i]; j++)
                {
                    Console.Write("█");
                }
            }
            Console.WriteLine();
        }
        static void printPart2(int n, int[] spaceArray)
        {
            Console.Write("　　　　　");
            for (int i = 0; i < n; i++)
            {
                Console.Write("█");
                Console.Write("".PadRight(spaceArray[i] * 2, ' '));
            }
            Console.Write("█");
            Console.WriteLine();
        }
        static void printPart2(string str,int n, int[] spaceArray)
        {
            Console.Write(str);
            for (int i = 0; i < n; i++)
            {
                Console.Write("█");
                Console.Write("".PadRight(spaceArray[i] * 2, ' '));
            }
            Console.Write("█");
            Console.WriteLine();
        }
        static void printPart2(string str, int n, int[] spaceArray, int[] programming, List<int>[] group)
        {
            Console.Write(str);
            for (int i = 0; i < n; i++)
            {
                Console.Write("█");
                string rst = "";
                for (int j = 0; j < group[i].Count(); j++)
                {
                    int id = group[i][j];
                    if (programming[id] == 0) continue;
                    rst += ("P" + (id + 1)).PadRight(programming[id] * 2, '=');
                }
                rst = rst.PadRight(spaceArray[i]*2, ' ');
                Console.Write(rst);
            }
            Console.Write("█");
            Console.WriteLine();
        }
        static void printPart3(int n, int[] spaceArray)
        {
            Console.Write("　　　　　　");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < spaceArray[i]; j++)
                {
                    Console.Write((j+1) + "-");
                }
                Console.Write("  ");
            }
            Console.Write("　");
            Console.WriteLine();
        }
        static void Main(string[] args)
        {
            int n, m;
            Console.WriteLine("記憶體管理程式-最適配置法(Best Fit)");
            Console.Write("請輸入記憶體區塊數(<6):");
            n = Convert.ToInt32(Console.ReadLine());
            Console.Write("請輸入程序數(<6):");
            m = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine();
            Console.WriteLine("請輸入各區塊大小(<10)---");
            int[] spaceArray = new int[6];
            int[] programArray = new int[6];
            for (int i = 0; i < 6; spaceArray[i] = 0, i++) ;
            for (int i = 0; i < 6; programArray[i] = 0, i++) ;
            for(int i = 0; i < n; i++)
            {
                Console.Write("區塊" + (i + 1) + ":");
                spaceArray[i] = Convert.ToInt16(Console.ReadKey().KeyChar - '0');
                Console.Write(", ");
            }
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("請輸入各程式所需大小(<10)---");
            for (int i = 0; i < m; i++)
            {
                Console.Write("程序" + (i + 1) + ":");
                programArray[i] = Convert.ToInt16(Console.ReadKey().KeyChar - '0');
                Console.Write(", ");
            }
            int[] select = new int[6];
            List<int>[] group = new List<int>[6];
            for (int i = 0; i < 6; select[i] = 0, i++);
            int count = 100000;
            for (int a = 0; a < n; a++)
            {
                for (int b = 0; b < n; b++)
                {
                    for (int c = 0; c < n; c++)
                    {
                        for (int d = 0; d < n; d++)
                        {
                            for (int e = 0; e < n; e++)
                            {
                                for (int f = 0; f < n; f++)
                                {
                                    int[] vec = new int[6];
                                    int[] item = new int[6];
                                    bool[] put = new bool[6];
                                    for (int i = 0; i < 6; i++)
                                    {
                                        vec[i] = spaceArray[i];
                                    }
                                    for (int i = 0; i < 6; i++)
                                    {
                                        item[i] = programArray[i];
                                    }
                                    if (vec[a] - item[0] >= 0)
                                    {
                                        put[0] = true;
                                        vec[a] -= item[0];
                                    }
                                    if (vec[b] - item[1] >= 0)
                                    {
                                        put[1] = true;
                                        vec[b] -= item[1];
                                    }
                                    if (vec[c] - item[2] >= 0)
                                    {
                                        put[2] = true;
                                        vec[c] -= item[2];
                                    }
                                    if (vec[d] - item[3] >= 0)
                                    {
                                        put[3] = true;
                                        vec[d] -= item[3];
                                    }
                                    if (vec[e] - item[4] >= 0)
                                    {
                                        put[4] = true;
                                        vec[e] -= item[4];
                                    }
                                    if (vec[f] - item[5] >= 0)
                                    {
                                        put[5] = true;
                                        vec[f] -= item[5];
                                    }
                                    bool find = false;
                                    int mn = 0;
                                    for (int i = 0; i < 6 && find == false; i++)
                                    {
                                        mn += vec[i];
                                    }
                                    if (mn < count)
                                    {
                                        select[0] = (put[0] == true ? a : -1);
                                        select[1] = (put[1] == true ? b : -1);
                                        select[2] = (put[2] == true ? c : -1);
                                        select[3] = (put[3] == true ? d : -1);
                                        select[4] = (put[4] == true ? e : -1);
                                        select[5] = (put[5] == true ? f : -1);
                                        for (int i = 0; i < 6; group[i] = new List<int>(), i++) ;
                                        for (int i = 0; i < select.Length; i++)
                                        {
                                            int val = select[i];
                                            if (val == -1) continue;
                                            group[val].Add(i);
                                        }
                                        count = mn;
                                    }                                   
                                }
                            }
                        }
                    }
                }
            }
            Console.WriteLine();
            Console.WriteLine();
            for (int i = 0; i <= m; i++)
            {
                if(i == 0)
                {
                    Console.WriteLine("程式編號　　　　所需大小　　　　區塊編號　　　　區塊大小　　　　剩餘空間");
                    continue;
                }
                Console.Write(fixedString(i.ToString()));
                Console.Write(fixedString(programArray[i - 1].ToString()));
                int sel = select[i - 1];
                if (sel != -1)
                {
                    Console.Write(fixedString((select[i - 1] + 1).ToString()));
                    Console.Write(fixedString(spaceArray[select[i - 1]].ToString()));
                    Console.Write(fixedString((spaceArray[select[i - 1]] - programArray[i - 1]).ToString()));
                }
                else
                {
                    Console.Write("未分配記憶體區塊");
                    Console.Write(fixedString(""));
                    Console.Write(fixedString(""));
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            printPart1(n, spaceArray);
            printPart2(n, spaceArray);
            printPart2("配置程序前", n, spaceArray);
            printPart2(n, spaceArray);
            printPart1(n, spaceArray);
            printPart3(n, spaceArray);
            printPart1(n, spaceArray);
            printPart2(n, spaceArray);
            printPart2("程序配置後", n, spaceArray,programArray,group);
            printPart2(n, spaceArray);
            printPart1(n, spaceArray);
        }
    }
}