Microsoft Word - Homework_1.2

Size: px

Start display at page:

Download "Microsoft Word - Homework_1.2"

仲简
7 years ago
Views:

1 資料結構與程式設計 (Data Structure and Programming) 100 學年上學期複選必修課程 Homework #1.2 (Due: 11:00pm, Oct 15, 2011) Department: Grade: Id: Name: 1. [Debugger] In your uncompressed hw1.2 directory, you should see a file permute-err.cpp. Change directory to hw1.2 and compile the cpp file by the command: g++ -g Wall o permute-err permute-err.cpp. You should get an executable file called permute-err. This program is supposed to generate all the permutations of a given number string and print them on the screen in the ascending order. Note that the maximum number of digits is 10 and we allow repeated digits. However, there is a bug in this program. You should be able to observe it by trying some number sequences. In this problem, you are asked to follow the steps in the subproblems below by using the debugging tool ddd. If you cannot find ddd, probably it is because you don t have it under your Linux machine. Try to download and install it, or talk to your system admin. If you are using remote Linux workstation by a SSH program, make sure you have set up X forwarding properly as we will need to display the graphical user interface (GUI) of ddd on your local machine. If in any case you still cannot get the debugger ddd in your Linux machine, you can try the non-graphical debugger, gdb. (a) Execute the program permute-err in the shell. When you see the prompted question, enter 3 for the number of digits and then enter 221 for the number string. What is the output? What is wrong? Now you should see the bug. Invoke the debugger by typing ddd permute-err. Follow the steps below and answer the questions. (b) The core permutation routine is the function PermuteNum::permute(int ibegin) (lines 93~116). As you can see, it is a recursive function and the permuted number string is printed in the base case (lines ). Let s first set a break point at line 102, which is a dummy cout after the end of each printing. You can set the break point by first clicking your mouse on that line and then click the Break icon on the tool bar. Or alternatively, you can evoke the command b 102 in the command window at the bottom of the debugger. 1

This program is supposed to generate all the permutations of a given number string and print them on the screen in the ascending order.

2 Now click on the run button or type in the command r. Enter the numbers as described in (a). What s the output you see on the command window? Which line does the program stop at? (c) Use mouse to highlight the data member _nums (note: you should also see the string _nums appearing on the upper left text box). Click on the Display icon on the tool bar, or type in the command graph display _nums (or display _nums for gdb). You should see the content of the array _nums on the display window. Adjust the display window properly so that you can at least see the first 3 elements of the array. What s the content of the array _nums? Are the numbers in the same order as you entered in (b)? Or are the numbers sorted? If the number is sorted, where in the source code are they sorted? (d) Now let s see how the base case is reached. Click or type in the command up. Where does now the program pointer stop? (e) Repeat the display command for variables idx and ibegin. You can drag the displays to the proper places for you to watch. What are the values of idx and ibegin? (Note: idx and ibegin refer to the indices of the array). (f) Click or type the command up again. You should see the program pointer stop at the same place. What are the values of the displays now? Are there any value changes? From steps (d) to (f), describe how the recursive function is called. (g) Now let s continue the program by clicking or typing the command continue. What s the output on the command window? What is the content of the array _nums? (h) Repeat Step (g). You should now see 3 number strings printed on the command window. They should complete all the permutations of the input number string, if the program is correct. That is, the program should terminate. However, it won t. Let s figure the cause. Click or type the command next until the program pointer goes back to line 111, that is, returning from the base case and then going back to the previous recursion in (g). What are the values of the displayed variables? Let s continue to click or type the command next again until you go up one level of recursion and stop at line 111. What are the values of the displayed variables? (i) Remember that your program should terminate. That is, if we continue executing the source code after line 111, you should NOT find a different digit and the value of the variable idx should become greater than or equal to _digit (3) so that the while loop (lines 108~115) can be broken. However, if you type next again, you will see that we do find a different digit with index idx = 2. Repeatedly type next and you will see the recursive function is called again. Continue until the break point. What are the values of the displayed variables? 2

Click on the Display icon on the tool bar, or type in the command graph display _nums (or display _nums for gdb). You should see the content of the array _nums on the display window.

3 (j) Now let s restart the program. Before that, please set a break point at the recursive function PermuteNum::permute. You can do it by highlighting PermuteNum::permute and then clicking on break, or by the command b PermuteNum::permute. Rerun the program by clicking or typing run. You can now use the commands continue and next to explore the program and figure out why it has the bug. (There is a hint below. If you don t want to see it, just continue to answer this subproblem. Otherwise, change the following white text to a visible color, or copy it to a pure text file.) (Hint) The bug is caused by forgetting to restore the array _nums at the end of the function (line 114). That is, because the recursive call may change the content (number order) of the array, after coming back from the recursive call and going out of the while loop in lines 107~114, you should restore the order of the numbers to that as before the recursive calls. Please fix the bug. Note that you are NOT allowed to modify or remove the existing lines. You should be able to fix the bug by adding some lines of codes. Describe your fix. [Note] For ease of grading, put your fixed program in a single file called hw1.2.p1.cpp. Answer the above subproblems in a text file called hw1.2.p1.txt. 2. This is a problem taken from National Problem Solving Contest on Internet (NPSC) 網際網路程式設計全國大賽 We will use this problem to guide you how to write an OOP program. [Problem Description] 瘋狂博士 X 是一個很龜毛的人, 他有很多奇怪的原則, 例如 : 不穿有兩顆釦子的衣服坐下來的時候不可以朝向東方下雨天不能坐公車喝黑咖啡要用深藍色的馬克杯, 如果是加糖的咖啡一定要用白色的咖啡杯裝著, 而且加糖的步驟一定要是先加 1 塊方糖攪拌 2 下加入 5 毫升的鮮奶再攪拌 7 下, 最後看他當天的心情決定要補加多少砂糖瑞特是瘋狂博士 X 的鄰居, 每個星期天下午會到瘋狂博士 X 家幫他整理家務瑞特的工作包括整理瘋狂博士 X 的小型圖書館, 最近瘋狂博士 X 買回家的書似乎有越來越多的趨勢, 他希望有人可以幫他寫一個有下列功能的程式 : 輸入瑞特手邊的書籍資料, 程式會自動輸出這些書籍的排序值得注意的是, 在瘋狂博士 X 的心中,AEIOU 五個母音的順序是 OAUIE, 而且 X 是 26 個字母之首 ; 所以對於瘋狂博士 X 而言, 英文字母的順序如下 : XOBCDAFGHUJKLMNIPQRSTEVWYZ 書籍擺放方式的規則 : 3

You can now use the commands continue and next to explore the program and figure out why it has the bug. (There is a hint below. If you don t want to see it, just continue to answer this subproblem.

4 i. 先按照作者的名字排序, ii. 作者相同的書籍再按照書籍問世的年份排序, iii. 如果作者出版年份都相同則按照書名排序千萬不要忘記這裡的順序是按照瘋狂博士 X 心目中的英文字母順序排列! [Problem Inputs] 總共只有一筆測試資料第一行有一個整數 N, 代表總共有幾本書籍資料, 至多 100 本書接下來共有 N 行, 每一行描述一本書籍, 格式為 : 書籍作者, 書籍名稱 ( 出版年份 ), 書籍作者和書籍名稱中間由一個逗點及一個空白字元分開書籍作者包括大小寫英文字母半形句點或空白字元, 至多 30 個字元書籍名稱包括大小寫英文字母或空白字元, 至多 100 個字元出版年份必定為四位數字本題的輸入測試檔案皆會符合上述要求, 不用考慮格式錯誤的問題, 也不用考慮會有多出來的空格 ( 如逗號之前多一個空格之類的 ) [Sample Inputs] 12 Erle Stanley Gardner, Drifting Down the Delta (1969) Agatha Christie, Five Little Pigs (1942) Erle Stanley Gardner, Host With the Big Hat (1969) J. R. R. Tolkien, Leaf by Niggle (1945) Agatha Christie, The Body in the Library (1942) Erle Stanley Gardner, The Case of the Murderers Bride (1969) Erle Stanley Gardner, The Case of the Stuttering Bishop (1937) J. R. R. Tolkien, The Hobbit (1937) J. R. R. Tolkien, The Lay of Aotrou and Itroun (1945) Agatha Christie, The Moving Finger (1942) Crazy Doctor X, AAA (2009) Crazy Doctor X, XXX (2009) [Problem Outputs] 排序後的書單, 按照瘋狂博士 X 心目中的英文字母順序排列與要求排序時同一字母的大小寫視為相等, 但輸出資料的大小寫必須和輸入資料一致空白字元的順序較英文字母為先半形句點的順序在空白字元和英文字母之間總共有 N 行輸出, 格式為書籍作者, 書籍名稱 ( 出版年份 ), 與輸入格式相同 [Sample Outputs] 4

個空白字元分開書籍作者包括大小寫英文字母半形句點或空白字元, 至多 30 個字元書籍名稱包括大小寫英文字母或空白字元, 至多 100 個字元出版年份必定為四位數字本題的輸入測試檔案皆會符合上述要求, 不用考慮格式錯誤的問

5 Crazy Doctor X, XXX (2009) Crazy Doctor X, AAA (2009) Agatha Christie, Five Little Pigs (1942) Agatha Christie, The Body in the Library (1942) Agatha Christie, The Moving Finger (1942) J. R. R. Tolkien, The Hobbit (1937) J. R. R. Tolkien, Leaf by Niggle (1945) J. R. R. Tolkien, The Lay of Aotrou and Itroun (1945) Erle Stanley Gardner, The Case of the Stuttering Bishop (1937) Erle Stanley Gardner, Drifting Down the Delta (1969) Erle Stanley Gardner, Host With the Big Hat (1969) Erle Stanley Gardner, The Case of the Murderers Bride (1969) Complete the TODO s of the following sub-problems. (a) (Operator overloading) The program hw1.2.p2a.cpp defines a class xstr that takes a char string and converts it to a new upper-case string with the alphabetic order in Crazy Doc s mind. For example, the string XO will be converted to AB, and dog will be converted to EBH. This is to facilitate the comparison of strings using the existing string comparison functions. A sample input/output is: Type Ctrl-C to terminate the program... First string : Test Crazy Doc's : UVTU Enter a string: dog Crazy Doc's : EBH >> dog is smaller than Test >> dog is not equal to Test Enter a string: abc Crazy Doc's : FCD >> abc is not smaller than dog >> abc is not equal to dog Enter a string: ha123 Crazy Doc's : IF123 >> ha123 is not smaller than abc >> ha123 is not equal to abc (b) ( string manipulation) The program hw1.2.p2b.cpp defines a class Book that records the book information with the author (_author) and book (_book) names in class xstr, and the year. You should overload the operator < by following Crazy Doc s rules in sorting books. The input file hw1.2.p2b.in is provided, and your generated output file hw1.2.p2b.out should match the sample outputs above. 5

6 3. For the following SelectionSort function, void selectionsort(vector<int>& array) { for (size_t i = 0, n = array.size(); i < n - 1; ++i) { size_t pivot = i; for (size_t j = i+1; j < n; ++j) { if (!compare(array[pivot], array[j])) pivot = j; } if (pivot!= i) myswap(array[pivot], array[i]); } } (a) Implement the main() function so that the program can ask the user to input a sequence of numbers and store them in an array. The above function SelectionSort() will then be called by main() to sort the numbers in ascending order. Please also implement the functions compare() and myswap() as called in SelectionSort(). However, please DO NOT change the code in SelectionSort(). The following is a sample output: How many numbers? After sort: For ease of grading, put your code in a single file called hw1.2.p3a.cpp. (b) Change the compare() function into a functional object argument for the selectionsort() function. That is, the function prototype will be: void selectionsort (vector<int>& array, const Compare& compare); Please create another two functional object classes, Less and Greater, which inherit the class Compare. Therefore, in main(), if we pass in a functional object of type Less (i.e. calling selectionsort(arr, Less()) ), the numbers will be sorted in ascending order. On the contrary, the function object of type Greater will sort the numbers in descending order. Please make the base functional object class Compare a virtual class. That is, make its operator () a pure virtual function. Sort the numbers in main() in both ascending and descending order. A sample output is as follows: How many numbers?

= i) myswap(array[pivot], array[i]); } } (a) Implement the main() function so that the program can ask the user to input a sequence of numbers and store them in an array.

7 Ascending sort: Descending sort: For ease of grading, put your code in a single file called hw1.2.p3b.cpp. (c) Modify the functions into template functions. That is, the selectionsort will not only be able to sort integers, but any data type as long as its operator < and operator > are defined. In other words, the function prototype of selectionsort() will be: template <class T> void selectionsort (vector<t>& array, const Compare<T>& compare); In your main(), sort a sequence of strings in ascending order, and a sequence of doubles in descending order. A sample output is as follows: How many strings? 5 hello ric what is up hello ric what is up Ascending sort: hello is ric up what How many doubles? Descending sort: For ease of grading, put your code in a single file called hw1.2.p3c.cpp. Notes: Please pay attention to the homework rules on the website. Failure to abide by the rules may result in deduction in homework points. 7

In other words, the function prototype of selectionsort() will be: template <class T> void selectionsort (vector<t>& array, const Compare<T>& compare); In your main(), sort a sequence of strings in

Windows XP

Windows XP What is Windows XP Windows is an Operating System An Operating System is the program that controls the hardware of your computer, and gives you an interface that allows you and other programs