【CSC 3002 分析】CSC 3002 (Spring 2021) Assignment 4
Problem 1
If you search the web for fractal designs, you will find many intricate wonders beyond the Koch
snowflake illustrated in this chapter. H-fractal, in which the repeated pattern is shaped like an
elongated letter H in which the horizontal bar and vertical lines on the sides have the same length.
Thus, the order-0 H-fractal looks like this:
To create the order-1 fractal, all you do is add four new H-fractalseach one half of the original
sizeat each open end of the order-0 fractal, like this:
To create the order-2 fractal, all you have to do is add even smaller H-fractals (again half the
size of the fractal to which they connect) to each of the open endpoints. This process gives rise to
the following order-2 fractal:
Write a recursive function
where x and y are the coordinates of the center of the H-fractal, size specifies the width and
the height, and order indicates the order of the fractal. As an example, the main program
would draw an order-3 H-fractal at the center of the graphics window, like this:
Requirments & Hints:
Please fill in the TODO part of the function drawHFractal() in P1HFractal.cpp.
Problem 2
The game of tic-tac-toe is played by two players who take turns placing Xs and Os in a 3 × 3
grid that looks like this:
The object of the game is to line up three of your own symbols in a row, horizontally, vertically,
or diagonally. In the following game, for example, X has won the game by completing three in a
row across the top:
If the board fills up without anyone completing a row, the game is a draw, which is called a cats
game in tic-tac-toe. Write a program that uses the minimax algorithm to play a perfect game of
tic-tac-toe. Figure shows a sample run against a particularly inept player.
Requirments & Hints:
Please fill in the TODO part of the functions in P2TicTacToe.cpp.
Problem 3
Rewrite the implementation of the merge sort algorithm from Figure 10-3 so that it sorts an
array rather than a vector. As in the reimplementation of the selection sort algorithm on page 499,
your function should use the prototype
Requirments & Hints: Do not use other sort algorithms! Do not modify the header file and
the implementation should be in the .cpp file. We will check your implementation and make sure
it uses exactly the merge and sort strategy.
Please fill in the TODO part of function sort() in P3MergeSort.cpp.
Problem 4
Implement the EditorBuffer class using the strategy described in the section entitled Doubly
linked lists (Page 606). Be sure to test your implementation as thoroughly as you can. In particular,
make sure that you can move the cursor in both directions across parts of the buffer where you
have recently made insertions and deletions.
In this implementation, the ends of the linked list are joined to form a ring, with the dummy
cell at both the beginning and the end. This representation makes it possible to implement the
moveCursorToEnd method in constant time, and reduces the number of special cases in the
code. The constructor is already given. Methods need to be implemented:
? The destructor that delete all cells
? Methods move the cursor
? A insertCharacter method that inserts one character into the buffer on the cursor
? A deleteCharacter method that deletes one character after the cursor
? A getText method that returns the content in buffer
? A getCursor method that returns the index of the cursor
Implement the EditorBuffer class using this representation (which is, in fact, the design strategy
used in many editors today). Make sure that your program continues to have the same
computational efficiency as the two-stack implementation in the text and that the buffer space
expands dynamically as needed.
Requirments & Hints:
Please fill in the TODO part of the methods in buffer.cpp.
Requirements for Assignment 4
I’ve provided a project named as Assignment4.pro. You should write TODO part in each .cpp
file according to the problem requirements. Finally, please pack your whole project files into a
single .zip file, name it using your student ID (e.g. if your student ID is 123456, hereby the file
should be named as 123456. zip ), and then submit the .zip file via BB system. The zip file should
be less than 8 MB.
Please note that, the teaching assistant may ask you to explain the meaning of your program, to
ensure that the codes are indeed written by yourself. Please also note that we may check whether
your program is too similar to your fellow students’ code using BB.
Please refer to the BB system for the assignment deadline April 18, 2021. For each day of late
submission, you will obtain late penalty in the assignment marks. If you submit more than 3 days
later than the deadline, you will receive 0 in this assignment.
Marking scheme:
? 1.5 + 3.5 + 1.5 + 3.5 = 10 grades for each problem and the whole Assignment 4
? 25% Marks will be given to students who have submitted the program on time.
? 25% Marks will be given to students who wrote the program that meet all the requirements
of the questions
? 25% Marks will be given to students who programs that can be compiled without errors.
? 25% Marks will be given to students whose programs produce the correct output if their
programs can be compiled.
Reminder: For windows users, please switch your input language to English before interacting
in Stanford console. Or, you will get no response.
推荐阅读
- Java|社招和校招有什么不同（阿里美团等大厂 JAVA 社招面经分享）
- Webapp和后端交互检查测试
- 数据库开发|通过栗子来学习MySQL高级知识点（学习，复习，面试都可）
- 程序员|redis常见数据结构以及使用场景分析，附面试题答案
- 程序员|备战三个月，Redis面试复习大纲在手面试不慌
- C++|【C++】类和对象（一）
- Java每日一练|Java基础每日一练—第8天（判断大小）
- JavaSE系列详解|新星计划day4【Java语言IO流】缓冲流的详解
- Java每日一练|Java基础每日一练—第7天（最优选择）