數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--隨機(jī)漫步-資料下載頁
2025-01-16 14:20本頁面
【正文】 //輸出蟑螂到過每一塊瓷磚的次數(shù) { for (int j=0。 jn。 j++) { cout setw(4)matrix[i][j]。 } cout endl。 } for (i=0。 im。 i++) //數(shù)組matrix delete[] matrix[i]。}四、 調(diào)試分析“隨機(jī)漫步”問題長久以來一直吸引著數(shù)學(xué)界的興趣，但即便是最簡單的隨機(jī)漫步問題，解決起來是極其困難，本課程設(shè)計(jì)只是一個(gè)模擬的隨機(jī)問題，所以技術(shù)含量并不高。一開始設(shè)計(jì)了一個(gè)使用隨機(jī)數(shù)的程序，運(yùn)行起來相當(dāng)?shù)穆?，要?jì)算一個(gè)15行15列矩陣的“隨機(jī)問題”需要運(yùn)行差不多二個(gè)小時(shí)，后來經(jīng)過改進(jìn)，才形成第一種程序，運(yùn)行速度非常的快。該程序設(shè)置進(jìn)行得比較順利，初始運(yùn)行時(shí)只有幾處小的錯(cuò)誤，改正后就能正常運(yùn)行了。五、 用戶手冊(cè) 本程序的運(yùn)行環(huán)境為DOS操作環(huán)境。本例演示程序簡單明了，按提示輸入即可。六、 時(shí)間復(fù)雜度和空間復(fù)雜度分析 時(shí)間復(fù)雜度分析：對(duì)于程序的第一種設(shè)計(jì)，是用函數(shù)劃分功能模塊的方式，將漫步問題的每個(gè)步驟劃分為一個(gè)個(gè)功能函數(shù)，然后調(diào)用這些函數(shù)來實(shí)現(xiàn)漫步過程。可以看到其中 cishu()函數(shù) midu()函數(shù) panduan()函數(shù) chuzhi()函數(shù)都有兩個(gè)for循環(huán)，每一個(gè)函數(shù)的時(shí)間復(fù)雜度為O（M）*O（N）。在 manbu()函數(shù)中有一個(gè)for循環(huán)，要循環(huán)50000次。最壞情況下其時(shí)間復(fù)雜度為：O（50000）。所以程序總的時(shí)間復(fù)雜度為：O（M）*O（N）*3＋O（50000）*O（M）*O（N）。對(duì)于程序的第二種設(shè)計(jì)，是在主函數(shù)中一并實(shí)現(xiàn)所有過程。沒有使用函數(shù)來封裝功能。它總共包含了九個(gè)for語句。第一個(gè)for語句的時(shí)間復(fù)雜度為O（M）。進(jìn)入第二個(gè)for之后為O（M）*O（N）。進(jìn)入第四個(gè)for語句之后的時(shí)間復(fù)雜度為：O（M*N）+O（50000M*N）*O（M）*O（N）。進(jìn)入第七個(gè)for的時(shí)間復(fù)雜度為：O（M）*O（N）。最后一個(gè)for：O（M）。因此，第二種程序總時(shí)間復(fù)雜度為：O（M）＋O（M）*O（N）+ O（M*N）+O（50000M*N）*O（M）*O（N）+ O（M）*O（N）+ O（M）。 空間復(fù)雜度分析：很明顯可以看出：第一種程序設(shè)計(jì)用的是一個(gè)固定大小的數(shù)組，而第二種程序設(shè)計(jì)用的是動(dòng)態(tài)分配數(shù)組。其他方面均相差不大，對(duì)于空間復(fù)雜度的問題，最主要的就在于一個(gè)動(dòng)態(tài)數(shù)組一個(gè)固定數(shù)組。動(dòng)態(tài)數(shù)組能按照實(shí)時(shí)需要來分配合適的內(nèi)存空間，而固定的數(shù)組則不能辦到。當(dāng)需要的數(shù)據(jù)小時(shí)，固定數(shù)組必然會(huì)浪費(fèi)大量的內(nèi)存空間；當(dāng)需要大量數(shù)據(jù)時(shí)，固定數(shù)組必然會(huì)出錯(cuò)，不能達(dá)到需要。故而，使用動(dòng)態(tài)數(shù)組能更好的滿足需要且節(jié)約大量的內(nèi)存空間，程序靈活性更大。七、 測(cè)試結(jié)果
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1