第一題

公司每年定期為員工實施健康檢查測量血壓，血壓的值包含收縮壓(較高者)與舒張壓(較低者)。
在測量完所有員工的兩項血壓數值後，公司會統計並輸出所有員工之收縮壓與舒張壓的平均值與中位數以資參考。
一串數字的中位數，是這些數字依序居中的值，例如：3,7,1,9,5的中位數是5；而5,8,2,6的中位數是5和6的平均(無條件捨去小數位)。
請協助完成函式split − range()以完成計算員工兩項血壓的中位數值。(注意：本程式並未使用排序來找出中位數。)

輸入格式：

  • n：員工數
  • ha1, …, han：員工的收縮壓
  • hb1, …, hbn：員工的舒張壓

輸出格式：

  • ha_avg : 員工收縮壓平均值
  • hb_avg : 員工舒張壓平均值
  • ha_md : 員工收縮壓中位數
  • hb_md : 員工舒張壓中位數

需要完成及繳交的函式（擇一程式語言完成作答即可）：

static void Split_Range(int split_pos, int mid, ref int left, ref int right) 函式

  • split_pos: 分割點位置
  • mid: 中位數位置
  • left: 排序左端
  • right: 排序右端
  • 此函式依照呼叫split函數的結果(split_pos)，來逐漸縮小尋找的範圍。

static void Split_Range(int split_pos, int mid, ref int left, ref int right) {
    //請完成並繳交本函式
}

void split_range(int split_pos, int mid, int *left, int *right) 函式

  • split_pos: 分割點位置
  • int mid: 中位數位置
  • int *lef: 排序左端
  • int *right: 排序右端
  • 此函式依照呼叫split函數的結果(split_pos)，來逐漸縮小尋找的範圍。

void split_range(int split_pos, int mid, int *left, int *right) {
    // 請完成並繳交本函式
}

private static int[] splitRange(int splitPos, int mid, int left, int right) 函式

  • splitPos: 分割點位置
  • mid: 中位數位置
  • left: 排序左端
  • right: 排序右端
  • 此函式依照呼叫split函數的結果(splitPos)，來逐漸縮小尋找的範圍。

private static int[] splitRange(int splitPos, int mid, int left, int right) {
    //請完成並繳交本函式
}

def split_range(pivot_position, mid, left, right): 函式

  • pivot_position: 分割點位置
  • mid: 中位數位置
  • left: 排序左端
  • right: 排序右端
  • 此函式依照呼叫split函數的結果(pivot_position)，來逐漸縮小尋找的範圍。

def split_range(pivot_position, mid, left, right):
    #請完成並繳交本函式


測資

範例測資：
測資1
輸入
5
139 93 121 142 116
68 89 58 67 83
輸出
122
73
121
68

測資2
輸入
4
125 132 130 108
96 67 82 96
輸出
123
85
127
89

測資3
輸入
3
149 147 119
77 68 70
輸出
138
71
147
70

測資4
輸入
10
108 140 141 132 140 100 116 116 94 90
89 55 84 77 79 91 74 72 85 99
輸出
117
80
116
81

測資5
輸入
1
134
55
輸出
134
55
134
55


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using System;

namespace Q1
{
    class Program
    {
        static int Average(int[] x)
        {
            int sum = 0;
            for (int i = 0; i < x.Length; ++i)
            {
                sum += x[i];
            }
            return sum / x.Length;
        }

        static int Split(int[] x, int left, int right)
        {
            int focus_data = x[left];
            int focus_pos = left, tmp;

            for (int i = left + 1; i <= right; ++i)
            {
                if (x[i] < focus_data)
                {
                    tmp = x[++focus_pos];
                    x[focus_pos] = x[i];
                    x[i] = tmp;
                }
            }

            tmp = x[left];
            x[left] = x[focus_pos];
            x[focus_pos] = tmp;

            return focus_pos;
        }

        static void Split_Range(int split_pos, int mid, ref int left, ref int right)
        {
            // 你的程式碼
        }

        static int half(int[] data)
        {
            int value = data[data.Length / 2];
            for (int i = data.Length / 2; i < data.Length; ++i)
            {
                if (data[i] < value)
                    value = data[i];
            }
            return value;
        }

        static int Midian(int[] x)
        {
            int left = 0, right = x.Length - 1, mid = right / 2, split_pos;
            while (true)
            {
                split_pos = Split(x, left, right);
                if (split_pos == mid) break;
                else Split_Range(split_pos, mid, ref left, ref right);
            }

            if (x.Length % 2 == 1) return x[mid];
            else return (x[mid] + half(x)) / 2;
        }

        static void Main(string[] args)
        {
            //Console.Write("input n: ");
            //int n = 
            Convert.ToInt32(Console.ReadLine());
            int[] ha, hb;
            int ha_avg, hb_avg, ha_md, hb_md;

            ha = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), item => Convert.ToInt32(item));
            hb = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), item => Convert.ToInt32(item));

            ha_avg = Average(ha);
            hb_avg = Average(hb);
            ha_md = Midian(ha);
            hb_md = Midian(hb);
            Console.WriteLine(ha_avg + "\n" + hb_avg + "\n" + ha_md + "\n" + hb_md);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def average(data, n):
    avg = 0
    for x in data:
        avg += x
    return avg//n

def split(data, left, right):
    pivot = data[left]
    pivot_position = left
    for i in range(left+1,right+1):
        if data[i] < pivot:
            pivot_position += 1
            data[i], data[pivot_position] = data[pivot_position], data[i]
    data[left], data[pivot_position] = data[pivot_position], data[left]
    return pivot_position

def split_range(pivot_position, mid, left, right):
	
# 你的程式碼
	
def half(data, n):
    value = data[n//2]
    for i in range(n//2,n):
        if data[i] < value:
            value = data[i]
    return value

def median(data, n):
    left = 0
    right = n-1
    mid = (left+right)//2

    while(True):
        pivot_position = split(data, left, right)
        if pivot_position == mid:
            break
        else:
            left,right = split_range(pivot_position, mid, left, right)

    if n%2 == 1:
        return data[mid]
    else:
        return (data[mid] + half(data, n))//2

num = int(input())
systolic = list(map(int,input().split()))
diastolic = list(map(int,input().split()))

sy_average = average(systolic, num)
dia_average = average(diastolic, num)
sy_median = median(systolic, num)
dia_median = median(diastolic, num)
print(sy_average, dia_average, sy_median, dia_median,sep='\n')
第二題

台灣兒童保護基金會募集發票後，請志工協助對獎並統計中獎金額製作出公開報表，供捐贈者自由查閱。
統一發票獎別及獎金如下：

一張發票若同時符合2個獎項，則獎金以最高獎金為主，例如發票號碼同時符合五獎及六獎，則以五獎判定。
對獎主程式將呼叫WinPrize()函式以計算並回傳一張發票的中獎金額，據以統計全部發票的中獎總金額。


輸入格式：

  • W：頭獎號碼，其中W為8碼字串
  • N：發票總數，其中N為整數， 1≤N≤20
  • P1: 第一張發票
  • ...
  • PN: 第N 張發票

輸出格式：

  • M: 中獎總金額


需要完成及繳交的函式（擇一程式語言完成作答即可）：

static int WinPrize(string W, string P)函式

  • W頭獎發票號碼，其長度始終為8，內容為0到9
  • P發票號碼，其長度始終為8，內容為0到9
  • 此函式計算並回傳發票中獎金額。

static int WinPrize(string W, string P) {
    // 請完成並繳交本函式
}

int WinPrize (char W[], char P[])函式

  • W頭獎發票號碼，其長度始終為8，內容為0到9
  • P發票號碼，其長度始終為8，內容為0到9
  • 此函式計算並回傳發票中獎金額。

int WinPrize (char W[], char P[]) {
    // 請完成並繳交本函式
}

private static int WinPrize(String W, String P)函式

  • W頭獎發票號碼，其長度始終為88，內容為00到99
  • P發票號碼，其長度始終為88，內容為00到99
  • 此函式計算並回傳發票中獎金額。

private static int WinPrize(String W, String P) {
    // 請完成並繳交本函式
}

def WinPrize(W, P)函式

  • W頭獎發票號碼，其長度始終為8，內容為0到9
  • P發票號碼，其長度始終為8，內容為0到9
  • 此函式計算並回傳發票中獎金額。

def WinPrize(W, P):
    # 請完成並繳交本函式


測資

範例測資：
測資1
輸入
13859285
3
38592769
42893285
32398733
輸出
200

測資2
輸入
39384729
4
93859284
38494729
39472859
39485739
輸出
1000

測資3
輸入
22385928
3
22385927
38420848
48347982
輸出
0

測資4
輸入
00384929
3
82948372
00374872
82984929
輸出
4000

測資5
輸入
98384928
2
98384928
93849284
輸出
200000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System;

namespace csharp
{
    class Q2
    {
        static int WinPrize(string W, string P)
        {
            // 你的程式碼
        }

        static void Main()
        {
            string W = Console.ReadLine(); // 頭獎號碼
            string P; // 發票號碼
            int N = Convert.ToInt32(Console.ReadLine()); // 發票總數
            int M = 0; // 中獎總金額

            for (int i = 0; i < N; i += 1)
            {
                P = Console.ReadLine();
                M += WinPrize(W, P);
            }
            Console.WriteLine(M);
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
def WinPrize(W, P):
	
# 你的程式碼

if __name__ == '__main__':
    W = input()
    N = int(input())
    M = 0
    
    for i in range(N):
        P = input()
        M += WinPrize(W, P)
    print(M)
第三題

一小時音樂廣播節目中共有4個單元，每單元結束時會進2分鐘的廣告，因此每個單元最多僅能播放13分鐘的歌曲。

單元中的音樂由AI程式從DJ準備的音樂歌單中，依下列規則選擇播放：

  1. 每首歌僅能播放一次，且須完整播完，不能中間卡歌。
  2. 歌曲播放順序以音樂歌單中長度最長且能完整播完的優先。若兩首歌曲長度相同，編號較大者優先選擇播放。
  3. 若有單元剩餘時間（進廣告前）無法完整播放下一首歌，則由節目DJ串場直至進廣告為止。

範例

　　DJ音樂歌單共有M=15首音樂，每首音樂的資訊記錄為<音樂編號，音樂長度>，15首音樂分別記錄為
　　<1, 210>,<2, 246>,<3, 252>,<4, 192>, <5, 186>,
　　<6, 282>,<7, 168>,<8, 162>,<9, 90>,<10, 234>,
　　<11, 252>,<12, 210>,<13, 258>,<14, 210>,<15, 204>。

　　我們根據音樂長度將音樂歌單由大到小排序，若音樂長度相同，則以音樂編號大者優先排序，其順序為
　　<6, 282>, <13, 258>,<11, 252>, <3, 252>, <2, 246>,
　　<10, 234>, <14, 210>, <12, 210>, <1, 210>, <15, 204>,
　　<4, 192>,<5, 186>, <7, 168>, <8, 162>, <9, 90>。

　　因此四個單元的歌單為：

　　第一個單元13分鐘，歌曲 6, 13, 10，剩餘6秒；

　　第二個單元13分鐘，歌曲 11, 3, 2，剩餘30秒；

　　第三個單元13分鐘，歌曲 14, 12, 1, 9，剩餘60秒；

　　第四個單元13分鐘，歌曲 15, 4, 5, 7，剩餘30秒。

　　請協助完成程式中MusicOrder函式，回傳該單元的音樂播放清單。


輸入格式：

  • M：音樂歌單的歌曲數，音樂編號就是1到M。
  • X1 ... XM：每一首音樂的時間長度(單位：秒)，0 < Xi ≤ 600，其中1 ≤ i ≤ M，兩數之間以一空格分隔。

輸出格式：

  • Y1 … Yk T1：第一單元音樂播放清單及剩餘時間，兩數之間以一空格分隔。
  • Y1 … Yk T2：第二單元音樂播放清單及剩餘時間，兩數之間以一空格分隔。
  • Y1 … Yk T3：第三單元音樂播放清單及剩餘時間，兩數之間以一空格分隔。
  • Y1 … Yk T4：第四單元音樂播放清單及剩餘時間，兩數之間以一空格分隔。


需要完成及繳交的函式（擇一程式語言完成作答即可）：

int *MusicOrder(int chapter_len, int M, int *X_sorted, int *X_sorted_id, int *music_list)函式

  • 整數chapter_len代表每單元所剩時間。
  • 整數M代表音樂歌單歌曲數。
  • 陣列X_sorted代表排序後的音樂歌單時長。
  • 陣列X_sorted_id代表排序後的音樂清單編號。
  • 陣列music_list代表該單元的音樂播放清單。
  • 此函式計算該單元的音樂播放清單與剩下未播放音樂的時間長度。

int *MusicOrder(int chapter_len, int M, int *X_sorted, int *X_sorted_id, int *music_list) {
    // 請完成並繳交本函式

    return music_list;
}

public static int[] MusicOrder(int chapter_len, int M, int[] X_sorted, int[] X_sorted_id, int[] music_list)函式

  • 整數chapter_len代表每單元所剩時間。
  • 整數M代表音樂歌單歌曲數。
  • 陣列X_sorted代表排序後的音樂歌單時長。
  • 陣列X_sorted_id代表排序後的音樂清單編號。
  • 陣列music_list代表該單元的音樂播放清單。
  • 此函式計算該單元的音樂播放清單與剩下未播放音樂的時間長度。

public static int[] MusicOrder(int chapter_len, int M, int[] X_sorted, int[] X_sorted_id, int[] music_list)
{
    // 請完成並繳交本函式

    return music_list;
}

def MusicOrder(chapter_len, X_sorted, X_sorted_id)函式

  • 整數chapter_len代表每單元所剩時間。
  • 串列X_sorted代表排序後的音樂歌單時長。
  • 串列X_sorted_id代表排序後的音樂清單編號。
  • 此函數計算該單元的音樂播放清單與剩下未播放音樂的時間長度。

def MusicOrder(chapter_len, X_sorted, X_sorted_id): # 回傳該單元的音樂播放清單
    # 請完成並繳交本函式


測資

範例測資：
測資1
輸入
1
800
輸出
780
780
780
780

測資2
輸入
2
300 300
輸出
2 1 180
780
780
780

測資3
輸入
5
60 100 200 300 400
輸出
5 4 1 20
3 2 480
780
780

測資4
輸入
5
638 527 416 354 223
輸出
1 142
2 5 30
3 4 10
780

測資5
輸入
10
272 623 226 398 452 328 705 646 172 763
輸出
10 17
7 75
8 134
2 157

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def MusicOrder(chapter_len, X_sorted, X_sorted_id): # 回傳該單元的音樂播放清單

# 你的程式碼
	
if __name__ == '__main__':
    M = int(input()) # 音樂歌單歌曲數M
    X = [None] * M # 音樂歌單時長
    X_sorted = [None] * M # 排序後的音樂歌單時長
    X_sorted_id = [None] * M #排序後的音樂清單編號

    X_all = input() # 輸入音樂歌單時長
    X = X_all.split(' ')
    X = list(map(int, X))
    
    # 插入排序（由大至小）
    X_sorted[0] = X[0]
    X_sorted_id[0] = 0
    for i in range(1, M):
        key = X[i]
        j = i - 1
        while(j>=0 and X_sorted[j]<=key):
            X_sorted[j+1] = X_sorted[j]
            X_sorted_id[j+1] = X_sorted_id[j]
            j -= 1
        X_sorted[j+1] = key
        X_sorted_id[j+1] = i
    
    # 安排四個單元的歌單
    chapter_len = 13 * 60 # 每個單元時長
    rounds = 4 # 單元數量
    
    for r in range(rounds):
        music_list = MusicOrder(chapter_len, X_sorted, X_sorted_id)
    
        music_list_len = len(music_list)
        remain = chapter_len
        for m in music_list:
            remain -= X[m-1]
            print(m, end=" ") # 印出該單元的音樂播放清單
        print(remain) # 印出該單元剩餘時間
第四題

剛成為大一新鮮人的王小明要開始選課了，他想把課程全部排在三天內，其他時間去打工與參加社團。因此他先列出三天內可以選的課程清單，決定使用以下規則輕鬆選課：                                         

  1. 從第一天開始挑選，挑選完後，再挑選下一天的課程。
  2. 依照當天課程之下課節次排序，先挑選最早下課者（如有相同下課時間的課程，則選擇英文字母排序較前者， 例如：A為2-3節，B為1-3節，會選擇A）。
  3. 每日盡可能把課程排滿。
  4. 課程時間不可重疊。
  5. 同一天不會有重複的課程名稱，且相同課程在三天內只能挑選一次。

例如王小明挑選的三天課表為下表：

第一天選的課程是A、C (B的時間與A重疊、D的時間與C 重疊)
第二天選的課程是B、D(A選過了，E的時間與D 重疊)
第三天選的課程是F   (C選過了，E的時間與F 重疊)


輸入格式：
未排序的課程清單

  • N：共有幾筆資料輸入，其中N 為整數，3≤N ≤36
  • d1  c1  s1  e1：天(1-3) 課程名稱(A-L) 課程開始節次(1-7) 課程結束節次(2-8)
  • d2  c2  s2  e2：天(1-3) 課程名稱(A-L) 課程開始節次(1-7) 課程結束節次(2-8)
  • ...
  • dn  cn  sn  en：天(1-3) 課程名稱(A-L) 課程開始節次(1-7) 課程結束節次(2-8)

輸出格式：

  • d1  c1  s1  e1
  • d2  c2  s2  e2
  • ...
  • dn  cn  sn  en


需要完成及繳交的函式（擇一程式語言完成作答即可）：

static void SelectCourse(Course[] results, bool[] selected, Course[] candidates, int cs)函式

  • results選課結果。
  • selected紀錄課程是否被選過，未選過則紀錄false，已選過則紀錄true。
  • candidates每日可選課程。
  • cs每日可選課程（candidates）數量
  • 此函式計算並回傳每日的選課清單。

static void SelectCourse(Course[] results, bool[] selected, Course[] candidates, int cs) {
    // 請完成並繳交本函式
}

void SelectCourse(Course results[], int *rs, bool selected[], Course candidates[], int cs)函式

  • results選課結果。
  • rs選課結果（results）數量。
  • selected紀錄課程是否被選過，未選過則紀錄false，已選過則紀錄true。
  • candidates每日可選課程。
  • cs每日可選課程（candidates）數量
  • 此函式計算並更新選課結果(results)，同時更新rs及selected。

void SelectCourse(Course results[], int *rs, bool selected[], Course candidates[], int cs) {
    // 請完成並繳交本函式
}

static void SelectCourse(Course results[], boolean selected[], Course candidates[], int cs)函式

  • results選課結果。
  • selected紀錄課程是否被選過，未選過則紀錄false，已選過則紀錄true。
  • candidates每日可選課程。
  • cs每日可選課程（candidates）數量
  • 此函式計算並更新選課結果(results)，同時更新rs及selected。

static void SelectCourse(Course results[], boolean selected[], Course candidates[], int cs) {
    // 請完成並繳交本函式
}

def selectCourse(candidates, selected):函式

  • candidates為每天可選之課程。
  • selected為已經選擇的課程。
  • 此函式計算並回傳每日的選課清單。

def selectCourse(candidates, selected):
    # 請完成並繳交本函式


測資

範例測資：
測資1
輸入
11
2 D 5 7
3 C 2 3
1 C 5 6
2 E 7 8
1 B 2 4
2 A 5 6
3 E 5 7
1 D 6 8
1 A 1 2
3 F 5 6
2 B 1 4
輸出
1 A 1 2  
1 C 5 6  
2 B 1 4  
2 D 5 7  
3 F 5 6  

測資2
輸入
10
1 A 1 3
1 B 3 6
1 C 5 7
2 A 2 4
2 B 5 7
2 E 3 5
3 B 6 8
3 D 3 5
3 C 4 6
3 F 5 7
輸出
1 A 1 3
1 C 5 7
2 E 3 5
3 D 3 5
3 B 6 8

測資3
輸入
12
1 A 1 3
2 B 2 5
3 C 3 5
1 B 4 6
2 E 5 8
3 F 3 5
2 C 1 3
2 D 4 6
2 F 3 5
1 C 5 8
2 G 7 8
3 D 6 8
輸出
1 A 1 3
1 B 4 6
2 C 1 3
2 D 4 6
2 G 7 8
3 F 3 5

測資4
輸入
9
1 A 1 3
2 B 3 4
3 C 4 6
2 C 5 7
2 D 6 8
3 F 4 6
1 B 6 8
2 F 3 5
3 E 1 3
輸出
1 A 1 3
1 B 6 8
2 F 3 5
2 D 6 8
3 E 1 3
3 C 4 6

測資5
輸入
8
1 D 1 3
1 E 4 6
2 A 1 3
2 B 2 4
3 B 5 7
3 E 4 6
1 C 3 5
2 C 6 8
輸出
1 D 1 3
1 E 4 6
2 A 1 3
2 C 6 8
3 B 5 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using System;
using System.Collections.Generic;
using System.Text;

namespace csharp
{
    public static class Global
    { // 全域變數
        public static int rs = 0; // 紀錄選課數量（results）
    }
    class Q4
    {
        public struct Course
        { // 課程
            public int day;
            public char name;
            public int start;
            public int end;
        }
        static void SelectCourse(Course[] results, bool[] selected, Course[] candidates, int cs)
        {
            // 你的程式碼
        }

        static void Main()
        {
            Course[] allcourse = new Course[36]; // 所有課程
            Course[] results = new Course[36]; // 選課結果
            int n = Convert.ToInt32(Console.ReadLine());  // 所有課程數量

            bool[] selected = new bool[36]; // 紀錄已選過的課
            for (int i = 0; i < 36; i += 1)
            {
                selected[i] = false;
            }

            for (int i = 0; i < n; i += 1)
            { // 輸入課程
                string[] input = Console.ReadLine().Split(' ');
                allcourse[i].day = Convert.ToInt32(input[0]);
                allcourse[i].name = Convert.ToChar(input[1]);
                allcourse[i].start = Convert.ToInt32(input[2]);
                allcourse[i].end = Convert.ToInt32(input[3]);
            }

            for (int days = 1; days <= 3; days += 1)
            {
                Course[] candidates = new Course[12];
                int cs = 0; // 紀錄candidates有多少
                for (int i = 0; i < n; i += 1)
                {
                    if (allcourse[i].day == days)
                    {
                        candidates[cs] = allcourse[i];
                        cs += 1;
                    }
                }
                SelectCourse(results, selected, candidates, cs);
            }
            for (int i = 0; i < Global.rs; i += 1)
            {
                Console.WriteLine("{0} {1} {2} {3}", results[i].day, results[i].name, results[i].start, results[i].end);
            }

        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def selectCourse(candidates, selected):

# 你的程式碼

if __name__ == '__main__':
    n = int(input()) # 所有課程數量

    allcourse = [] # 所有的課程
    candidates = []
    selected = []

    for i in range(n): # 輸入課程資料 將輸入的課程資料全部加在allcourse
        courses = input()
        dataSplit = courses.split(' ')
        allcourse.append([int(dataSplit[0]),dataSplit[1],int(dataSplit[2]),int(dataSplit[3])])

    for i in range(3): # 有三天 所以for 跑三次
        for j in range(n):
            if(allcourse[j][0] == i+1):
                candidates.append(allcourse[j])
        result = selectCourse(candidates, selected)
        candidates = []
        for x in result:
            selected.append(x[1]) # 把選好的課 加入到selected裡
            for z in x: #印出答案
                print( str(z), end = ' ')
            print("")
第五題

佇列(Queue)具備先進先出(first in first out, FIFO)的特性，廣泛的使用於需要排隊機制的應用中。請完成環形佇列函式circular_queue ( )來輔助進行廣度優先搜尋的功能。

本題主程式將透過廣度優先搜尋(Breadth First Search, BFS)法，從下圖中某一節點開始搜尋，搜尋過程中每一節點會依序透過 circular_queue( )函式放入佇列或自佇列中取出。

輸入格式：

  • P：廣度優先搜尋的起點節點 (0-9)

輸出格式：

  • p1 p2 … p9：廣度優先搜尋依序輸出節點

例如

若從節點4開始搜尋，環狀佇列的變化如下所示：

[0] [1] [2] [3] [4] [5]
 4                   
     1   3   5   6   
 2       3   5   6   0
 2           5   6   0
 2   7           6   0
 2   7   8           0
 2   7   8           
     7   8           
         8   9       
             9

輸出

4 1 3 5 6 0 2 7 8 9


需要完成及繳交的函式（擇一程式語言完成作答即可）：

public static void circular_queue(char c, int y)函式

  • 其中參數字元c控制此函數執行新增或刪除動作。
  • 當新增資料時，整數x為新增的資料內容；當刪除資料時，整數x為傳回的刪除資料項。

public static void circular_queue(char c, int y) {
        // 請完成並繳交本函式
}

void circular_queue (char c, int* x )函式

  • 其中參數字元c控制此函數執行新增或刪除動作。
  • 當新增資料時，整數x為新增的資料內容；當刪除資料時，整數x為傳回的刪除資料項。

void circular_queue (char c, int* x ){
        // 請完成並繳交本函式
}

public static void circular_queue(char c, int y)函式

  • 其中參數字元c控制此函數執行新增或刪除動作。
  • 當新增資料時，整數x為新增的資料內容；當刪除資料時，整數x為傳回的刪除資料項。

public static void circular_queue(char c, int y) {
        // 你的程式碼
}


測資

範例測資：
測資1
輸入
1
輸出
1
0
2
4
3
8
5
6
9
7

測資2
輸入
3
輸出
3
0
4
5
1
6
7
2
8
9

測資3
輸入
5
輸出
5
3
4
6
7
0
1
8
9
2

測資4
輸入
7
輸出
7
5
6
9
3
4
8
0
1
2

測資5
輸入
9
輸出
9
7
8
5
6
2
3
4
1
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using System;

namespace csharp
{
    class Program
    {
        public static int N = 10;
        public static int x = 0;
        public static int rear, front;
        public static int[] queue = new int[N];
        public static int[] visited = new int[N];

        static void Main(string[] args)
        {
            int[,] src = new int[,]{
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
            {1, 0, 1, 0, 1, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
            {1, 0, 0, 0, 1, 1, 0, 0, 0, 0},
            {0, 1, 0, 1, 0, 1, 1, 0, 0, 0},
            {0, 0, 0, 1, 1, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 1, 1, 0, 1, 1, 0},
            {0, 0, 0, 0, 0, 1, 1, 0, 0, 1},
            {0, 0, 1, 0, 0, 0, 1, 0, 0, 1},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 0}};
            //Console.WriteLine("請輸入廣度優先走訪的起點位置: ");
            int p = Convert.ToInt16(Console.ReadLine());
            // for (int i = 0 ; i < N ; i++){
            //     visited[i] = 0;
            //     queue[i]=0;
            // } 
            BFS(src, p);

        }
        public static void circular_queue(char c, int y)
        {

            //你的程式碼
        }
        public static void BFS(int[,] src, int p)
        {

            //Console.WriteLine("走訪節點: "+p+"\n");
            Console.WriteLine(p);
            visited[p] = 1;

            for (int i = 0; i < N; i++)
                if (src[p, i] == 1)
                    if (visited[i] != 1)
                    {
                        circular_queue('i', i);

                    }



            while (front != rear)
            {
                circular_queue('d', x);
                if (visited[x] != 1)
                    BFS(src, x);
            }

        }
    }
}