---
# System prepended metadata

title: Python

---

# Python
## Pandas & Matplotlib
讀取'臺北市勞動力及就業按半年.csv'，篩選部分資料並倒置資料，然後用matplotlib劃出圓柱圖。

![](https://i.imgur.com/0JFcvu1.png)

```python=
import os
import pandas as pd
import matplotlib.pyplot as plt
import csv

data = pd.read_csv("臺北市勞動力及就業按半年.csv")
#了解csv檔長甚麼樣子
# print(data.columns)
# print(data['半年[季/月]平均別'][98], data['勞動力人口/就業者[千人]'][98], data['就業結構/農業人數[千人]'][98], data['就業結構/工業人數[千人]'][98]
# , data['就業結構/服務業人數[千人]'][98], data['就業者教育程度/大專以上人數[千人]'][98]
# , data['就業者教育程度/高中職人數[千人]'][98], data['就業者教育程度/國中以下人數[千人]'][98], sep="  ")

numbers = data['勞動力人口/就業者[千人]']; agricultrue = data['就業結構/農業人數[千人]']
industry = data['就業結構/工業人數[千人]']; service = data['就業結構/服務業人數[千人]']
college = data['就業者教育程度/大專以上人數[千人]']; highs = data['就業者教育程度/高中職人數[千人]']
jhighs = data['就業者教育程度/國中以下人數[千人]']

#擷取部分資料並把資料轉置
newData = pd.DataFrame({
    "標題":[ "Total\npopulation","Agriculture\npopulation","Industry\npopulation","Service\npopulation"
    ,"Education:\nAbove College","Education:\nHigh school","Education:\nUunder\njunior high school" ],
    "JUN94":[ int(numbers[70]) * 1000, int(agricultrue[70]) * 1000, int(industry[70]) * 1000,
             int(service[70]) * 1000, int(college[70]) * 1000, int(highs[70]) * 1000, int(jhighs[70]) * 1000 ],
    "JUN109":[ int(numbers[98]) * 1000, int(agricultrue[98]) * 1000, int(industry[98]) * 1000,
             int(service[98]) * 1000, int(college[98]) * 1000, int(highs[98]) * 1000, int(jhighs[98]) * 1000 ]
})

#寫進新的CSV檔
if os.path.exists("D:/元智資工/python練習/94JUN_109JUN.csv"):
    pass
else:
    with open("D:/元智資工/python練習/94JUN_109JUN.csv", 'w', newline='', encoding='utf-8') as file_in:
        newData.to_csv("94JUN_109JUN.csv", index=False)#to_csv 會重複寫入index 所以 index=False
_94_109 = pd.read_csv("94JUN_109JUN.csv")
print(_94_109)

condition=_94_109["標題"].str.contains("population") #篩選出就業人口
populations = _94_109[condition]
largestTwo=populations["JUN94"].nlargest(2) #第一大是Total第二大才是某職業人口
excepTotal=largestTwo.nsmallest(1) #篩出第二大的也就是最大的職業人口
mostpop94 = "Most popular career in JUN94:" + _94_109.iloc[excepTotal.index]["標題"].to_string(index=False)
mostpop94 = str(mostpop94).replace("npopulation", "").replace('\\','')
largestTwo=populations["JUN109"].nlargest(2) #
excepTotal=largestTwo.nsmallest(1) #
mostpop109 = "Most popular career in JUN109:" + _94_109.iloc[excepTotal.index]["標題"].to_string(index=False)
mostpop109 = str(mostpop109).replace("npopulation", "").replace('\\', '')

# 用ANSI編碼方式存另一個CSV檔,才能用Excel閱讀且沒有亂碼
# with open("D:/元智資工/python練習/ttttt.csv", 'w', newline='', encoding='ANSI'):
#     newData.to_csv("ttttt.csv", encoding='ANSI', index=False)

plt.rcParams["figure.figsize"] = (13, 10) #設定show圖片時預設的圖片大小
x_pos = [0,2.5,5,7.5,10,12.5,15] #X軸的位置
bar1 = plt.bar(x_pos, _94_109["JUN94"], label ='94_JUN' ,align ="edge", width = -1)#負數代表往左寬0.35
bar2 = plt.bar(x_pos, _94_109["JUN109"], label ='109_JUN' ,align ="edge", width = 1)
plt.xticks(x_pos, _94_109["標題"])
plt.legend(loc=1)

for rect in bar1: #添加百分比跟實際數字
    height = rect.get_height()
    plt.text(rect.get_x() + rect.get_width()/2.0-0.3, height/2.0, '{:.1%}'.format(height/bar1[0].get_height()), fontsize = 9)
    plt.text(rect.get_x() + rect.get_width()/2.0-0.5, height+20000, height, fontsize = 10)

for rect in bar2: #添加百分比跟實際數字
    height = rect.get_height()
    plt.text(rect.get_x() + rect.get_width()/2.0-0.3, height/2.0, '{:.1%}'.format(height/bar2[0].get_height()), fontsize = 9)
    plt.text(rect.get_x() + rect.get_width()/2.0-0.5, height+20000, height, fontsize = 10)

plt.text(3.5, 1180000, mostpop94+"\n"+mostpop109,fontsize=15) #輸出最多人從事行業
plt.title("Career Structure", fontsize=18) #標題
plt.ylabel("Population(million)", fontsize=15) #Y軸標題
plt.xlabel("Career", fontsize=15) #X軸標題
plt.savefig("D:/元智資工/python練習/ThePic.png") #儲存圖片
plt.show() #顯示圖片
```
## Selenium模擬登入
```python=
from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import Select
from selenium.common.exceptions import NoSuchElementException
import time
import bs4
import requests
import os
import re
driver = webdriver.Chrome()
driver.get('https://kater.me/') #開啟網頁
time.sleep(3) #等待網站載入以免進入登入表單得按鈕還沒讀取出來

#找到進入登入表單的按鈕
log=driver.find_element_by_xpath("/html/body/div[1]/div[2]/header/div[2]/div[2]/ul/li[3]/button")
log.click() #點擊進入登入表單的按鈕
time.sleep(1)

username = driver.find_element_by_name("identification") #找到input username的欄位
password = driver.find_element_by_name("password") #找到input password的欄位
username.send_keys("Your username") #輸入username
password.send_keys("Your password") #輸入password
time.sleep(2)

#找登入按鈕,由於登入按鈕的Xpath會變動,導致find_element會出現NoSuchElementException錯誤,所以用try-except排除錯誤訊息
#如果Xpath不是上者則是下者
try:
    login = driver.find_element_by_xpath("/html/body/div[2]/div/div/div/form/div[3]/div[2]/div[4]/button")
except NoSuchElementException:
    login=driver.find_element_by_xpath("/html/body/div[3]/div/div/div/form/div[3]/div[2]/div[4]/button")

login.click() #點擊登入按鈕
time.sleep(3) #等待網站載入

adult = driver.find_element_by_xpath("/html/body/div[1]/main/div[1]/div/div/div/nav/ul/li[2]/div/ul/li[12]/a")
adult.click() #點擊進入閒聊看版

driver.get("https://kater.me/t/chat") #開啟閒聊看版

root = bs4.BeautifulSoup(driver.page_source,"html.parser") #解析原始碼
titles = root.find_all(href=re.compile("https://kater.me/d/")) #藉由找到標題
print(titles)

#如果桌面沒有karterImg資料夾則創建一個
if not os.path.isdir("C:/Users/s1071441/Desktop/karterImg"):
    os.mkdir("C:/Users/s1071441/Desktop/karterImg")

num = 1
for x in titles:
    driver.get(x["href"]) #進入標題文章
    sonpage = bs4.BeautifulSoup(driver.page_source, "html.parser") #解析文章網頁原始碼
    imgTag = sonpage.find_all("img") #找圖片
    
    for y in imgTag:
        imgUrl = requests.get(y["src"]) #獲取圖片來源網址
        img = imgUrl.content #獲取圖片內容
        check = True
        while check:
            if os.path.exists("C:/Users/s1071441/Desktop/karterImg/" +str(num)+ ".jpg"): #檢查是否有重複檔名
                num += 1
            else:
                 check = False
        #用二元檔寫入圖片進資料夾
        with open("C:/Users/s1071441/Desktop/karterImg/" +str(num)+ ".jpg",'wb') as pic_out:
            pic_out.write(img)
            print(num)
            time.sleep(1.5)
            
    time.sleep(1.5)
```

## Web Crawl
```python=
import os
import time
import requests
import urllib.request as req
import bs4

def geturl(url, duplication,num): #每一頁都執行這個函式
    #建立Request物件
    request = req.Request(url, headers={"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/85.0.4183.121 Safari/537.36"
    })
    with req.urlopen(request) as response:
        data = response.read().decode("utf-8")
    root = bs4.BeautifulSoup(data, "html.parser") #解析網頁原始碼

    #如果桌面沒有karterImg資料夾則創建一個
    if not os.path.isdir("C:/Users/s1071441/Desktop/BahaImg"):
        os.mkdir("C:/Users/s1071441/Desktop/BahaImg")

    titles = root.find_all("p", class_ = "b-list__main__title") #找到所有標題
    for title in titles:
        if "貓" in title.string: #找標題文字中有貓的標題
             #因為巴哈每一頁都會標題有一些跟上一頁重複,所以宣告一個list放爬過的標題,重複的話就跳過該次迴圈
            if duplication.__contains__(title.string):
                continue
            else:
                duplication.append(title.string)
            print(title.string)

            sontitle = req.Request("https://forum.gamer.com.tw/" + title["href"],headers={"User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/85.0.4183.121 Safari/537.36"
            })
            with req.urlopen(sontitle) as titlepage:
                titleurl = titlepage.read().decode("utf-8")
            titledata = bs4.BeautifulSoup(titleurl, "html.parser")

            imgurls = titledata.find_all("a" , class_ ="photoswipe-image") #找到圖片

            for imgurl in imgurls:
                pic = requests.get(imgurl["href"]) #獲取圖片來源網址
                imgg = pic.content #獲得圖片內容
                check = True
                while check:
                    if os.path.exists("C:/Users/s1071441/Desktop/BahaImg/" +str(num)+ ".jpg"): #檢查是否有檔名重複
                        num += 1
                    else:
                        check = False
                #用二元檔寫入圖片
                with open("C:/Users/s1071441/Desktop/BahaImg/" +str(num)+ ".jpg",'wb') as pic_out:
                    pic_out.write(imgg)
                    print(num)
                    time.sleep(0.5)
                    
    nextLink = root.find("a", class_ = "next") #找到下一頁的網址
    return nextLink["href"] #回傳下一頁的網址

numbers = 1
dupl = []
url = "https://forum.gamer.com.tw/B.php?bsn=60076"
count = 0
while count < 200:
    url = "https://forum.gamer.com.tw/B.php" + geturl(url,dupl,numbers) #執行geturl並串接出下一頁的網址
    time.sleep(0.3)
    count += 1
```
## Kruskal
```python=
vertexNum = int(input('Please input numbers of vertex:')) #輸入vertex的數量
edgeNum = int(input('Please input numbers of edges:')) #輸入edge的數量
edges = [] #全部的edge
nodes = set() #全部的node
subset={} #subset放每個node所屬set的root 跟 node所屬set的元素數量

#輸入每條edge([node1, node2, weight])ex:[1, 2 ,5]
for x in range(edgeNum):
    edges.append([])
print('Please input edges:')
for i in range(edgeNum):
    edge=[]
    for j in range(2):
        edge.append(int(input('Node' + str(j+1) + ' of NO. ' + str(i+1) +'edge:')))
    edge.append(int(input('Weight of NO. ' + str(i+1) + 'edge:')))
    nodes.add(edge[0]) #node放進nodes裡
    nodes.add(edge[1])
    edges[i] = edge
    del edge
    print('\n')
#
#用weight排序 小的排後面以方便pop
edges = sorted(edges, key=lambda element: element[2], reverse=True)

#subset放每個node所屬set的root 跟 node所屬set的元素數量
for x in nodes:
    subset[str(x)] = [x,1]

def Kruskal(nodes, edges):
    nodes = nodes
    edges = edges
    usedNode = set()
    MST = []

    while usedNode != nodes: #直到每個node都走過才脫離迴圈
        current = edges.pop()
        if findRoot(current[0]) == findRoot(current[1]): #如果n1 跟 n2的root相同會形成cycle
            del current
            continue
        else: #如果n1 跟 n2的root不同
            union(current[0], current[1])
            MST.append(current) #將edge加入MST
            usedNode.update(current[:2]) #更新usedNode
            del current
            
    return MST
#將兩個 node 所屬的 set 合成一個
def union(n1,n2):
    n1 = n1
    n2 = n2
    if subset[str(findRoot(n1))][1] >= subset[str(findRoot(n2))][1]: #n1 的 root 的set 的node數量大於n2的
        subset[str(findRoot(n2))][0] = findRoot(n1) #n2 所屬set 的 root 放入 n1 的 root(變成屬於n1的set)
        subset[str( findRoot(n1) ) ][1] += 1 # n1 所屬 set 的 node數量+1
    else:
        subset[str(findRoot(n1))][0] = findRoot(n2) #同上 n1 n2對調
        subset[str( findRoot(n2) ) ][1] += 1
        
#找到該node所屬set的root
def findRoot(node):
    node = node
    if subset[str(node)][0] != node: #自己的root不是自己的話 遞迴
        return findRoot(subset[str(node)][0])
    else:
        return node #root是自己

mmst = Kruskal(nodes,edges)
print(mmst) #輸出最短路徑
```
# LINUX(Ubuntu)
## Multi-processs shared memory練習
利用 fork() 來使得一個程式得以建構多個子行程(child process)，每個子行程會賦予一個隨機的次序（０～１２）。所有子行程將透過共用記憶體的內容來進行同步，由次序為０的人開始印出字母，並透過改變共同記憶體的內容來讓其他子程序依序接著印出"Hello world!"的每個字。

```C++=
#include<sys/types.h>
#include<iostream>
#include<unistd.h>
#include<sys/wait.h>
#include<vector>
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>   
#include <algorithm>
#include<sys/shm.h>
using namespace std;

int main(void)
{	
	int key = 777;  //第一個shared memory的key
	int key2 = 666;  //第二個shared memory的key
	int shm_id;  //第一個shared memory的id
	int shm_id2;  //第二個shared memory的id

	shm_id = shmget(key, sizeof(char) * 13, 0666 | IPC_CREAT);  //建立第一個shared memory
	shm_id2 = shmget(key2, sizeof(int), 0666 | IPC_CREAT);  //建立第二個shared memory

 	if (shm_id == -1) //第一個shared memory 建立失敗
	{
        cout << "getting shared memory failed ";
        return 1;
   	}

	if (shm_id2 == -1) //第二個shared memory 建立失敗
	{
        cout << "getting shared memory failed ";
        return 1;
   	}

	int sign;  //號碼牌
	pid_t pid;

	//父程序先寫Hello world進shared memory
	//連接process跟shared memory
	void* mem; //shared memory的記憶體位置
	mem = shmat(shm_id, (const void *)0, 0);
	char *p = (char *)mem;
	void* mem2;
	mem2 = shmat(shm_id2, (const void *)0, 0);
	int *current = (int *)mem2;//之後critical section防止race condition用 

	*p = 'H';
	*(p + 1) = 'e';
	*(p + 2) = 'l';
	*(p + 3) = 'l';
	*(p + 4) = 'o';
	*(p + 5) = ' ';
	*(p + 6) = 'w';		//寫"Hello world!"進shared memory
	*(p + 7) = 'o';
	*(p + 8) = 'r';
	*(p + 9) = 'l';
	*(p + 10) = 'd';
	*(p + 11) = '!';
	*(p + 12) = '\0';
	*current = 0;
	//之後critical section防止race condition用
	//sign跟current一樣才能脫離迴圈進critical section

	srand(time(0));
	vector<int> order = { 0,1,2,3,4,5,6,7,8,9,10,11,12 };//籤筒
	int pos;  //放抽到的order的位置
	int x;  //放order[pos]
	int rest = 13;  //剩下的號碼排數量

for(int i = 0; i < 13; i++)  //生成13個children
{//隨機抽取號碼牌
	pos = rand() % rest;  //抽一個order的index
	x = order[pos];  //放order[pos]進x
	remove(order.begin(), order.end(), x);  //刪除被抽到的位置的數,避免重複
	order.resize(order.size() - 1);  //order的size = size - 1
	rest--; //剩下的號碼牌數量減一
	pid = fork();
	sign = x;  //給予抽到的籤
	if(pid == 0 || pid == -1) //是子程序或錯誤的話跳出迴圈，確保只有父程序生child
	{
		break;
	}
}

if(pid < 0)  //fork失敗
{
	cerr << "Fork failed";
	return 1;
}

if(pid > 0)  //parent
{
//等待所有子程序結束
	while (pid = waitpid(-1, NULL, 0)) 
	{
  	 if (errno == ECHILD) 
		{
     		 break;
   		}
	}
}
else if(pid == 0)  //child
{	
	//連接process跟shared memory
	void* mem;
	mem = shmat(shm_id, (const void *)0, 0);
	char* p = (char *)mem;
	//連接process跟shared memory
	void* mem2;
	mem2 = shmat(shm_id2, (const void *)0, 0);
	int* current = (int *)mem2;
	while(sign != *current){} //sign跟current一樣才能脫離迴圈進critical section

	//critical section start
	char word = (p+sign);  //放要輸出的字進word,因為sign每+1,去掉第一個字
	usleep(5000);
	*current = *current + 1;
	//current = current + 1;//使下一個能脫離while的thread,是號碼為自己加一的thread
	cout << word;//輸出word
	//critical section end
}
return 0;
}
```

## Multi-process Multi-thread練習
改用 Multi-thread 實作上者的功能

```C++=
#include<sys/types.h>
#include<iostream>
#include<unistd.h>
#include<sys/wait.h>
#include<vector>
#include <stdio.h>
#include <stdlib.h> 
#include <time.h>   
#include <algorithm>
#include<sys/shm.h>
#include<cstdlib>
#include<sys/file.h>
#include<sys/mman.h>
#include<pthread.h>
using namespace std;

//用全域變數當shared memory
char msg[13] = "Hello world!";
int current = 0;  //防止race condition用
//第一個進critical section的thread的號碼是0,所以預設0
void *outputByOrder(void *ptr);

int main(void)
{	
	int sign[13];  //號碼牌
	pthread_t t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13;
	srand(time(0));
	vector<int> order = { 0,1,2,3,4,5,6,7,8,9,10,11,12 };//籤筒
	int pos;  //放抽到的order的位置
	int x;  //放order[pos]
	int rest = 13;  //剩下的號碼排數量
for(int i = 0; i < 13; i++)  //抽籤
{
	pos = rand() % rest;  //抽一個order的index
	x = order[pos];  //放order[pos]進x
	remove(order.begin(), order.end(), x);  //刪除被抽到的位置的數,避免重複
	order.resize(order.size() - 1);  //order的size = size - 1
	rest--; //剩下的號碼牌數量減一
	sign[i] = x;  //給予抽到的籤
}
//創建13個thread,並把號碼牌傳進去
//sign[i]是隨機的，所以thread的號碼並不會照順序，會隨機
 pthread_create (&t1, NULL,outputByOrder, (void *) &sign[0]);
 pthread_create (&t2, NULL,outputByOrder, (void *) &sign[1]);
 pthread_create (&t3, NULL,outputByOrder, (void *) &sign[2]);
 pthread_create (&t4, NULL,outputByOrder, (void *) &sign[3]);
 pthread_create (&t5, NULL,outputByOrder, (void *) &sign[4]);
 pthread_create (&t6, NULL,outputByOrder, (void *) &sign[5]);
 pthread_create (&t7, NULL,outputByOrder, (void *) &sign[6]);
 pthread_create (&t8, NULL,outputByOrder, (void *) &sign[7]);
 pthread_create (&t9, NULL,outputByOrder, (void *) &sign[8]);
 pthread_create (&t10, NULL,outputByOrder, (void *) &sign[9]);
 pthread_create (&t11, NULL,outputByOrder, (void *) &sign[10]);
 pthread_create (&t12, NULL,outputByOrder, (void *) &sign[11]);
 pthread_create (&t13, NULL,outputByOrder, (void *) &sign[12]);
//等待thread結束
 pthread_join(t1, NULL);
 pthread_join(t2, NULL);
 pthread_join(t3, NULL);
 pthread_join(t4, NULL);
 pthread_join(t5, NULL);
 pthread_join(t6, NULL);
 pthread_join(t7, NULL);
 pthread_join(t8, NULL);
 pthread_join(t9, NULL);
 pthread_join(t10, NULL);
 pthread_join(t11, NULL);
 pthread_join(t12, NULL); 
 pthread_join(t13, NULL);
}

void *outputByOrder(void *ptr)
{
	int *data; //取資料(sign[i])用
	data = (int *)ptr; //取資料
	while(*data != current){} //data跟current一樣才能脫離迴圈進critical section
	//critical section
	cout << msg[*data];//msg裡第data(該thread的號碼)個位置的字,正好是該thread要輸出的字
	current = current + 1;//使下一個能脫離while的thread,是號碼為自己加一的thread
	//critical section
}
```

## Multi-processs pipe練習
用 fork()來使得一個程式得以建構多個子行程(child process)，
並且兩者之間透過由父行程透過 pipe() 發送訊息給第一個子行程、
接著第一個子行程發送訊息給第二個子行程的方式，
每一個收到訊息的子行程將印出一個字母並繼續傳遞訊息給下一個子行程。
```C++=
#include<sys/types.h>
#include<iostream>
#include<cstring>
#include<unistd.h>
#include<sys/wait.h>
#define READ_END 0  //read端
#define WRITE_END 1 //write端
using namespace std;

int main(void)
{
    int BUFFER_SIZE = 13;
    char write_msg[BUFFER_SIZE] = "Hello world!";
    char read_msg[BUFFER_SIZE];
    int fd[2]; //pipe的兩端
    pid_t pid;
    if(pipe(fd) == -1)  //pipe失敗
    {
    	cerr << "Pipe failed";
    	return 1;
    }

    for(int i = 0; i < 13; i++)  //生成13個children
    {
        pid = fork();
        if(pid == 0 || pid == -1) //是子程序或錯誤的話跳出迴圈，確保只有父程序生child
        {
            break;
        }
    }

	if(pid < 0)  //fork失敗
	{
	    cerr << "Fork failed";
	    return 1;
	}

	if(pid > 0)  //parent
        {
	    close(fd[READ_END]);  //關閉read端
	    write(fd[WRITE_END], write_msg, strlen(write_msg)+1);//用write_end寫write_msg
	    close(fd[WRITE_END]);  //關閉write端
	    waitpid(pid, NULL, 0);  //等待所有子程序結束
	}

	else if(pid == 0)	//child
	{
	    read(fd[READ_END], read_msg, BUFFER_SIZE); //用read_end把文字讀出

		cout << read_msg[0];  //輸出第一個字
		for(int i = 0; i < BUFFER_SIZE; i++)	//去掉第一個字
		{
                       //藉由把每個字往前一個位置再放進write_msg去掉第一個字
			write_msg[i] = read_msg[i + 1];
		}		
		BUFFER_SIZE--;
		write(fd[WRITE_END], write_msg,BUFFER_SIZE);
	}
    return 0;
}
```

# C++

## Branch Prediction
實作預測器(predictor)
```C++=
#include<iostream>
#include<vector>
#include<string>
#include<istream>
#include<sstream>
#include<map>
using namespace std;

//輸入只會有add ,addi ,beq
string twoBC_intToString_onlyNT(int bc)
{
	string N = "N"; string T = "T";
	if (bc == 0)
		return N;
	else if (bc == 1)
		return N;
	else if (bc == 2)
		return T;
	else if (bc == 3)
		return T;
}

string history_intToString(int hi)
{
	string nn = "00"; string nt = "01"; string tn = "10"; string tt = "11";
	if (hi == 0)
		return nn;
	else if (hi == 1)
		return nt;
	else if (hi == 2)
		return tn;
	else if (hi == 3)
		return tt;
}

string twoBC_intToString(int bc)
{
	string SN = "SN"; string WN = "WN"; string WT = "WT"; string ST = "ST";
	if (bc == 0)
		return SN;
	else if (bc == 1)
		return WN;
	else if (bc == 2)
		return WT;
	else if (bc == 3)
		return ST;
}

class entry
{
public:
	void set_history(string onep, string twop)
	{
		if (onep == "N" && twop == "N")
			history = 0;
		else if (onep == "T" && twop == "N")
			history = 1;
		else if (onep == "N" && twop == "T")
			history = 2;
		else if (onep == "T" && twop == "T")
			history = 3;
	}
	void show_update(int whichEntry, string temp)
	{
		cout << "entry: " << whichEntry << "                " << "beq " << temp << endl;  //entry: 2      beq R1,R2,End
		// (00, SN, SN, SN, SN) N N 
		cout << "(" << history_intToString(history) << ", " << twoBC_intToString(twoBC[0]) << ", " 	
			<< twoBC_intToString(twoBC[1]) << ", " << twoBC_intToString(twoBC[2]) << ", " << twoBC_intToString(twoBC[3]) << ")  ";
		cout << twoBC_intToString_onlyNT(twoBC[history]) << " " << current_actually;

		if (twoBC_intToString_onlyNT(twoBC[history]) != current_actually)  // N  T
			miscount++;

		cout << "              misprediction: " << miscount << endl << endl;

		if (twoBC[history] > 0 && current_actually == "N")      //更新twoBC
			twoBC[history]--;
		else if(twoBC[history] < 3 && current_actually == "T")
			twoBC[history]++;

	}
	int history = 0; // 0看第1個2BC, 1看第2個......
	int twoBC[4] = { 0, 0, 0, 0 }; //預設全部SN    //0 = SN, 1 = WN, 2 = WT, 3 = ST
	string current_actually = "N";  //放該次預測 的 指令 的 實際值
	string one_pre = "N";    //上一次預測時的實際值
	string two_pre = "N";    //上二次預測時的實際值
	int miscount = 0;
};

void upToLow(string& s)   //全部換成小寫好比較
{
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] >= 'A' && s[i] <= 'Z')
			s[i] += 32;
	}
}

void addFunc(int &rd, int rs1, int rs2)
{
	rd = rs1 + rs2;
}

void addiFunc(int &rd, int rs, int immd)
{
	rd = rs + immd;
}

int main()
{
	int x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 = 0, x9 = 0, x10 = 0, x11 = 0, x12 = 0, x13 = 0, x14 = 0, x15 = 0 //全部的register
		, x16 = 0, x17 = 0, x18 = 0, x19 = 0, x20 = 0, x21 = 0, x22 = 0, x23 = 0, x24 = 0, x25 = 0, x26 = 0, x27 = 0, x28 = 0, x29 = 0, x30 = 0, x31 = 0, x32 = 0;
	map<string, int> m1;
	m1["1"] = x1; m1["2"] = x2; m1["3"] = x3; m1["4"] = x4; m1["5"] = x5; m1["6"] = x6; m1["7"] = x7; m1["8"] = x8; m1["9"] = x9; m1["10"] = x10; m1["11"] = x11;  //string "1" == int x1......
	m1["12"] = x12; m1["13"] = x13; m1["14"] = x14; m1["15"] = x15; m1["16"] = x16; m1["17"] = x17; m1["18"] = x18; m1["19"] = x19; m1["20"] = x20; m1["21"] = x21;
	m1["22"] = x22; m1["23"] = x23; m1["24"] = x24; m1["25"] = x25; m1["26"] = x26; m1["27"] = x27; m1["28"] = x28; m1["29"] = x29; m1["30"] = x30; m1["31"] = x31; m1["32"] = x32;

	int entry_num = 0;
	cout << "輸入幾個BHT entry:" << endl;
	cin >> entry_num;
	entry* entries = new entry[entry_num];  //創建使用者輸入個數的entry

	string s;
	vector<string>ins(100);

	vector <string> all_ins;   //用來放所有的risc-v指令
	string line;               //輸入時使用
	stringstream ss1;          //轉型用 輸出遇空格會停
	string insType;            //用來判斷指令的類型

	cout << "輸入instructions:" << endl;
	int insNum = 0;  //指令的數量

	while (getline(cin, line))
	{
		all_ins.push_back(line);   //指令一行一行放進all_ins
		insNum++;
	}

	for (int i = 0; i < insNum; i++)  //逐行 instruction 判斷 類型並處理
	{
		insType = "";  //初始化insType

		ss1.str("");   //初始化stringstream
		ss1.clear();   //

		ss1 << all_ins[i];
		ss1 >> insType;
		upToLow(insType);

		if (insType != "beq" && insType != "addi"&& insType != "add") 
		{
			string t = "";
			ss1 >> t;
			if (t == "")    //如果label之後就沒東西了 表示該行只有label  Ex: L1:
			{
				continue;
			}
			else // label 跟 指令同一行的狀況   EX -> L1: addi x1,x2,8787
			{
				insType = t;
			}
		}
		if (insType == "add")  // add x1,x2,x3  //temp == x1,x2,x3
		{
			string temp = "";
			ss1 >> temp;  //temp == x1,x2,x3
			int io = 0;   //用來計  x1,x2,x3 "逗號"的位置

			string rd = "";
			string rs1 = "";
			string rs2 = "";

			stringstream trans;  //轉型用

			for (int i = 1; i < temp.size(); i++)   //  i 從 1 開始直接忽略一開始的"x" or "R"
			{
				if (temp[i] == ',')     //x1, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rd += temp[i];  // rd == 1
			}

			for (int i = io + 2; i < temp.size(); i++)  //  i 從 io + 2 開始直接忽略第二個的"x"or"R"
			{
				if (temp[i] == ',')     //x2, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rs1 += temp[i];  //rs1 == 2
			}

			for (int i = io + 2; i < temp.size(); i++) //  i 從 io + 2 開始直接忽略第二個的"x" or "R"
			{
				rs2 += temp[i];   //rs2 == 3
			}

			addFunc(m1[rd], m1[rs1], m1[rs2]);
		}
		else if (insType == "addi")   // addi x1,x2,8787
		{
			string temp = "";
			ss1 >> temp;  // temp == "x1,x2,8787"
			int io = 0;   //用來計  x1,x2,8787 "逗號"的位置

			string rd = "";
			string rs = "";
			string immd = "";
			int immdi = 0;
			stringstream trans;

			for (int i = 1; i < temp.size(); i++)   //  i 從 1 開始直接忽略一開始的 x
			{
				if (temp[i] == ',')     //x1, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rd += temp[i];  // rd == 1
			}

			for (int i = io + 2; i < temp.size(); i++)  //  i 從 io + 2 開始直接忽略第二個的 x
			{
				if (temp[i] == ',')     //x2, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rs += temp[i];  // rs == 2
			}

			for (int i = io + 1; i < temp.size(); i++)
			{
				immd += temp[i];
			}
			trans.clear();
			trans.str("");
			trans << immd;
			trans >> immdi;  // immdi = 8787

			addiFunc(m1[rd], m1[rs], immdi);
		}
		else if (insType == "beq")  //beq x1,x2,label
		{
			int whichEntry = i % entry_num;  //決定進哪個entry ，行數除 總entry數 的餘數 一定不超過 總entry數

			string temp = "";
			ss1 >> temp;  //temp == "x1,x2,label"
			int io = 0;   //用來計  x1,x2,label "逗號"的位置

			string rs1 = "";
			string rs2 = "";
			string label = "";

			stringstream trans;

			for (int i = 1; i < temp.size(); i++)   //  i 從 1 開始直接忽略一開始的 x
			{
				if (temp[i] == ',')     //x1, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rs1 += temp[i];  //rs1 == "1"
			}
			for (int i = io + 2; i < temp.size(); i++)  //  i 從 io + 2 開始直接忽略第二個的 x
			{
				if (temp[i] == ',')     //x2, 的"逗號"的位置
				{
					io = i;
					break;
				}
				rs2 += temp[i];  //rs2 == "2"
			}
			for (int i = io + 1; i < temp.size(); i++)
			{
				label += temp[i];  //label == "L1"
			}
			label += ":";  //加":"變 "L1:"
			
			//----------Predictor----------------------------------------------------------------------
			if (m1[rs1] == m1[rs2])  //更新current_actaully
			{
				entries[whichEntry].current_actually = "T";
			}
			else
			{
				entries[whichEntry].current_actually = "N";
			}

			entries[whichEntry].show_update(whichEntry, temp);  //顯示當前該entry的狀態，並更新entry的狀態，以便下次show_update

			entries[whichEntry].two_pre = entries[whichEntry].one_pre;    //更新歷史紀錄 上一次的紀錄變成上兩次的紀錄
			entries[whichEntry].one_pre = entries[whichEntry].current_actually;  //更新歷史紀錄 這次的紀錄變成上一次的紀錄
			entries[whichEntry].set_history(entries[whichEntry].one_pre, entries[whichEntry].two_pre); //更新history  把上兩次的實際值放進 history裡
		    //----------------------------------------------------------------------------------------------

			if (m1[rs1] == m1[rs2])
			{
				//--------------------找目標行數--------------
				string iflabel = "";
				for (int j = 0; j < insNum; j++)  //找出label的行數
				{
					stringstream ss2;
					ss2.clear();
					ss2.str("");

					ss2 << all_ins[j];
					ss2 >> iflabel;   //取出標籤
					if (iflabel == label)
					{                 // 這邊會改到 i !!
						i = j - 1;    //i = j - 1;  這樣的話 等等這個迴圈跑完 i 再++ 就會執行 i 那行 ，也就是目標行數
						break;
					}
				}
				//------------------------------------------------
			}

		}

	}
	system("pause");
	return 0;
}



```
---

## Tree 練習
Construct one binary tree by reading the results of the preorderand inorder traversal. 
**Example:**
Inorder: 3 7 8 6 11 2 5 4 9
Preorder:2 7 3 6 8 11 5 9 4

Output the tree by preorder:2  7  3  6  8  11  5  9  4
```C++=
#include <iostream>
#include <vector>
using namespace std;

struct  Node
{
	int data;
	Node* left;
	Node* right;
};

Node* newnode(int data)
{
	Node* temp = new Node;
	temp->data = data;
	temp->left = temp->right = nullptr;
	return temp;
}

vector<int> mark_Preorder_order_in_Inorder(vector<int>& inorder, vector<int>& preorder)   //把preorder在inorder出現的位置放進number
{
	vector<int> number;

	for (int i = 0; i < preorder.size(); i++)
	{
		for (int j = 0; j < inorder.size(); j++)
		{
			if (inorder[j] == preorder[i])    //發現inorder跟preorder一樣的值
			{
				number.push_back(j);   //把在inorder裡的位置放進numder
				continue;
			}
		}
	}
	return number;           //以範例題來看  number: 5 1 0 3 2 4 6 8 7
}

Node* buildtree(int start, int end, vector<int>& preorder, int& c, vector<int>& number)
{//遞迴，Preorder的第一個值是root，該值在Inorder的位置key，Inorder中在key左邊的是root的leftchild，反之為右子。而形成的子樹也一樣，所以遞迴呼叫
	if (start > end)   //返回條件，沒符合則繼續建node
		return nullptr;

	int key = 0;  //放Preorder在Inorder的位置key
	Node* root = newnode(preorder[c]);  //新子樹的root是preorder[c]，c從0開始
	key = number[c];
	c++;

	root->left = buildtree(start, key - 1, preorder, c, number);   //遞迴呼叫
	root->right = buildtree(key + 1, end, preorder, c, number);      //遞迴呼叫

	return root;
}

void Preorder(Node* current) //測試是否正確
{
	if (current)
	{
		cout << current->data << "  ";   // V
		Preorder(current->left);       // L
		Preorder(current->right);      // R
	}
}

int main()
{
	vector<int> inorder = { 3, 7, 8, 6, 11, 2, 5, 4,9 };
	vector<int> preorder = { 2, 7, 3, 6, 8, 11, 5, 9,4 };

	cout << "Inorder: ";
	for (int i = 0; i < inorder.size(); i++)
	{
		cout << inorder[i] << " ";
	}
	cout << endl;
	cout << "Preorder:";
	for (int i = 0; i < preorder.size(); i++)
	{
		cout << preorder[i] << " ";
	}
	cout << endl << endl;

	vector<int>orderOFpreINinorder;
	orderOFpreINinorder = mark_Preorder_order_in_Inorder(inorder, preorder);
	int n = inorder.size();
	int label = 0;
	Node* tree = buildtree(0, n - 1, preorder, label, orderOFpreINinorder);

	cout << "Output the tree by preorder:" << endl;
	Preorder(tree);

	cout << endl;
	system("pause");
	return 0;
}
```


---

## Range Minimum Queries
**Example:**
Sample Input: |Sample Output:

| Sample Input:| Sample Output |
| -------- | -------- |
| 6(數字串長度6)     | |
|3 1 2 6 5 4(數字串)|
|4 6<font color="gray"> (找第4個數到第6個數中最小的)</font>|4|
|2 4<font color="gray"> (找第2個數到第4個數中最小的)</font>|1|
|3 6<font color="gray"> (找第3個數到第6個數中最小的)</font>|2|
|1 6<font color="gray"> (找第1個數到第6個數中最小的)</font>|1|
|2 5<font color="gray"> (找第2個數到第5個數中最小的)</font>|1|
|3 3<font color="gray"> (找第3個數到第3個數中最小的)</font>|2|
```C++=
#include<iostream>
#include<vector>
//#include<fstream>
using namespace std;
//ifstream infile("test_in.txt");

int main()
{
	int tlen = 1;  // 要分割到多長
	int times = 0;  // 2的幾次方
	int arrNum = 0;
	cin >> arrNum;
	int* Arr = new int[arrNum];

	for (int i = 0; i < arrNum; i++)
	{
		cin >> Arr[i];
	}

	// 決定要做到多長 (2的幾次方)
	if (arrNum % 2 == 0)
	{
		while (tlen < (arrNum / 2))
		{
			tlen *= 2;
			times++;
		}
	}
	else if (arrNum % 2 == 1)
	{
		while (tlen < ((arrNum / 2) + 1))
		{
			tlen *= 2;
			times++;
		}
	}
	//
	int** smallest;							 //[1-2] [2-3] [3-4] [4-5] [5-6] [6-7] [7-8]
	smallest = new int* [times];			//[1-4] [2-5] [3-6] [4-7] [5-8]            放每段的最小值
	for (int i = 0; i < times; i++)
	{
		smallest[i] = new int[arrNum];
		for (int j = 0; j < arrNum; j++)
			smallest[i][j] = 20000000;
	}
	
	int len = 2;

	for (int j = 0; j < (arrNum - len + 1); j++)  // {1, 2, 3, 4}  len == 2 要做[1-2] [2-3] [3-4]  4 - 2 + 1 = 3次
	{
		for (int k = 0; k < len; k++)  // len是2的話就要比兩個值
		{
			if (Arr[j + k] <= smallest[0][j])   // Arr[0 + 0] Arr[0 + 1] -> [0-1] 、 Arr[1 + 0] Arr[1 + 1]  ->[1-2]
				smallest[0][j] = Arr[j + k];
		}
	}  //找出段落長為2的最小值

	int prelen = 0;  //  每層用上一層的 smallest[prelen][] 兩段組
	int currentlen = 2;  // [1, 2, 3, 4] 用 [1,2](smallest[][0])    [3,4](smallest[][0 + currentlen]) 比
	for (int i = 1; i < times; i++)
	{
		for (int j = 0; j < (arrNum - len + 1); j++)
		{
			if (smallest[prelen][j] <= smallest[prelen][j + currentlen])
				smallest[i][j] = smallest[prelen][j];
			else
				smallest[i][j] = smallest[prelen][j + currentlen];
		}
		prelen++;
		currentlen *= 2;
	}

	int begin, end, partlen;
	vector<int> result;

	tlen = 1;
	times = 0;
	while (cin >> begin >> end)
	{
		partlen = end - begin + 1;  // 段落的長度

		// 算要用多長的兩段smallest來涵蓋整個段落
		if (partlen == 2)
		{
			tlen = 2;
			times = 1;
		}
		else if (partlen % 2 == 0)
		{
			while (tlen < (partlen / 2))
			{
				tlen *= 2;
				times++;
			}
		}
		else if (partlen % 2 == 1)
		{
			while (tlen < ((partlen / 2) + 1))
			{
				tlen *= 2;
				times++;
			}
		}
		//
		if (begin == end)
		{
			result.push_back(Arr[begin - 1]);
		}
		else if (smallest[times - 1][begin - 1] >= smallest[times - 1][(begin - 1) + (partlen - tlen)])  // +1-1 削掉
			result.push_back(smallest[times - 1][end - tlen]);
		else
			result.push_back(smallest[times - 1][begin - 1]);
	}

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}
	system("pause");
}
```

---
## Gragh練習
Find the Minimum Product of Costs
**Kruskal's Algorithm**
```C++=
#include <iostream>
#include <vector>
#include <list>
#include <iomanip>

using namespace std;

struct Edge
{
	int from, to, weight;
	Edge() {};
	Edge(int u, int v, int w) :from(u), to(v), weight(w) {};
};

class Graph
{
private:
	int verNum;
	vector<vector<int>> AdjMatrix;
public:
	Graph() :verNum(0) {};
	Graph(int n) :verNum(n)
	{
		AdjMatrix.resize(verNum);
		for (int i = 0; i < verNum; i++)
		{
			AdjMatrix[i].resize(verNum);
		}

		for (int i = 0; i < verNum; i++)
		{
			for (int j = 0; j < verNum; j++)
			{
				AdjMatrix[i][j] = -1;
			}
		}
	}
	void AddEdge(int from, int to, int weight);

	int findMST();
	void GetSortedEdge(vector<struct Edge>& vec);
	friend int FindSetCollapsing(int* subset, int i);
	friend void UnionSet(int* subset, int x, int y);
};
int FindSetCollapsing(int* subset, int i)
{
	int root;
	for (root = i; subset[root] >= 0; root = subset[root]);

	while (i != root)
	{
		int parent = subset[i];
		subset[i] = root;
		i = parent;
	}
	return root;
}
void UnionSet(int* subset, int x, int y)
{

	int xroot = FindSetCollapsing(subset, x),
		yroot = FindSetCollapsing(subset, y);

	if (subset[xroot] <= subset[yroot])
	{ 
		subset[xroot] += subset[yroot];
		subset[yroot] = xroot;
	}
	else
	{ 
		subset[yroot] += subset[xroot];
		subset[xroot] = yroot;
	}
}
bool WeightComp(struct Edge e1, struct Edge e2)
{
	return (e1.weight < e2.weight);
}
void Graph::GetSortedEdge(vector<struct Edge>& edgearray) {
	//把所有邊放進edgearray
	for (int i = 0; i < verNum - 1; i++)
	{
		for (int j = i; j < verNum; j++)
		{
			if (AdjMatrix[i][j] != (-1))
			{
				edgearray.push_back(Edge(i, j, AdjMatrix[i][j]));
			}
		}
	}
	// 排序
	for (int i = 0; i < edgearray.size(); i++)
	{
		for (int j = 0; j < edgearray.size() - 1; j++)
		{
			if (edgearray[j].weight > edgearray[j + 1].weight)
			{
				Edge temp = edgearray[j];
				edgearray[j] = edgearray[j + 1];
				edgearray[j + 1] = temp;
			}
		}
	}
}
int Graph::findMST()
{
	struct Edge* finalMST = new struct Edge[verNum - 1];
	int edgesetcount = 0;

	int* subset = new int[verNum];
	for (int i = 0; i < verNum; i++)
	{
		subset[i] = -1;
	}

	vector<struct Edge> increaseWeight;
	GetSortedEdge(increaseWeight);  // 按weight大小升序排列所有edge放進increaseWeight

	for (int i = 0; i < increaseWeight.size(); i++)
	{
		if (FindSetCollapsing(subset, increaseWeight[i].from) != FindSetCollapsing(subset, increaseWeight[i].to))
		{
			finalMST[edgesetcount++] = increaseWeight[i];
			UnionSet(subset, increaseWeight[i].from, increaseWeight[i].to);
		}
	}
	int product = finalMST[0].weight * finalMST[1].weight;
	product = product % 65537;
	for (int i = 2; i < (verNum - 1); i++)
	{
		product = product * finalMST[i].weight;
		product = product % 65537;
	}
	return product;
}
void Graph::AddEdge(int from, int to, int weight)
{
	AdjMatrix[from][to] = weight;
	AdjMatrix[to][from] = weight;
}

int main()
{
	vector<int> result;
	int verNum;
	int edgeNum;
	int from;
	int to;
	int weight;
	while (true)
	{
		cin >> verNum >> edgeNum;
		if (verNum == 0 && edgeNum == 0)
			break;
		Graph G(verNum);
		for (int i = 0; i < edgeNum; i++)
		{
			cin >> from >> to >> weight;
			G.AddEdge(from, to, weight);
		}
		result.push_back(G.findMST());
	}
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}
	return 0;
}
```

---
## Linked list練習
Write a program to reverse a sublist of linked list from position m to n.
**Example:**
Input : 70->60->50->40->30->20->10, m = 3, n = 6
Output : 70->60->20->30->40->50->10 
```C++=
#include <iostream>
#include<vector>
#include<queue>
using namespace std;
queue<int> result;
class LinkedList;    //先宣告為了等一下的friend宣告
class ListNode {      //建立newNode用
private:
	int data;
	ListNode* next;
public:
	ListNode() :data(0), next(0) {};      //constructor
	ListNode(int a) :data(a), next(0) {};    //constructor

	friend class LinkedList;   //使LinkedList可以用Listnode的private成員
};

class LinkedList
{
private:
	ListNode* first;            //指向第一個node
public:
	LinkedList() :first(0) {};  //constructor

	void PushBack(int x)  // 在list的尾巴新增node
	{
		ListNode* newNode = new ListNode(x);   // 配置一個新的node

		if (first == 0) {        // 若list沒有node 則first指向newNode
			first = newNode;
			return;
		}

		ListNode* current = first;    // 用current在list中移動
		while (current->next != 0)    // 把current移到最後一個node
		{
			current = current->next;
		}
		current->next = newNode;               // 最後一個node的next指向newNode
	};

	void outputList()  //輸出整個list
	{
		if (first == 0) // 如果first指向NULL 表示list沒有資料
		{
			cout << "NULL" << endl;
		}
		else
		{
			ListNode* current = first;      // 用current在list中移動
			while (current != 0) {
				cout << current->data << "->";  // output完把current往下一個node移
				current = current->next;
			}
			cout << "NULL" << endl;
		}
	};

	void compareNode()   //實現題目要求的功能
	{
		ListNode* current = first;
		ListNode* compared = current;  //用來存要比較的node
		ListNode* comparetemp = current; //如果有更大的數, 拿來存, 並且繼續往下比
		bool compare = false;   //判斷是否有更大的
		int largest;  //如果後面有更大的數, 用來存最大的

		while (current->next != 0)
		{
			while (compared->next != 0)   //如果還有node要比
			{
				compared = compared->next;   //compared從current移到下一個node
				if (comparetemp->data < compared->data)  //如果 comparetemp的data 小於要比的 compared的data
				{
					compare = true;   //確認有更大的數
					comparetemp = compared;   //把comparetemp指向compared繼續比, 看有沒有更大的
					largest = comparetemp->data;  //把最大的data放進largest
				}
			}
			
			if (compare == true)   //如果確定有更大的
			{
				result.push(largest);   //放進queue
			}
			else   //沒找到更大的
			{
				result.push(0);   //放0進queue
			}

			compare = false;  //把compare重設成0
			current = current->next;  
			comparetemp = current;  //重設comparetemp
			compared = current;    //重設compared
		}
	}
};


int main()
{
	LinkedList a;  //建立一個list
	int x;   //放使用者輸入的整數
	cout << "Please input integers and use Ctrl+Z to end input:" << endl;
	while (cin >> x)
	{
		a.PushBack(x);
	}

	cout << "Input:" << endl;
	a.outputList();

	a.compareNode();

	cout << "[";
	while (!result.empty())
	{
		cout << result.front() << ", ";
		result.pop();
	}
	cout << "0]" << endl;
}
```

---

Write a program to group all odd nodes together followed by the even nodes in a singly linked liststructure. 
**Example:**
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
```C++=
#include <iostream>
using namespace std;

class LinkedList;    //先宣告為了等一下的friend宣告

class ListNode {      //建立newNode用
private:
	int data;
	ListNode* next;
public:
	ListNode() :data(0), next(0) {};      //constructor
	ListNode(int a) :data(a), next(0) {};    //constructor

	friend class LinkedList;   //使LinkedList可以用Listnode的private成員
};

class LinkedList
{
private:
	ListNode* first;            //指向第一個node
public:
	LinkedList() :first(0) {};  //constructor

	void PushBack(int x)  // 在list的尾巴新增node
	{
		ListNode* newNode = new ListNode(x);   // 配置一個新的node

		if (first == 0) {        // 若list沒有node 則first指向newNode
			first = newNode;
			return;
		}

		ListNode* current = first;    // 用current在list中移動
		while (current->next != 0)    // 把current移到最後一個node
		{
			current = current->next;
		}
		current->next = newNode;               // 最後一個node的next指向newNode
	};

	void outputList()  //輸出整個list
	{
		if (first == 0) // 如果first指向NULL 表示list沒有資料
		{
			cout << "NULL" << endl;
		}
		else
		{
			ListNode* current = first;       // 用current在list中移動
			while (current != 0) {                 
				cout << current->data << "->";   // output完把current往下一個node移
				current = current->next;
			}
			cout << "NULL" << endl;
		}
	};

	void sortList()   //整理odd node 和 even node
	{
		ListNode* current = first;  // 用current在list中移動
		ListNode* head = first;     //當第一個node不是奇數時重設first用
		ListNode* lastodd = first;  //用來指向"已排序"的最後一個"奇數"
		ListNode* tempodd;  //用來存正在處理的"奇數"
		
		if(first->data %2 == 0)   //當first是偶數 先把第一個找到的奇數當first
		{
			if (current->next != 0) 
			{
				while (current->next->data % 2 == 0)   //當current的next的data是"偶數"時  把current往下移  直到current的next的data是"奇數"時 
				{
					current = current->next;   //把current往下移
					if (current->next == 0)    //當next沒有指東西 跳出
						break;
				}
			}

			if (current->next != 0)
			{
				if (current->next->data % 2 != 0)   //current的next的data是"奇數"時  把它當新的first
				{
					head = current->next;   //head指向第一個找到的"奇數"
					lastodd = current->next;  //lastodd指向找到的"奇數"
					current->next = current->next->next;  // current,  也就是"奇數"前的偶數,   指向"奇數"下一個node
					head->next = first;   //head, 也就是第一個找到的"奇數", 指向first
					first = head;   //first指向第一個找到的"奇數", 把第一個找到的"奇數"變成first了
				}
			}
			
			while (current->next != 0)   //開始整理
			{

				if (current->next != 0)
				{
					while (current->next->data % 2 == 0)   //當current的next的data是"偶數"時  把current往下移  直到current的next的data是"奇數"時 
					{
						current = current->next;  //把current往下移
						if (current->next == 0)   //當next沒有指東西 跳出
							break;
					}
				}

				if (current->next != 0)
				{
					if (current->next->data % 2 != 0)   //current的next的data是"奇數"時
					{
						tempodd = current->next;   //tempodd指向找到的"奇數", 把它當正在處理的奇數
						current->next = current->next->next;   // current,  也就是"奇數"前的偶數,   指向"奇數"下一個node
						tempodd->next = lastodd->next;   //把tempodd指向"已處理的[奇數]的最後一個"所指向的node
						lastodd->next = tempodd;   //把原本的"已處理的[奇數]的最後一個" 指向正在處理的[奇數]tempodd
						lastodd = tempodd;   //把lastodd指向正在處理的[奇數]tempodd, tempodd變成"已處理的[奇數]的最後一個"
					}
				}
			}
		}

		else  //第一個數就是奇數
		{
			while (current->next != 0)
			{

				if (current->next != 0)
				{
					while (current->next->data % 2 == 0)    //同上
					{
						current = current->next;
						if (current->next == 0)
							break;
					}
				}

				if (current->next != 0)
				{
					if (current->next->data % 2 != 0)       //同上
					{
						tempodd = current->next;
						current->next = current->next->next;
						tempodd->next = lastodd->next;
						lastodd->next = tempodd;
						lastodd = tempodd;
						
					}
				}
			}
		}
	};
};

int main()
{
	LinkedList a;  //建立一個list
	int x;   //放使用者輸入的整數

	cout << "Please input integers and use Ctrl+Z to end input:" << endl;

	while (cin >> x)
	{
		a.PushBack(x);
	}

	cout << "Input:" << endl;
	a.outputList();

	a.sortList();

	cout << "Output:" << endl;
	a.outputList();
}
```


---

# Web(html,css,javascript)
## 輪盤遊戲
能下注並按下run開始遊戲。
輪盤利用三角函數寫出一圈數字，並用setInterval讓指針轉圈。
取毫秒增加轉圈的隨機性。
![](https://i.imgur.com/j2anmyB.png)
```htmlmixed=
<html>
<style>
</style>
<body>
<p id="money">you have 870000 money left.</p>
<script language="JavaScript">

function getdiv(id1,x2,y2,w2,h2,color2,text2)
{
	var newElement = document.createElement('div');
	var newText = document.createTextNode(text2);
	
	newElement.id = id1;
	
	newElement.style.position="absolute";
	
	newElement.style.top = y2;
	newElement.style.left = x2;
	
	newElement.style.width = w2;
	newElement.style.height = h2;
	
	newElement.style.color = "white";
	newElement.style.background = color2;
	
	newElement.appendChild(newText);
	document.body.appendChild(newElement);
	
}

var r = 300;
var x = 350, y = 350;
var colors = new Array("black","blue","#999900","red");

getdiv("c8763",350,50,20,20,colors[2],0);
for(i=10,a=20;i<=360;i+=20,a+=20){
	getdiv("z"+i,x+r*Math.cos((i+270)*(Math.PI/180)),y+r*Math.sin((i+270)*(Math.PI/180)),20,20,colors[0],i/10);
	getdiv("z"+a,x+r*Math.cos((a+270)*(Math.PI/180)),y+r*Math.sin((a+270)*(Math.PI/180)),20,20,colors[1],a/10);
}

for(i=0;i<(r-20);i+=4){
	getdiv("p"+i,x+i*Math.cos(270*(Math.PI/180)),y+i*Math.sin(270*(Math.PI/180)),3,3,colors[3],"");
}
var time = new Date() ;
var rodom = time.getMilliseconds()+100;
var run=1;
var stop = 0;
var star = 0;
function move(){
	stop = stop + 2;
	
	if(star < 1)
	{
	time = new Date() ;
	rodom = time.getMilliseconds()+100;
	document.getElementById("test").innerHTML = rodom;
	//document.write(rodom);
	star = 3;
	}
	if(stop > rodom){
	stop = 0;
	star = 0;
	clearInterval(run1);
	checkwin();
	clear();
	}
	
	else{
	run++;
	if(run>36)run=1;
	
	for(i=0;i<(r-20);i+=4){
	x1=x+i*Math.cos((run*10-90)*(Math.PI/180));
	y1=y+i*Math.sin((run*10-90)*(Math.PI/180));
	document.getElementById('p'+i).style.top=y1;
	document.getElementById('p'+i).style.left=x1;
	}
	}
}


//run1 = window.setInterval("move()",10);

var numberMoney=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
var total = 870000;
var remember = 0;
function clear()
{
	for(var i = 1; i <= 36; i++)
	{
		if(i % 2 == 0)
		{
			document.getElementById(i).bgColor = "black";
		}
		else
		{
			document.getElementById(i).bgColor = "red";
		}
		document.getElementById(i).className = "";
		document.getElementById("37").className = "";
		document.getElementById("38").className = "";
		document.getElementById("39").className = "";
		document.getElementById("40").className = "";
		document.getElementById("41").className = "";
		document.getElementById("37").bgColor = "white";
		document.getElementById("38").bgColor = "white";
		document.getElementById("39").bgColor = "white";
		document.getElementById("40").bgColor = "white";
		document.getElementById("41").bgColor = "white";
		
	}
}

var now=0;
function putmoney(obj)
{
	if (obj.className != "in")
	{
		obj.bgColor = Color ;
		obj.className = "in" ;
		numberMoney[obj.id]=temp;
		total -= temp;
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
	else
	{
		obj.bgColor = "white" ;
		obj.className = "" ;
		total+= numberMoney[obj.id];
		numberMoney[obj.id]=0;
		
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
}

function putmoneyBlack(obj)
{
	if (obj.className != "in")
	{
		obj.bgColor = Color ;
		obj.className = "in" ;
		numberMoney[obj.id]=temp;
		total -= temp;
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
	else
	{
		obj.bgColor = "black" ;
		obj.className = "" ;
		total+= numberMoney[obj.id];
		numberMoney[obj.id]=0;
		
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
}

function putmoneyRed(obj)
{
	if (obj.className != "in")
	{
		obj.bgColor = Color ;
		obj.className = "in" ;
		numberMoney[obj.id]=temp;
		total -= temp;
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
	else
	{
		obj.bgColor = "red" ;
		obj.className = "" ;
		total+= numberMoney[obj.id];
		numberMoney[obj.id]=0;
		
		document.getElementById("money").innerHTML = "you have " + total + " money left." ;
	}
}
function SE(a,obj)
{
	if(a==1000)
	{
		if (obj.className != "in" )
		{
			temp = 1000;
			
			Color = "#b3d1ff" ;
			obj.bgColor = "#b3d1ff" ;
			obj.className = "in" ;
		}
		else if(obj.className == "in")
		{
			
			obj.className = "" ;
			obj.bgColor = "white" ;
		}
	}
	if(a==2000)
	{	
		if (obj.className != "in")
		{
			temp = 2000;
			
			Color = "#3385ff" ;
			obj.bgColor = "#3385ff" ;
			obj.className = "in" ;
		}
		else if(obj.className == "in")
		{
			
			obj.className = "" ;
			obj.bgColor = "white" ;
		}	
	}
	if(a==5000 )
	{
		if (obj.className != "in" )
		{
			temp = 5000;
			
			Color = "#0047b3" ;
			obj.bgColor = "#0047b3" ;
			obj.className = "in" ;
		}
		else if(obj.className == "in")
		{
			
			obj.className = "" ;
			obj.bgColor = "white" ;
		}
	}
}
function checkwin()
{
	for (var i = 1, x = 10 ; i <= 36 ; i++,x+=10)
	{
		if (document.getElementById(i).className == "in")
		{
			if (document.getElementById(i).innerHTML == document.getElementById("z"+x).innerHTML &&i==run)
				total = total + numberMoney[run] * 36;
		}
	}
	if (document.getElementById("37").className == "in")
		{
			if(run >= 1 && run <= 12)
				total = total + numberMoney[37] * 2;
		}
		if (document.getElementById("38").className == "in")
		{
			if(run >= 13 && run <= 24)
				total = total + numberMoney[38] * 2;
		}
		if (document.getElementById("39").className == "in")
		{
			if(run >= 25 && run <= 36)
				total = total + numberMoney[39] * 2;
		}
		if (document.getElementById("40").className == "in")
		{
			if(run % 2 == 1)
				total = total + numberMoney[40];
		}
		if (document.getElementById("41").className == "in")
		{
			if(run % 2 == 0)
				total = total + numberMoney[41];
		}
	document.getElementById("money").innerHTML = "you have " + total + " money left.";
}


</script>




<div id="game" style="position:absolute;top:50px;left:800px;">
<table border="3" bgcolor="white" width="500" height="150" >

<tr width="50" height="50">
<td id=a colspan="4" onclick="SE(1000,this)" align="center">1000</td>
<td id=b colspan="4" onclick="SE(2000,this)" align="center">2000</td>
<td id=c colspan="4" onclick="SE(5000,this)" align="center">5000</td>
</tr>

<tr>
<td id="1" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white" >1</td>
<td id="4" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">4</td>
<td id="7" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">7</td>
<td id="10" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">10</td>
<td id="13" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">13</td>
<td id="16" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">16</td>
<td id="19" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">19</td>
<td id="22" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">22</td>
<td id="25" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">25</td>
<td id="28" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">28</td>
<td id="31" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">31</td>
<td id="34" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">34</td>
</tr>
<tr>
<td id="2" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">2</td>
<td id="5" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">5</td>
<td id="8" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">8</td>
<td id="11" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">11</td>
<td id="14" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">14</td>
<td id="17" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">17</td>
<td id="20" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">20</td>
<td id="23" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">23</td>
<td id="26" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">26</td>
<td id="29" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">29</td>
<td id="32" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">32</td>
<td id="35" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">35</td>
</tr>
<tr>
<td id="3" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">3</td>
<td id="6" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">6</td>
<td id="9" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">9</td>
<td id="12" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">12</td>
<td id="15" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">15</td>
<td id="18" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">18</td>
<td id="21" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">21</td>
<td id="24" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">24</td>
<td id="27" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">27</td>
<td id="30" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">30</td>
<td id="33" bgcolor="red" class="n" onclick="putmoneyRed(this)" width="50" height="50" align="center" style="color:white">33</td>
<td id="36" bgcolor="Black" class="n" onclick="putmoneyBlack(this)" width="50" height="50" align="center" style="color:white">36</td>
</tr>

<tr>
<td id="37" colspan="4" class="n" onclick="putmoney(this)" width="50" height="40" align="center">1 to 12</td>
<td id="38" colspan="4" class="n" onclick="putmoney(this)" width="50" height="40" align="center">13 to 24</td>
<td id="39" colspan="4" class="n" onclick="putmoney(this)" width="50" height="40" align="center">25 to 36</td>
</tr>

<tr>
<td id="40" colspan="6" class="n" onclick="putmoney(this)" width="50" height="40" align="center">Red</td>
<td id="41" colspan="6" class="n" onclick="putmoney(this)" width="50" height="40" align="center">Black</td>
</tr>
</td>
</table>
</div>
<input type="button" value="stop"
		onClick="clearInterval(run1);">

<input type="button" value="run"
		onClick="run1 = window.setInterval('move()' , 10);">
<p id="test">
123
</p>


</body>
</html>
```

---

# C#
## 角色移動
![](https://i.imgur.com/o9C6X3l.jpg)
```c#=
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace _1071441_15_2
{
    public partial class Form1 : Form
    {
        Image prince = new Bitmap(Properties.Resources.Prince); // 人物圖
        Rectangle[,] r = new Rectangle[4, 4]; // 人物圖的 16張小圖的矩形區域
        int dir = 2; // 人物前進方向 0 往下，1 往上，2 往右，3 往左
        int spriteStep = 0;    // 人物小圖的分解圖 0 ~ 3

        Image bg = new Bitmap(Properties.Resources.kingdomcome); // 背景圖
        int dx = 0, dy = 0; // 背景圖的X軸、Y軸的偏移值

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            // 繪出背景圖
            e.Graphics.DrawImage(bg, dx, dy, bg.Width, bg.Height);
            // 在視窗中心繪出人物小圖
            e.Graphics.DrawImage(prince, ClientSize.Width / 2 - 85 / 2,
                                         ClientSize.Height / 2 - 153 / 2,
                                         r[dir, spriteStep], GraphicsUnit.Pixel);

        }

        private void Form1_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.KeyData == Keys.Up) // 人物往上
                dir = 1;
            else if (e.KeyData == Keys.Down)  // 人物往下 背景往上
                dir = 0;
            else if (e.KeyData == Keys.Right) // 人物往右 背景往左
                dir = 2;
            else if (e.KeyData == Keys.Left)  // 人物往左
                dir = 3;
        }

        private void Timer1_Tick(object sender, EventArgs e)
        {
            spriteStep = spriteStep + 1; // 下一張人物小圖
            if (spriteStep > 3) spriteStep = 0;

            Invalidate();

        }

        private void Timer2_Tick(object sender, EventArgs e)
        {
            if (dir == 0) dy = dy - 5;       // 背景往上 偏移値遞減
            else if (dir == 1) dy = dy + 5;  // 背景往下 偏移値遞增
            else if (dir == 2) dx = dx - 5;  // 背景往左 偏移値遞減
            else if (dir == 3) dx = dx + 5;  // 背景往右 偏移値遞增

            Invalidate();

        }

        public Form1()
        {
            InitializeComponent();
            DoubleBuffered = true;
            // 計算出 人物圖的 16張小圖的矩形區域
            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                    r[i, j] = new Rectangle(j * 85, i * 153, 85, 153);
            timer1.Start();
            timer2.Start();

        }
    }
}

```
## 接水果遊戲
![](https://i.imgur.com/pmU8Abn.png)
```C#=
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Drawing.Imaging;

namespace _1071441_hw6
{
    public partial class Form1 : Form
    {
        int received = 0;
        Random rd = new Random();
        int counter = 120;
        Bitmap bg;
        Bitmap bowl = Properties.Resources.Bowl;
        Bitmap banana = Properties.Resources.Banana;
        Bitmap tomato = Properties.Resources.Tomato;
        Bitmap strawberry = Properties.Resources.StawBerry;
        int bg_counter = 2;
        Point MousePos;
        //隨機掉落位置X
        int drop_X1 = 350 , drop_X2 = 400, drop_X3 = 168;
        int drop_Y1 = 0;
        int drop_Y2 = 0;
        int drop_Y3 = 0;
        int dropSpeed = 6;
        int dropSpeed2 = 4;
        int dropSpeed3 = 3;
        int dropsituation;
        float[][] cmArray1 =
               {
                  new float[] {1, 0, 0, 0,    0},
                  new float[] {0, 1, 0, 0,    0},
                  new float[] {0, 0, 1, 0,    0},
                  new float[] {0, 0, 0, 0.5f, 0},
                  new float[] {0, 0, 0, 0,    1}
               };

        public Form1()
        {
            InitializeComponent();
        }
        private void Form1_Load(object sender, EventArgs e)
        {
            int drop_X1 = rd.Next(ClientSize.Width);
            int drop_X2 = rd.Next(ClientSize.Width);
            int drop_X3 = rd.Next(ClientSize.Width);
            bg = Properties.Resources.background_1;
            label1.ForeColor = Color.Red;
            label2.ForeColor = Color.Red;
        }
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            label1.Location = new Point(0, ClientSize.Height - 40);  //重置label1位置
            label2.Location = new Point(0, ClientSize.Height - 25);  //重置label2位置
            //畫背景
            ColorMatrix bgM = new ColorMatrix(cmArray1);
            ImageAttributes ia1 = new ImageAttributes();
            ia1.SetColorMatrix(bgM, ColorMatrixFlag.Default, ColorAdjustType.Bitmap);
            e.Graphics.DrawImage(bg,
                 new Rectangle(0, 10, ClientSize.Width, ClientSize.Height - 100), 0, 0, bg.Width, bg.Height, GraphicsUnit.Pixel, ia1);

            //畫碗
            e.Graphics.DrawImage(bowl,
            new Rectangle(MousePos.X - bowl.Width / 2, ClientSize.Height - 90, bowl.Width, bowl.Height), 0, 0, bowl.Width, bowl.Height, GraphicsUnit.Pixel);

            if (dropsituation == 0)
            {
                e.Graphics.DrawImage(banana,
              new Rectangle(drop_X1, drop_Y1, banana.Width, banana.Height), 0, 0, banana.Width, banana.Height, GraphicsUnit.Pixel);

                e.Graphics.DrawImage(tomato,
               new Rectangle(drop_X2, drop_Y2, tomato.Width, tomato.Height), 0, 0, tomato.Width, tomato.Height, GraphicsUnit.Pixel);

                e.Graphics.DrawImage(strawberry,
               new Rectangle(drop_X3, drop_Y3, strawberry.Width, strawberry.Height), 0, 0, strawberry.Width, strawberry.Height, GraphicsUnit.Pixel);
            }

            if (dropsituation == 1)
            {
                e.Graphics.DrawImage(banana,
             new Rectangle(drop_X1, drop_Y2, banana.Width, banana.Height), 0, 0, banana.Width, banana.Height, GraphicsUnit.Pixel);

                e.Graphics.DrawImage(tomato,
               new Rectangle(drop_X2, drop_Y3, tomato.Width, tomato.Height), 0, 0, tomato.Width, tomato.Height, GraphicsUnit.Pixel);
            }

            if (dropsituation == 2)
            {
                e.Graphics.DrawImage(tomato,
              new Rectangle(drop_X2, drop_Y1, tomato.Width, tomato.Height), 0, 0, tomato.Width, tomato.Height, GraphicsUnit.Pixel);

                e.Graphics.DrawImage(strawberry,
               new Rectangle(drop_X3, drop_Y3, strawberry.Width, strawberry.Height), 0, 0, strawberry.Width, strawberry.Height, GraphicsUnit.Pixel);
            }

            if (dropsituation == 3)
            {
                e.Graphics.DrawImage(banana,
             new Rectangle(drop_X1, drop_Y3, banana.Width, banana.Height), 0, 0, banana.Width, banana.Height, GraphicsUnit.Pixel);

                e.Graphics.DrawImage(strawberry,
             new Rectangle(drop_X3, drop_Y2, strawberry.Width, strawberry.Height), 0, 0, strawberry.Width, strawberry.Height, GraphicsUnit.Pixel);
            }

            if (dropsituation == 4)
            {
                e.Graphics.DrawImage(tomato,
              new Rectangle(drop_X2, drop_Y1, tomato.Width, tomato.Height), 0, 0, tomato.Width, tomato.Height, GraphicsUnit.Pixel);
            }

            if (dropsituation == 5)
            {
                e.Graphics.DrawImage(banana,
             new Rectangle(drop_X1, drop_Y1, banana.Width, banana.Height), 0, 0, banana.Width, banana.Height, GraphicsUnit.Pixel);
            }
        }
        private void Timer1_Tick(object sender, EventArgs e)
        {
            counter--;
            label1.Text = "Remaining:  " + counter.ToString() + "  Seconds";
        }
        private void Timer2_Tick(object sender, EventArgs e)
        {
            if (bg_counter == 3)
                bg_counter = 1;
            else
                bg_counter++;

            if(bg_counter == 1)
                bg = Properties.Resources.background_1;
            else if(bg_counter == 2)
                bg = Properties.Resources.background_2;
            else if(bg_counter == 3)
                bg = Properties.Resources.background_3;

        }
        private void Timer3_Tick(object sender, EventArgs e)
        {
            if(counter == 0)    //結束
            {
                timer1.Stop();
                timer2.Stop();
                timer3.Stop();
                timer4.Stop();
            }
            drop_Y1 += dropSpeed;
            drop_Y2 += dropSpeed2;
            drop_Y3 += dropSpeed3;
            label2.Text = "Received:  " + received.ToString();
            //s0
            if (drop_Y1 >= ClientSize.Height - 105 && drop_Y1 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 0
                && drop_X1 >= MousePos.X - bowl.Width / 2 && drop_X1 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y1 = ClientSize.Width + 50;
                received++;
            }
            if (drop_Y2 >= ClientSize.Height - 105 && drop_Y2 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 0
                && drop_X2 >= MousePos.X - bowl.Width / 2 && drop_X2 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y2 = ClientSize.Width + 50;
                received++;
            }

            if (drop_Y3 >= ClientSize.Height - 105 && drop_Y3 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 0
                && drop_X3 >= MousePos.X - bowl.Width / 2 && drop_X3 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y3 = ClientSize.Width + 50;
                received++;
            }
            //s1
            if (drop_Y2 >= ClientSize.Height - 105 && drop_Y2 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 1
               && drop_X1 >= MousePos.X - bowl.Width / 2 && drop_X1 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y2 = ClientSize.Width + 50;
                received++;
            }
            if (drop_Y3 >= ClientSize.Height - 105 && drop_Y3 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 1
               && drop_X2 >= MousePos.X - bowl.Width / 2 && drop_X2 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y3 = ClientSize.Width + 50;
                received++;
            }
            //s2
            if (drop_Y1 >= ClientSize.Height - 105 && drop_Y1 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 2
               && drop_X2 >= MousePos.X - bowl.Width / 2 && drop_X2 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y1 = ClientSize.Width + 50;
                received++;
            }
            if (drop_Y3 >= ClientSize.Height - 105 && drop_Y3 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 2
               && drop_X3 >= MousePos.X - bowl.Width / 2 && drop_X3 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y3 = ClientSize.Width + 50;
                received++;
            }
            //s3
            if (drop_Y3 >= ClientSize.Height - 105 && drop_Y3 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 3
               && drop_X1 >= MousePos.X - bowl.Width / 2 && drop_X1 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y3 = ClientSize.Width + 50;
                received++;
            }
            if (drop_Y2 >= ClientSize.Height - 105 && drop_Y2 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 3
           && drop_X3 >= MousePos.X - bowl.Width / 2 && drop_X3 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y2 = ClientSize.Width + 50;
                received++;
            }
            //s4
            if (drop_Y1 >= ClientSize.Height - 105 && drop_Y1 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 4
              && drop_X2 >= MousePos.X - bowl.Width / 2 && drop_X2 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y1 = ClientSize.Width + 50;
                received++;
            }
            //s5
            if (drop_Y1 >= ClientSize.Height - 105 && drop_Y1 <= ClientSize.Height - 90 + bowl.Height && dropsituation == 5
              && drop_X1 >= MousePos.X - bowl.Width / 2 && drop_X1 <= MousePos.X + bowl.Width / 2)
            {
                drop_Y1 = ClientSize.Width + 50;
                received++;
            }
            Invalidate();
        }
        private void RestartToolStripMenuItem_Click(object sender, EventArgs e)
        {
            counter = 120;
            received = 0;
            drop_X1 = rd.Next(ClientSize.Width);
            drop_X2 = rd.Next(ClientSize.Width);
            drop_X3 = rd.Next(ClientSize.Width);
            drop_Y1 = 0;
            drop_Y2 = 0;
            drop_Y3 = 0;
            dropsituation = rd.Next(6);
            timer1.Start();
            timer2.Start();
            timer3.Start();
            timer4.Start();
        }

        private void Form1_MouseMove(object sender, MouseEventArgs e)
        {
            MousePos = e.Location;
        }
        private void Timer4_Tick(object sender, EventArgs e)
        {
            drop_X1 = rd.Next(ClientSize.Width);
            drop_X2 = rd.Next(ClientSize.Width);
            drop_X3 = rd.Next(ClientSize.Width);
            drop_Y1 = 0;
            drop_Y2 = 0;
            drop_Y3 = 0;
            dropsituation = rd.Next(6);
        }
    }
}

```
## 
---

# RISC-V
 give Nnumbers and a positive integer M. You will have to sort the N numbers in ascending order of their modulo M value. If there is a tie between an odd number and an even number (that is their modulo M value is the same) then the odd number will precede the even number. If there is a tie between two odd numbers (that is their modulo M value is the same) then the larger odd number will precede the smaller odd number and if there is a tie between two even numbers (that is their modulo M value is the same) then the smaller even number will precede the larger even number.
 
```clike=
.globl main
.data
	endl:	.string"\n"
	Input0:	.string"請輸入N和M，N代表要排序的數列大小，M代表要mod的值:"
	Input1:	.string"請輸入要排列的N個數:"
	numbers:	.word 1000
.text
#

main:
	la a0, Input0 #輸出  "輸入N.M:"
	li a7, 4
	ecall
	la a0, endl #換行
	li a7, 4
	ecall
	li a7, 5 #寫值到a0
	ecall
	add t0, a0, zero #N 放到 t0
	li a7, 5 #寫值到a0
	ecall
	add t1, a0, zero #M 放到  t1
	la a0, Input1 #輸出  "輸入N個數:"
	li a7, 4
	ecall
	la a0, endl #換行
	li a7, 4
	ecall
	
	la s6, numbers  #  s6 = numbers 的 baseAddress
	add t2, s6, zero # t2用來當等等放值用的address
	slli t3, t0, 3 # t3 = N * 8
	add s7, s6, t3  # s7 = numbers[N] 的 address
			
add t2, zero, zero  #  i = 0
LOOP: #寫N個值進陣列
	slli t3, t2, 3 #  i * 8
	add t3, t3, s6 # numbers[i] 的 address
	li a7, 5
	ecall
	sb a0, 0(t3)
	addi t2, t2, 1
	blt t2, t0, LOOP
	
	la a0, endl #換行
	li a7, 4
	ecall
	addi s1, t0, -1
	addi s10, zero, 2 # s10 = 2
	add t2, zero, zero  # t2 = j = 0
LOOPJ:
	add t3, zero, zero  # t3 = k = 0
LOOPK:
	addi t4, t3, 1  # t4 = k + 1
	slli t5, t3, 3 # t5 = k * 8
	slli t6, t4, 3 # t6 = (k + 1) *8
	add t5, t5, s6 # t5 = numbers[k] 的 address
	add t6, t6, s6 # t6 = number[k+1] 的 address
	lb s2, 0(t5) # s2 = numbers[k]
	lb s3, 0(t6) # s3 = numbers[k+1]
	rem s4, s2, t1 # s4 = number[k]  %  M
	rem s5, s3, t1 # s5 = number[k+1] % M
	rem s8, s2, s10 # s8 = numbers[k] % 2
	rem s9, s3, s10 # s9 = numbers[k+1] % 2
	
	ble s4, s5, L1  # 第1個 if    if (numbers[k] % M > numbers[k + 1] % M)
	jal x1, SWAP
L1:	# 第2個 if 開始
	bne s4, s5, KE	 # if (numbers[k] % M == numbers[k + 1] % M)
	# 第2個 if  裡的 第1個if
	beq s8, zero, IF22  # if(numbers[k] % 2 != 0
	beq s9, zero, IF22  #  && numbers[k + 1] % 2 != 0
	bge s2, s3, IF22    # && numbers[k] < numbers[k + 1]
	jal x1, SWAP
	j KE
IF22:	# 第2個 if  裡的 第2個if
	bne s8, zero, IF23  # if(numbers[k] % 2 == 0
	bne s9, zero, IF23  # && numbers[k + 1] % 2 == 0
	ble s2, s3, IF23    # && numbers[k] > numbers[k + 1]
	jal x1, SWAP
	j KE
IF23	:# 第2個 if  裡的 第3個if
	bne s8, zero, KE   # numbers[k] % 2 == 0
	beq s9, zero, KE   #&& numbers[k + 1] % 2 != 0
	jal x1, SWAP
	j KE
KE:	#FORK結束
	addi t3, t3, 1 # k++
	blt t3, s1, LOOPK
	
	addi t2, t2, 1  # j++
	blt t2, t0, LOOPJ
	
	j PRINT
	
	
SWAP:
	sb s3, 0(t5) # numbers[k] = number[k+1]
	sb s2, 0(t6) #number[k+1] = number[k]
	lb s2, 0(t5) # s2 = numbers[k]
	lb s3, 0(t6) # s3 = numbers[k+1]
	# numbers[k] % M 跟 numbers[k+1] % M也要換
	add s11, s4, zero
	add s4, s5, zero
	add s5, s11, zero
	# numbers[k] % 2 跟 numbers[k+1] % 2也要換
	add s11, s8, zero
	add s8, s9, zero
	add s9, s11, zero
	jalr x0, x1, 0
	
PRINT:
	add t2, zero, zero  #  l = 0
LOOPL:
	slli t3, t2, 3 #  l * 8
	add t3, t3, s6 # numbers[l] 的 address
	lb a0, 0(t3)  # number[l]
	li a7, 1
	ecall
	la a0, endl #換行
	li a7, 4
	ecall
	addi t2, t2, 1
	blt t2, t0, LOOPL
	j EXIT
	
EXIT:
	li a7, 10
	ecall
``` 
# C++實作Instruction Scheduling
Example input and output:
![](https://i.imgur.com/if5T5Tg.png)![](https://i.imgur.com/mMXUjzR.png)


```c++=
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<sstream>
#include<vector>
using namespace std;


void upToLow(string& s)   //全部換成小寫好比較
{
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] >= 'A' && s[i] <= 'Z')
			s[i] += 32;
	}
}

struct ASALU
{
	int count = 0;  // 0 表示沒東西 其他數字表示剩餘多少cycle算完
	int result = 0;
	string RD;
	string mrat;
	int rs11;
	int rs22;
	string op;
};

struct MDALU
{
	int count = 0;  // 0 表示沒東西 其他數字表示剩餘多少cycle算完
	int result = 0;
	string RD;
	string mrat;
	int rs11;
	int rs22;
	string op;
};

struct RSp
{
	string rd;
	int rs1 = 2000000000;
	int rs2 = 2000000000;
	string preRs1;  //要等的值 在哪個rs
	string preRs2;  //要等的值 在哪個rs
	string oprend;
	bool ready = false;   //準備好dispatch了
	bool justI = false;   //剛ISSUE 同cycle不能同時dispatch
	bool justC = false;   //剛capture 同cycle不能同時dispatch
};

struct ARS
{
	RSp rs[3];
};

struct MRS
{
	RSp rs[2];
};

vector<string> InsProcess(string instru)
{
	string ins;
	string insType;
	string rd;
	string rs1;
	string rs2;
	stringstream ss;
	int io = 0;

	ss.clear();
	ss.str("");
	ss << instru;
	ss >> insType;  // add
	ss >> ins;  // F1,F2,F3

	for (int i = 1; i < ins.size(); i++)   //  i 從 1 開始直接忽略一開始的"F"
	{
		if (ins[i] == ',')     //x1, 的"逗號"的位置
		{
			io = i;
			break;
		}
		rd += ins[i];  // rd == "1' (F1)
	}

	for (int i = io + 2; i < ins.size(); i++)  //  i 從 io + 2 開始直接忽略第二個的"F"
	{
		if (ins[i] == ',')     //x2, 的"逗號"的位置
		{
			io = i;
			break;
		}
		rs1 += ins[i];  //rs1 == "2" (F2)
	}

	for (int i = io + 1; i < ins.size(); i++) //  i 從 io + 1 開始直接忽略" , "
	{
		if (ins[i] == 'f')   // addi 的話沒有 F
			continue;
		rs2 += ins[i];   //rs2 == F3 or rs2 == 1 
	}
	vector<string> i;  // i[0] = insType  , i[1] = rd , i[2] = rs1 , i[3] = rs2
	i.push_back(insType);
	i.push_back(rd);
	i.push_back(rs1);
	i.push_back(rs2);

	return i;
}

void issue_capture(queue<string>& iq, ARS& as, MRS& md, string(&RAT)[5], int(&RF)[5])
{
	map<string, string> m_RAT;
	map<string, int> m_RF;
	//	m_RAT["1"] = RAT[0]; m_RAT["2"] = RAT[1]; m_RAT["3"] = RAT[2]; m_RAT["4"] = RAT[3]; m_RAT["5"] = RAT[4];
	//	m_RF["1"] = RF[0]; m_RF["2"] = RF[1]; m_RF["3"] = RF[2]; m_RF["4"] = RF[3]; m_RF["5"] = RF[4];
	if (!iq.empty())
	{
		int rp; //空的rs的位置
		int check = 0;
		string temp;
		string t2;
		vector<string> insParted;
		int trat;
		string Srp;
		int rs1;
		int rs2;
		stringstream tra;
		temp = iq.front();
		insParted = InsProcess(temp);

		if (insParted[0] == "add" || insParted[0] == "sub" || insParted[0] == "addi")   //要進 ADD/SUB/ADDI 的 RS的狀況
		{

			for (int i = 0; i < 3; i++)    //檢查rs有沒有位置
			{
				if (as.rs[i].oprend == "")
				{
					rp = i;
					break;
				}
				else
					check++;
			}

			if (check == 3)   //rs沒位置 直接結束issue不做
				return;
			iq.pop();  //有位置的話

			if (insParted[0] == "add" || insParted[0] == "addi")
				as.rs[rp].oprend += "+";
			else if (insParted[0] == "sub")
				as.rs[rp].oprend += "-";


			as.rs[rp].rd = insParted[1];

			tra.clear();
			tra.str("");
			tra << insParted[2];
			tra >> rs1;
			rs1--;
			tra.clear();
			tra.str("");
			tra << insParted[3];
			tra >> rs2;
			rs2--;

			if (RAT[rs1] != "")  //rat 裡有東西
				as.rs[rp].preRs1 = RAT[rs1];
			else                            //rat 沒東西 直接把rf裡的值放進 rs1  !!!capture!!!
				as.rs[rp].rs1 = RF[rs1];

			if (insParted[0] == "add" || insParted[0] == "sub")
			{
				if (RAT[rs2] != "")  //rat 裡有東西
					as.rs[rp].preRs2 = RAT[rs2];
				else                            //rat 沒東西 直接把rf裡的值放進 rs2   !!!capture!!!
					as.rs[rp].rs2 = RF[rs2];
			}
			else   // insType 是 addi 的情況， rs2已經是常數 準備好了
				as.rs[rp].rs2 = (rs2 + 1);

			//更新RAT
			tra.clear();
			tra.str("");
			tra << as.rs[rp].rd;
			tra >> trat;
			trat--;

			tra.clear();
			tra.str("");
			tra << (rp + 1);
			tra >> Srp;

			RAT[trat] = "";
			RAT[trat] += "a";
			RAT[trat] += Srp;		//更新RAT

			as.rs[rp].justI = 1;  //剛issue 不能dispatch

		}

		else if (insParted[0] == "mul" || insParted[0] == "div")   //要進 MUL/DIV 的 RS的狀況
		{

			for (int i = 0; i < 2; i++)    //檢查rs有沒有位置
			{
				if (md.rs[i].oprend == "")
				{
					rp = i;
					break;
				}
				else
					check++;
			}

			if (check == 2)   //rs沒位置 直接結束issue不做
				return;

			iq.pop();

			if (insParted[0] == "mul")
				md.rs[rp].oprend += "*";
			else if (insParted[0] == "div")
				md.rs[rp].oprend += "/";

			md.rs[rp].rd = insParted[1];

			tra.clear();
			tra.str("");
			tra << insParted[2];
			tra >> rs1;
			rs1--;
			tra.clear();
			tra.str("");
			tra << insParted[3];
			tra >> rs2;
			rs2--;

			if (RAT[rs1] != "")  //rat 裡有東西
				md.rs[rp].preRs1 = RAT[rs1];
			else                            //rat 沒東西 直接把rf裡的值放進 rs1  !!!capture!!!
				md.rs[rp].rs1 = RF[rs1];


			if (RAT[rs2] != "")  //rat 裡有東西
				md.rs[rp].preRs2 = RAT[rs2];
			else                            //rat 沒東西 直接把rf裡的值放進 rs2   !!!capture!!!
				md.rs[rp].rs2 = RF[rs2];

			//更新RAT
			tra.clear();
			tra.str("");
			tra << md.rs[rp].rd;
			tra >> trat;
			trat--;

			tra.clear();
			tra.str("");
			tra << (rp + 1);
			tra >> Srp;

			RAT[trat] = "";
			RAT[trat] += "m";
			RAT[trat] += Srp;  //更新RAT

		//md.rs[rp].justI = 1;  //剛issue 不能dispatch
		}
	}
}

void dispatch(ARS& as, MRS& md, ASALU& ASalu, MDALU& MDalu)  // + -  >  2cycles, *  > 4cycles, /  > 8cycles
{
	stringstream trans;
	int rs1 = 0;
	int rs2 = 0;
	string Si;
	for (int i = 0; i < 3; i++)
	{
		if (as.rs[i].ready == true && ASalu.count == 0 && ASalu.RD == "")		//要dispatch ADD/SUB/ADDi
		{
			trans.clear();		//轉成int
			trans.str("");
			trans << as.rs[i].rs1;
			trans >> rs1;

			trans.clear();		//轉成int
			trans.str("");
			trans << as.rs[i].rs2;
			trans >> rs2;

			ASalu.RD = as.rs[i].rd;		//alu 的 rd
			if (as.rs[i].oprend == "+")
				ASalu.result = rs1 + rs2;		//alu 的 result
			else if (as.rs[i].oprend == "-")
				ASalu.result = rs1 - rs2;		//alu 的 result

			ASalu.rs11 = rs1;
			ASalu.rs22 = rs2;
			ASalu.op = as.rs[i].oprend;

			ASalu.count = 2;		// 計時 alu 甚麼時候會算完
			ASalu.mrat = "";
			ASalu.mrat += 'a';			//到時候write時要對到rat
			trans.clear();		//轉成string
			trans.str("");
			trans << (i + 1);
			trans >> Si;
			ASalu.mrat += Si;

			as.rs[i].oprend = "";		//清空 RS
			as.rs[i].rs1 = 2000000000;
			as.rs[i].rs2 = 2000000000;
			as.rs[i].preRs1 = "";
			as.rs[i].preRs2 = "";
			as.rs[i].rd = "";
			as.rs[i].ready = false;
			as.rs[i].justC = 0;
			as.rs[i].justI = 0;
			break;
		}
	}

	for (int i = 0; i < 2; i++)
	{
		if (md.rs[i].ready == true && MDalu.count == 0 && MDalu.RD == "")		//要dispatch MUL/DIV
		{
			trans.clear();		//轉成int
			trans.str("");
			trans << md.rs[i].rs1;
			trans >> rs1;

			trans.clear();		//轉成int
			trans.str("");
			trans << md.rs[i].rs2;
			trans >> rs2;

			MDalu.RD = md.rs[i].rd;		//alu 的 rd
			if (md.rs[i].oprend == "*")
			{
				MDalu.result = rs1 * rs2;		//alu 的 result
				MDalu.count = 4;		// 計時 alu 甚麼時候會算完
			}
			else if (md.rs[i].oprend == "/")
			{
				MDalu.result = rs1 / rs2;		//alu 的 result
				MDalu.count = 8;		// 計時 alu 甚麼時候會算完
			}

			MDalu.rs11 = rs1;
			MDalu.rs22 = rs2;
			MDalu.op = md.rs[i].oprend;

			MDalu.mrat = "";
			MDalu.mrat += 'm';			//到時候write時要對到rat
			trans.clear();		//轉成string
			trans.str("");
			trans << (i + 1);
			trans >> Si;
			MDalu.mrat += Si;

			md.rs[i].oprend = "";		//清空 RS
			md.rs[i].rs1 = 2000000000;
			md.rs[i].rs2 = 2000000000;
			md.rs[i].preRs1 = "";
			md.rs[i].preRs2 = "";
			md.rs[i].rd = "";
			md.rs[i].ready = false;
			md.rs[i].justC = 0;
			md.rs[i].justI = 0;
			break;
		}
	}
}

void writeResult(ARS& as, MRS& md, ASALU& ASalu, MDALU& MDalu, map<string, string>& m_RAT, map<string, int>& m_RF, string(&RAT)[5], int(&RF)[5])
{
	int Ird;
	stringstream ss;

	// RS
	if (ASalu.RD != "" && ASalu.count == 0)  // ASalu檢查 add/sub rs
	{
		for (int i = 0; i < 3; i++)
		{
			if (as.rs[i].preRs1 == ASalu.mrat)
			{
				as.rs[i].rs1 = ASalu.result;
				as.rs[i].preRs1 = "";
			}
			if (as.rs[i].preRs2 == ASalu.mrat)
			{
				as.rs[i].rs2 = ASalu.result;
				as.rs[i].preRs2 = "";
			}
		}
	}

	if (ASalu.RD != "" && ASalu.count == 0)  // ASalu檢查 mul/div rs
	{
		for (int i = 0; i < 2; i++)
		{
			if (md.rs[i].preRs1 == ASalu.mrat)
			{
				md.rs[i].rs1 = ASalu.result;
				md.rs[i].preRs1 = "";
			}
			if (md.rs[i].preRs2 == ASalu.mrat)
			{
				md.rs[i].rs2 = ASalu.result;
				md.rs[i].preRs2 = "";
			}
		}
	}

	if (MDalu.RD != "" && MDalu.count == 0)  // MDalu檢查 mul/div rs
	{
		for (int i = 0; i < 2; i++)
		{
			if (md.rs[i].preRs1 == MDalu.mrat)
			{
				md.rs[i].rs1 = MDalu.result;
				md.rs[i].preRs1 = "";
			}
			if (md.rs[i].preRs2 == MDalu.mrat)
			{
				md.rs[i].rs2 = MDalu.result;
				md.rs[i].preRs2 = "";
			}
		}
	}

	if (MDalu.RD != "" && MDalu.count == 0)  // MDalu檢查 add/sub rs
	{
		for (int i = 0; i < 3; i++)
		{
			if (as.rs[i].preRs1 == MDalu.mrat)
			{
				as.rs[i].rs1 = MDalu.result;
				as.rs[i].preRs1 = "";
			}
			if (as.rs[i].preRs2 == MDalu.mrat)
			{
				as.rs[i].rs2 = MDalu.result;
				as.rs[i].preRs2 = "";
			}
		}
	}

	// RAT  RF
	if (ASalu.RD != "" && ASalu.count == 0)
	{
		for (int i = 0; i < 5; i++)		//檢查 rat 有沒有
		{
			if (RAT[i] == ASalu.mrat)
			{
				RAT[i] = "";
				RF[i] = ASalu.result;
			}
		}
	}

	if (MDalu.RD != "" && MDalu.count == 0)
	{
		for (int i = 0; i < 5; i++)		//檢查 rat 有沒有
		{
			if (RAT[i] ==MDalu.mrat)
			{
				RAT[i] = "";
				RF[i] = MDalu.result;
			}
		}
	}
	//
	if (ASalu.count == 0)
	{
		ASalu.mrat = "";
		ASalu.RD = "";
		ASalu.op = "";
		ASalu.rs11 = 2000000000;
		ASalu.rs22 = 2000000000;
	}
	if (MDalu.count == 0)
	{
		MDalu.mrat = "";
		MDalu.RD = "";
		MDalu.op = "";
		MDalu.rs11 = 2000000000;
		MDalu.rs22 = 2000000000;
	}
	for (int i = 0; i < 3; i++)
	{
		if (as.rs[i].rs1 != 2000000000 && as.rs[i].rs2 != 2000000000)
			as.rs[i].ready = true;
	}

	for (int i = 0; i < 2; i++)
	{
		if (md.rs[i].rs1 != 2000000000 && md.rs[i].rs2 != 2000000000)
			md.rs[i].ready = true;
	}

	//writeResult end


}
int main()
{
	ASALU ASalu;
	MDALU MDalu;
	int RF[5] = { 2 ,2 ,4 ,6 ,8 };
	string RAT[5];
	map<string, string> m_RAT;
	m_RAT["1"] = RAT[0]; m_RAT["2"] = RAT[1]; m_RAT["3"] = RAT[2]; m_RAT["4"] = RAT[3]; m_RAT["5"] = RAT[4];  //方便直接修改 RAT
	map<string, int> m_RF;
	m_RF["1"] = RF[0]; m_RF["2"] = RF[1]; m_RF["3"] = RF[2]; m_RF["4"] = RF[3]; m_RF["5"] = RF[4];  //方便直接修改 RF
	ARS as;
	MRS md;
	queue<string> iq;
	string line;

	cout << "輸入instructions:" << endl;
	int insNum = 0;  //指令的數量

	while (getline(cin, line))
	{
		upToLow(line);
		iq.push(line);   //指令一行一行放進 iq
		insNum++;
	}

	int cycle = 1;

	do
	{
		issue_capture(iq, as, md, RAT, RF);
		dispatch(as, md, ASalu, MDalu);
		writeResult(as, md, ASalu, MDalu, m_RAT, m_RF, RAT, RF);

		if (ASalu.count != 0)
			ASalu.count--;
		if (MDalu.count != 0)
			MDalu.count--;

		cout << "Cycle " << cycle << endl << endl;

		cout << "  _RF__" << endl;
		cout << "F1" << "|  " << RF[0] << "|" << endl;
		cout << "F2" << "|  " << RF[1] << "|" << endl;
		cout << "F3" << "|  " << RF[2] << "|" << endl;
		cout << "F4" << "|  " << RF[3] << "|" << endl;
		cout << "F5" << "|  " << RF[4] << "|" << endl;
		cout << "----------" << endl << endl;

		cout << "  _RAT__" << endl;
		cout << "F1" << "|  " << RAT[0] << "|" << endl;
		cout << "F2" << "|  " << RAT[1] << "|" << endl;
		cout << "F3" << "|  " << RAT[2] << "|" << endl;
		cout << "F4" << "|  " << RAT[3] << "|" << endl;
		cout << "F5" << "|  " << RAT[4] << "|" << endl;
		cout << "----------" << endl << endl;

		cout << "  _RS___________________" << endl;

		cout << "RS1 |  " << as.rs[0].oprend << " |  ";		//RS1

		if (as.rs[0].preRs1 == "" && as.rs[0].oprend != "")
			cout << as.rs[0].rs1;
		else if (as.rs[0].preRs1 == "" && as.rs[0].oprend == "")
			cout << "";
		else
			cout << as.rs[0].preRs1;

		cout << "|  ";

		if (as.rs[0].preRs2 == "" && as.rs[0].oprend != "")
			cout << as.rs[0].rs2;
		else if (as.rs[0].preRs2 == "" && as.rs[0].oprend == "")
			cout << "";
		else
			cout << as.rs[0].preRs2;
		cout << "|";
		cout << endl;

		cout << "RS2 |  " << as.rs[1].oprend << " |  ";		//RS2

		if (as.rs[1].preRs1 == "" && as.rs[1].oprend != "")
			cout << as.rs[1].rs1;
		else if (as.rs[1].preRs1 == "" && as.rs[1].oprend == "")
			cout << "";
		else
			cout << as.rs[1].preRs1;

		cout << "|  ";

		if (as.rs[1].preRs2 == "" && as.rs[1].oprend != "")
			cout << as.rs[1].rs2;
		else if (as.rs[1].preRs2 == "" && as.rs[1].oprend == "")
			cout << "";
		else
			cout << as.rs[1].preRs2;
		cout << "|";
		cout << endl;

		cout << "RS3 |  " << as.rs[2].oprend << " |  ";		//RS3

		if (as.rs[2].preRs1 == "" && as.rs[2].oprend != "")
			cout << as.rs[2].rs1;
		else if (as.rs[2].preRs1 == "" && as.rs[2].oprend == "")
			cout << "";
		else
			cout << as.rs[2].preRs1;

		cout << "|  ";

		if (as.rs[2].preRs2 == "" && as.rs[2].oprend != "")
			cout << as.rs[2].rs2;
		else if (as.rs[2].preRs2 == "" && as.rs[2].oprend == "")
			cout << "";
		else
			cout << as.rs[2].preRs2;
		cout << "|" << endl;
		cout << "--------------------------" << endl;
		if (ASalu.count != 0)
			cout << "BUFFER: (" << ASalu.mrat << ")  " << ASalu.rs11 << " " << ASalu.op << " " << ASalu.rs22 << "   剩餘" << ASalu.count << "cycles";
		else
			cout << "empty";

		cout << endl << endl << endl;

		cout << "________________________" << endl;

		cout << "RS4 |  " << md.rs[0].oprend << " |  ";		//RS4

		if (md.rs[0].preRs1 == "" && md.rs[0].oprend != "")
			cout << md.rs[0].rs1;
		else if (md.rs[0].preRs1 == "" && md.rs[0].oprend == "")
			cout << "";
		else
			cout << md.rs[0].preRs1;

		cout << "|  ";

		if (md.rs[0].preRs2 == "" && md.rs[0].oprend != "")
			cout << md.rs[0].rs2;
		else if (md.rs[0].preRs2 == "" && md.rs[0].oprend == "")
			cout << "";
		else
			cout << md.rs[0].preRs2;
		cout << "|";
		cout << endl;

		cout << "RS5 |  " << md.rs[1].oprend << " |  ";		//RS5

		if (md.rs[1].preRs1 == "" && md.rs[1].oprend != "")
			cout << md.rs[1].rs1;
		else if (md.rs[1].preRs1 == "" && md.rs[1].oprend == "")
			cout << "";
		else
			cout << md.rs[1].preRs1;

		cout << "|  ";

		if (md.rs[1].preRs2 == "" && md.rs[1].oprend != "")
			cout << md.rs[1].rs2;
		else if (md.rs[1].preRs2 == "" && md.rs[1].oprend == "")
			cout << "";
		else
			cout << md.rs[1].preRs2;
		cout << "|";
		cout << endl;
		cout << "---------------------------" << endl;

		if (MDalu.count != 0)
			cout << "BUFFER: (" << MDalu.mrat << ")  " << MDalu.rs11 << " " << MDalu.op << " " << MDalu.rs22 << "   剩餘" << MDalu.count << "cycles" << endl;
		else
			cout << "empty" << endl;

		cycle++;
		system("pause");
		system("cls");
	} while (!iq.empty() || as.rs[0].oprend != "" || as.rs[1].oprend != "" || as.rs[2].oprend != "" || md.rs[0].oprend != "" || md.rs[1].oprend != "" || ASalu.count != 0 || MDalu.count != 0);

	cout << "Cycle " << cycle << endl << endl;
	dispatch(as, md, ASalu, MDalu);
	issue_capture(iq, as, md, RAT, RF);
	writeResult(as, md, ASalu, MDalu, m_RAT, m_RF, RAT, RF);
	cout << "  _RF__" << endl;
	cout << "F1" << "|  " << RF[0] << "|" << endl;
	cout << "F2" << "|  " << RF[1] << "|" << endl;
	cout << "F3" << "|  " << RF[2] << "|" << endl;
	cout << "F4" << "|  " << RF[3] << "|" << endl;
	cout << "F5" << "|  " << RF[4] << "|" << endl;
	cout << "----------" << endl << endl;

	cout << "  _RAT__" << endl;
	cout << "F1" << "|  " << RAT[0] << "|" << endl;
	cout << "F2" << "|  " << RAT[1] << "|" << endl;
	cout << "F3" << "|  " << RAT[2] << "|" << endl;
	cout << "F4" << "|  " << RAT[3] << "|" << endl;
	cout << "F5" << "|  " << RAT[4] << "|" << endl;
	cout << "----------" << endl << endl;

	cout << "  _RS___________________" << endl;

	cout << "RS1 |  " << as.rs[0].oprend << " |  ";		//RS1

	if (as.rs[0].preRs1 == "" && as.rs[0].oprend != "")
		cout << as.rs[0].rs1;
	else if (as.rs[0].preRs1 == "" && as.rs[0].oprend == "")
		cout << "";
	else
		cout << as.rs[0].preRs1;

	cout << "|  ";

	if (as.rs[0].preRs2 == "" && as.rs[0].oprend != "")
		cout << as.rs[0].rs2;
	else if (as.rs[0].preRs2 == "" && as.rs[0].oprend == "")
		cout << "";
	else
		cout << as.rs[0].preRs2;
	cout << "|";
	cout << endl;

	cout << "RS2 |  " << as.rs[1].oprend << " |  ";		//RS2

	if (as.rs[1].preRs1 == "" && as.rs[1].oprend != "")
		cout << as.rs[1].rs1;
	else if (as.rs[1].preRs1 == "" && as.rs[1].oprend == "")
		cout << "";
	else
		cout << as.rs[1].preRs1;

	cout << "|  ";

	if (as.rs[1].preRs2 == "" && as.rs[1].oprend != "")
		cout << as.rs[1].rs2;
	else if (as.rs[1].preRs2 == "" && as.rs[1].oprend == "")
		cout << "";
	else
		cout << as.rs[1].preRs2;
	cout << "|";
	cout << endl;

	cout << "RS3 |  " << as.rs[2].oprend << " |  ";		//RS3

	if (as.rs[2].preRs1 == "" && as.rs[2].oprend != "")
		cout << as.rs[2].rs1;
	else if (as.rs[2].preRs1 == "" && as.rs[2].oprend == "")
		cout << "";
	else
		cout << as.rs[2].preRs1;

	cout << "|  ";

	if (as.rs[2].preRs2 == "" && as.rs[2].oprend != "")
		cout << as.rs[2].rs2;
	else if (as.rs[2].preRs2 == "" && as.rs[2].oprend == "")
		cout << "";
	else
		cout << as.rs[2].preRs2;
	cout << "|" << endl;
	cout << "--------------------------" << endl;
	if (ASalu.count != 0)
		cout << "BUFFER: (" << ASalu.mrat << ")  " << ASalu.rs11 << " " << ASalu.op << " " << ASalu.rs22;
	else
		cout << "empty";
	cout << endl << endl << endl;

	cout << "________________________" << endl;

	cout << "RS4 |  " << md.rs[0].oprend << " |  ";		//RS4

	if (md.rs[0].preRs1 == "" && md.rs[0].oprend != "")
		cout << md.rs[0].rs1;
	else if (md.rs[0].preRs1 == "" && md.rs[0].oprend == "")
		cout << "";
	else
		cout << md.rs[1].preRs1;

	cout << "|  ";

	if (md.rs[0].preRs2 == "" && md.rs[0].oprend != "")
		cout << md.rs[0].rs2;
	else if (md.rs[0].preRs2 == "" && md.rs[0].oprend == "")
		cout << "";
	else
		cout << md.rs[0].preRs2;
	cout << "|";
	cout << endl;

	cout << "RS5 |  " << md.rs[1].oprend << " |  ";		//RS5

	if (md.rs[1].preRs1 == "" && md.rs[1].oprend != "")
		cout << md.rs[1].rs1;
	else if (md.rs[1].preRs1 == "" && md.rs[1].oprend == "")
		cout << "";
	else
		cout << md.rs[1].preRs1;

	cout << "|  ";

	if (md.rs[1].preRs2 == "" && md.rs[1].oprend != "")
		cout << md.rs[1].rs2;
	else if (md.rs[1].preRs2 == "" && md.rs[1].oprend == "")
		cout << "";
	else
		cout << md.rs[1].preRs2;
	cout << "|";
	cout << endl;
	cout << "---------------------------" << endl;
	if (MDalu.count != 0)
		cout << "BUFFER: (" << MDalu.mrat << ")  " << MDalu.rs11 << " " << MDalu.op << " " << MDalu.rs22 << endl;
	else
		cout << "empty" << endl;
	cycle++;
	system("pause");

}
```