辅导data留学生、讲解c/c++语言、辅导Python，Java程序设计 讲解留学生Prolog|辅导留学生 Statistics统计、回归、迭代
- 首页 >> C/C++编程 You must choose 2 topics to finish, respectively one
from 1-4, the other from 5-8. Project 1: 24-point game
Problem Description:
The 24-point game is to pick any four cards from 52 cards, as shown in the figure below. Note that two
Jokers are excluded. Each card represents a number. An Ace, King, Queen, and Jack represent 1, 13, 12, and 11, respectively. Enter an expression that uses the four numbers from the four selected cards. Each
number must be used once and only once. You can use the operators (addition, subtraction, multiplication, and division) and parentheses in the expression. The expression must evaluate to 24. After entering the expression, click the Verify button to check whether the numbers in the expression
are currently selected and whether the result of the expression is correct. Display the verification in a
dialog box. Note that such an expression might not exist. In this case, click the Refresh button to get
another set of four cards. Assume that images are stored in files named 1.png, 2.png, ..., 52.png, in the
order of spades, hearts, diamonds, and clubs. So, the first 13 images are for spades 1, 2, 3, ..., and 13.
Figure 1 24-point game
Your program should also enable the computer to display the expression if one exists, as shown in the
figure. Otherwise, report that the expression does not exist. Project 2: Baby name popularity ranking
Problem Description:
The Popularity ranking of baby names from years 2001 to 2010 is downloaded form www.ssa. gov/oact/babynames and stored in files names babynamerankong2001.txt, babynameranking2002.t
xt, ... , babynameranking2010.txt. Write a program that enables the user to select a year, gende
r, and enter a name to display the ranking of the name for the selected year and gender, as s
hown in the following figure. To achieve the best efficiency, create two arrays for boy’s name
s and girl’s names, respectively. Each array has 10 elements for 10 years. Each element is a
map that stores a name and its ranking in a pair with the name as the key.
Figure 2.1 The user selects a year, gender, and enters a year and clicks the Find Ranking button
to display the ranking in a dialog box. Project 3: Convex Hull
Problem Description:
Given a set of points, a convex hull is a smallest convex polygon that encloses all these points, as
shown in Figure 3.1a. A polygon is convex if every line connecting two vertices is inside the polygon. For example, the vertices v0, v1, v2, v3, v4, and v5 in Figure 3.1a form a convex polygon, but not in
Figure 3.1b, because the line that connects v3 and v1 is not inside the polygon.
v5 (a) A convex hull (b) A non-convex polygon (c) convex hull animation Figure 3.1 A convex hull is a smallest convex polygon that contains
a set of points. Convex hull has many applications in game programming, pattern recognition, and image processing. Before we introduce the algorithms, it is helpful to get acquainted with the concept using an interactive
tool from liveexample.pearsoncmg.com/dsanimation/ConvexHull.html, as shown in Figure 3.1c. The
tool allows you to add/remove points and displays the convex hull dynamically. Many algorithms have been developed to find a convex hull. An intuitive approach, called the
gift-wrapping algorithm, works as follows:
Step 1: Given a list of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest
point h0 in S. As shown in Figure 3.2a, h0 is such a point. Add h0 to the convex hull H. H is a list
initially being empty. Let t0 be h0. Step 2: Let t1 be s0. For every point p in S
if p is on the right side of the direct line from t0 to t1 then
let t1 be p. (After Step 2, no points lie on the right side of the direct line from t0 to t1, as shown in Figure 3.2b.)
Step 3: If t1 is h0 (see Figure 3.2d), the points in H form a convex hull for S. Otherwise, add t1 to H, let
t0 be t1, and go to Step 2 (see Figure 3.2c).
t0 t1 = h0 (a) Step 1 (b) Step 2 (c) repeat Step 2 (d) H is found
Figure 3.2 (a) h0 is the rightmost lowest point in S. (b) Step 2 finds
point t1. (c) A convex hull is expanded repeatedly. (d) A convex hull
is found when t1 becomes h0. Project 4: Execution time for Sorting
Problem Description:
Write a program that obtains the execution time of selection sort, radix sort, bubble sort, merge
sort, quick sort, and heap sort for input size 50000, 100,000, 150,000, 200,000, 250,000, and
300,000. Your program should create data randomly and print a table like this:
Selection Sort Radix Sort Bubble Sort Merge Sort Quick Sort Heap Sort
50000
In the same program, obtain the execution time of selection sort, radix sort, bubble sort, and heap
sort for input size 2,000,000, 3,000,000, 4,000,000, and 5,000,000. Project 5: Data Compression
Problem Description:
Huffman codng compresses data by using fewer bits to encode characters that occur more
frequently. The codes for the characters are constructed based on the occurrence of the characters
in the text using a binary tree, called the Huffman coding tree. Suppose the text is “Mississipi”, Its Huffman tree is as shown in Figure 5.1a. The left and right
edges of a node are assigned the values 0 and 1, respectively. Each character is a leaf in the tree. The code for character consists of the edge values in the path from the root to the leaf, as shown in
Figure 5.2b.
Figure 5.1 The codes for characters are constructed based on the
occurrence of characters in the text using a coding tree.
(1) Write a program that prompts the user to enter a file name, obtains the Huffman codes for the
characters in the file, and encodes the text into a new file. For example, if the original file is
named abc.txt, the encoded file should be named as abc.txt.new. (2) Write a program that decompresses the file created in (1). The program prompts the user to
enter two file names. The first one is the source and the second one is the target. The program
decompresses the source into the target. Here is a sample run:
from 1-4, the other from 5-8. Project 1: 24-point game
Problem Description:
The 24-point game is to pick any four cards from 52 cards, as shown in the figure below. Note that two
Jokers are excluded. Each card represents a number. An Ace, King, Queen, and Jack represent 1, 13, 12, and 11, respectively. Enter an expression that uses the four numbers from the four selected cards. Each
number must be used once and only once. You can use the operators (addition, subtraction, multiplication, and division) and parentheses in the expression. The expression must evaluate to 24. After entering the expression, click the Verify button to check whether the numbers in the expression
are currently selected and whether the result of the expression is correct. Display the verification in a
dialog box. Note that such an expression might not exist. In this case, click the Refresh button to get
another set of four cards. Assume that images are stored in files named 1.png, 2.png, ..., 52.png, in the
order of spades, hearts, diamonds, and clubs. So, the first 13 images are for spades 1, 2, 3, ..., and 13.
Figure 1 24-point game
Your program should also enable the computer to display the expression if one exists, as shown in the
figure. Otherwise, report that the expression does not exist. Project 2: Baby name popularity ranking
Problem Description:
The Popularity ranking of baby names from years 2001 to 2010 is downloaded form www.ssa. gov/oact/babynames and stored in files names babynamerankong2001.txt, babynameranking2002.t
xt, ... , babynameranking2010.txt. Write a program that enables the user to select a year, gende
r, and enter a name to display the ranking of the name for the selected year and gender, as s
hown in the following figure. To achieve the best efficiency, create two arrays for boy’s name
s and girl’s names, respectively. Each array has 10 elements for 10 years. Each element is a
map that stores a name and its ranking in a pair with the name as the key.
Figure 2.1 The user selects a year, gender, and enters a year and clicks the Find Ranking button
to display the ranking in a dialog box. Project 3: Convex Hull
Problem Description:
Given a set of points, a convex hull is a smallest convex polygon that encloses all these points, as
shown in Figure 3.1a. A polygon is convex if every line connecting two vertices is inside the polygon. For example, the vertices v0, v1, v2, v3, v4, and v5 in Figure 3.1a form a convex polygon, but not in
Figure 3.1b, because the line that connects v3 and v1 is not inside the polygon.
v5 (a) A convex hull (b) A non-convex polygon (c) convex hull animation Figure 3.1 A convex hull is a smallest convex polygon that contains
a set of points. Convex hull has many applications in game programming, pattern recognition, and image processing. Before we introduce the algorithms, it is helpful to get acquainted with the concept using an interactive
tool from liveexample.pearsoncmg.com/dsanimation/ConvexHull.html, as shown in Figure 3.1c. The
tool allows you to add/remove points and displays the convex hull dynamically. Many algorithms have been developed to find a convex hull. An intuitive approach, called the
gift-wrapping algorithm, works as follows:
Step 1: Given a list of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest
point h0 in S. As shown in Figure 3.2a, h0 is such a point. Add h0 to the convex hull H. H is a list
initially being empty. Let t0 be h0. Step 2: Let t1 be s0. For every point p in S
if p is on the right side of the direct line from t0 to t1 then
let t1 be p. (After Step 2, no points lie on the right side of the direct line from t0 to t1, as shown in Figure 3.2b.)
Step 3: If t1 is h0 (see Figure 3.2d), the points in H form a convex hull for S. Otherwise, add t1 to H, let
t0 be t1, and go to Step 2 (see Figure 3.2c).
t0 t1 = h0 (a) Step 1 (b) Step 2 (c) repeat Step 2 (d) H is found
Figure 3.2 (a) h0 is the rightmost lowest point in S. (b) Step 2 finds
point t1. (c) A convex hull is expanded repeatedly. (d) A convex hull
is found when t1 becomes h0. Project 4: Execution time for Sorting
Problem Description:
Write a program that obtains the execution time of selection sort, radix sort, bubble sort, merge
sort, quick sort, and heap sort for input size 50000, 100,000, 150,000, 200,000, 250,000, and
300,000. Your program should create data randomly and print a table like this:
Selection Sort Radix Sort Bubble Sort Merge Sort Quick Sort Heap Sort
50000
In the same program, obtain the execution time of selection sort, radix sort, bubble sort, and heap
sort for input size 2,000,000, 3,000,000, 4,000,000, and 5,000,000. Project 5: Data Compression
Problem Description:
Huffman codng compresses data by using fewer bits to encode characters that occur more
frequently. The codes for the characters are constructed based on the occurrence of the characters
in the text using a binary tree, called the Huffman coding tree. Suppose the text is “Mississipi”, Its Huffman tree is as shown in Figure 5.1a. The left and right
edges of a node are assigned the values 0 and 1, respectively. Each character is a leaf in the tree. The code for character consists of the edge values in the path from the root to the leaf, as shown in
Figure 5.2b.
Figure 5.1 The codes for characters are constructed based on the
occurrence of characters in the text using a coding tree.
(1) Write a program that prompts the user to enter a file name, obtains the Huffman codes for the
characters in the file, and encodes the text into a new file. For example, if the original file is
named abc.txt, the encoded file should be named as abc.txt.new. (2) Write a program that decompresses the file created in (1). The program prompts the user to
enter two file names. The first one is the source and the second one is the target. The program
decompresses the source into the target. Here is a sample run: