路徑:Tournament \ 1-16 \ 1 - Inv 2001 R1 \ Prerequisites

分數:1000

題目

程式介面

Class Name: Prerequisites
Mathod Name: orderClasses
Parameters: String[]
Returns: String[]
Method signature: string[] orderClasses(string[] classSchedule)

說明

學生在大學修課時,會遇到複雜的先修課問題,也就是某些課會有要求需先修完另外某些課後才能修,所以我們來寫一支幫助排定修課續順的程式。程式會輸入字串陣列,每一筆資料表示課程與此課程的先修課,格式大致如下:

{系所代碼}{課號}: {先修課} {先修課}

例如

CSE111: CSE110 MATH101

請依據以下規則排出修課的順序:

  1. 課程的先修課必須全部修過後才能修。
  2. 同時有多個課程可以修時,先修課號數字小的。
  3. 承上,如果數字相同時,則先修系所代碼按字母排序先的。
  4. 當輸入資料錯誤時,回傳空的字串陣列。例如無法修完先修課或是先修課不存在。

系統保證輸入

  • 系所代碼:3或4個字母[A-Z]。
  • 課號:100-999。
  • 如果沒有先修課會以冒號結尾。

範例

輸入:{
"CSE121: CSE110",
"CSE110:",
"MATH122:",
} 輸出:{"CSE110","CSE121","MATH122"} 輸入:{
"ENGL111: ENGL110",
"ENGL110: ENGL111"
} 輸出:{} 輸入:{
"ENGL111: ENGL110"
} 輸出:{} 輸入:{
"CSE258: CSE244 CSE243 INTR100"
"CSE221: CSE254 INTR100"
"CSE254: CSE111 MATH210 INTR100"
"CSE244: CSE243 MATH210 INTR100"
"MATH210: INTR100"
"CSE101: INTR100"
"CSE111: INTR100"
"ECE201: CSE111 INTR100"
"ECE111: INTR100"
"CSE243: CSE254"
"INTR100:"
} 輸出:{"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210","CSE254","CSE221","CSE243","CSE244","CSE258"}

解法

聽起來類似遊戲的技能樹,要學會B技能前先要學會A技能,很容易就想要去記錄使用者學習的狀態,找出下一個可以學習的,不過實際上真的這樣子想去寫的話就太複雜,畢竟不是要開發甚麼系統。這邊我利用簡單的減法反向思考,使用過濾和排序逐一取出下一個課程,並將課程從清單中刪去。

語法

採用較易理解的寫法,效能並非最好

C#

using System;
using System.Collections.Generic;
using System.Text;

namespace Prerequisites
{
    class Prerequisites
    {
        public string[] orderClasses(string[] classSchedule)
        {
            try
            {
                List<string> result = new List<string>();

                // parse
                Dictionary<string, List<string>> courses = new Dictionary<string, List<string>>();
                foreach (string line in classSchedule)
                {
                    string[] tmp = line.Split(':');
                    courses[tmp[0]] = new List<string>(tmp[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
                }

                string course = Next(courses);
                while (course != null)
                {
                    result.Add(course);
                    // 將修過的課從先修課中刪除
                    courses.Remove(course);
                    foreach (List<string> prerequisites in courses.Values)
                        prerequisites.Remove(course);
                    course = Next(courses);
                }
                if(courses.Count > 0)
                    return new string[0];
                return result.ToArray();
            }
            catch
            {
                return new string[0];
            }
        }

        private string Next(Dictionary<string, List<string>> courses)
        {
            // filter
            List<string> candidates = new List<string>();
            foreach (KeyValuePair<string, List<string>> pair in courses)
                if (pair.Value.Count == 0)
                    candidates.Add(pair.Key);

            if (candidates.Count == 0)
                return null;

            candidates.Sort(Compare);
            return candidates[0];
        }

        private int Compare(string cousre1, string course2)
        {
            int num1 = int.Parse(cousre1.Substring(cousre1.Length - 3));
            int num2 = int.Parse(course2.Substring(course2.Length - 3));
            if (num1 == num2)
            {
                string code1 = cousre1.Remove(cousre1.Length - 3);
                string code2 = course2.Remove(course2.Length - 3);
                return code1.CompareTo(code2);
            }
            else
                return num1.CompareTo(num2);
        }
    }
}

下載

VS2010 C# 版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()