推 buefox:推小光認真 03/08 12:01
推 weareworld: 03/15 01:00
推 BoyoChen:推卷哥 03/18 00:14
不要作弊!(上一份翻過了，請詳讀)
作業200 分，另外加上10分加分題。
2.1 更多C++
(1) 下列函數會找到一個陣列中的最大元素和最小元素。
這個函數需要這要呼叫:
請把它改寫成可以這樣呼叫的形式:
(提示: reference!)
(2) 下面的函數sum1可能會跑一跑當掉，請說明原因。sum2不會跑一跑當掉，但是它會有
別的問題，請說明他的問題。
2.2 更多陣列
(1) 完成課本上C-3.3練習題。(越快越好喔)
(2) 完成課本上C-3.4練習題。(越快越好喔)
(3) 一個大小為N的帕斯卡三角形包含了所有C n取k(0<=k<=n<=N)的數值。請說明你要如
何用一個一為陣列來儲存這一個三角形的資料。你必須說明他們記憶體上分布的情況以及
取出任一C n取k的數值的方法。
(4) 承上題，你有沒辦法利用”C n取 k== C n取 n-k”這點想到另外一個方法可以只用
一半的記憶體儲存這一個三角形的方法? 你仍必須說明他們記憶體上分布的情況以及取出
任一C n取k的數值的方法。
2.3 多維陣列處理
你現在被要求要設計並實作一個資料結構來儲存來自2011 KDDCup Track1的一個很大的
資料組。KDDCup是一個國際Data Mining的比賽，而我們親愛的NTU隊伍贏得了當年的雙料
冠軍。這個檔案總共有252800275行。
在二一七linux 1~14都有。檔案格式為:
這個資料組來自Yahoo! 音樂 評價系統。每行代表使用者(User ID)在何日(Date)何時
(Time)給予一首歌(ItemID)的分數(Rating)。 你可以將檔案視為一個超大的4D陣列
M[UserID][ItemId][Date][Time]=rating。
你的設計必須包含下列功能:
. 取得: 給予使用者、音樂名稱、時間、日期時輸出分數。
. 項目: 逐行輸出u1,u2都給過評分的音樂名稱。
. 使用者: 按照(號嗎?)順序逐行輸出在[(d1,t1),(d2,t2)]這段時間內給過i1,i2評價的
使用者。
. 社團: 按照順序逐行輸出給予資料組Is中的音樂r1~r2分的使用者。
TA會提供要求的輸入輸出格式，你必須按照這些格式讓TA可以用他們的輸入、輸出檔案測
試你的程式。在下列問題中，你可以用標準函式庫中的任何功能。
這個作業的目的是要幫助你了解為龐大的資料設計資料結構是一件不容易的事。我們了解
你現在還不會很多招。所以請你盡力想出任何東西。我們鼓勵你發揮創意。
(1) 形容你設計的資料結構。把重點擺在你為什麼覺得你設計的資料結構在處理以上五個
命令時(在時間方面)是很有效率的。
(2) 請計算把這些資料讀進你的資料結構需要花多少時間(越快越好)。
(3) 請計算你的資料結構實際占據的記憶體大小。(越小越好)
(4) 請實作你設計的資料結構(包含輸入輸出界面)，並能執行上述的五個命令。並簡略說
明你如何測試你得實作是否正確。再來，寫一個Makefile來編譯你的code。TA會用make來
編譯你得程式，並用make run 在217工作站執行。
請按照以下格式上傳你的code。不能在217工作站上編譯執行的的程式都會算0分。
上傳學號.zip，包含你的實作 .h .cpp，Makefile，還有選擇性的README(給助教看的一
封小信)。
手寫部分，請印出來，並在課堂上繳交，或是交到217。
金牌使用方法:在手寫的作業封面上寫你要用幾面。ex. use 2 metals。
傳說一次用三面金牌可以召喚岳大將軍，用四面金牌可以召喚田神。但洽p詳細功能不甜n楚﹜d
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.164.17.45