Java程序辅导

CSc 245 — Introduction to Discrete Structures
Fall 2021 (McCann)
http://u.arizona.edu/~mccann/classes/245
Homework #6
(50 points)
Due Date: November 12 th, 2021, at the beginning of class
Directions
1. This is an INDIVIDUAL assignment; do your own work! Submitting answers created by
other people is NOT doing your own work.
2. Start early! Getting help is much easier n days before the due date/time than it will be n hours before.
3. The questions that have section numbers are found in the Rosen text, available via D2L. Note that
“(w,z)” is asking you to complete parts w and z only, not parts x and y.
4. Write complete answers to each of the following questions, in accordance with the given directions. Create
your solutions as a PDF document such that each question is on a separate page; all parts of a multi–part
question may be on the same page. Show your work, when appropriate, for possible partial credit.
5. If you have questions about any aspect of this assignment, help is available from the class staff via
piazza.com and our office hours.
6. When your answers are ready to be turned in, do so on gradescope.com. Be sure to assign pages to
problems after you upload your PDF. Need help? Visit https://help.gradescope.com/ and search for
“Submitting an Assignment.”
7. Solutions submitted after the first five minutes of class on the due date will not be accepted.
Integer Divisibility:
1. (6 points) Section 4.1, 4
2. (2 points) Section 4.1, 14(b)
3. (2 points) Section 4.1, 34(a,b)
Primes / GCDs / LCMs:
4. (2 points) Section 4.3, 16(d)
5. (2 points) Section 4.3, 24(b)
6. (2 points) Section 4.3, 26(d)
Congruences:
7. (2 points) Section 4.5, 16. See p. 307.
8. (2 points) Section 4.5, 20(a). See note p. 309.
Sequences and Summations:
9. (2 points) Section 2.4, 2(c,d)
10. (4 points) Section 2.4, 6(b,f). Just 6 terms.
11. (4 points) Section 2.4, 26(b,f)
12. (2 points) Section 2.4, 34(c)
Cardinalities of Sets:
13. (2 points) Section 2.5, 2(e)
14. (2 points) Section 2.5, 4(c)
Java/Python Exercise:
15. (14 points) Program! (see back =⇒)
(Continued . . . )
Write a complete, well–documented Java 16 or Python 3 program (named Hmwk6.java or
hmwk6.py) that finds all possible 3 × 3 magic squares containing the integers 1 through
3 ∗ 3 = 9. For our purposes, a magic square is “magic” because the sums of all 3 rows, all 3
columns, and both diagonals are the same. A 3× 3 magic square is shown to the right.
8 1 6
3 5 7
4 9 2
The sums are all 15, which is known as the square’s magic constant. The magic constant can be computed in
advance of the square’s construction; it is n
3
+n
2
for an n× n magic square.
There are numerous ways to construct magic squares; here’s the one you are to use: In our text on page 459
is an algorithm that, given a sequence of values, computes the ‘next’ permutation (lexicographically speaking)
of that sequence. For example, the permutation 123 is immediately followed by 132; 123 < 132. Implement
this algorithm, and modify it so that it “wraps around” to the beginning when it is asked to generate the
permutation following the lexicographically largest. That is, when presented with a collection of integers
containing 321 as its three elements, it should return a collection containing 123. If you follow the algorithm
well enough to make that modification, great. That’s all you need to learn about how it works.
As there are many permutations possible, even for small squares, for this assignment we’ll settle for finding
only magic squares of size 3× 3. Write your program to generate all (3 ∗ 3)! = 362, 880 permutations and test
each to see if describes the content of a magic square. Assume that the square is to be filled with the permuted
values a row at a time, top–down and left to right. Thus, the permutation 816357492 produces the square
shown above.
Starting with a permutation of the values 1 – 9 entered by the user on the command line, your output is to
be (a) the first magic square you find in the permutation sequence generated from the input permutation, and
(b) the total quantity of magic squares found among all permutations. Just to be clear: The first permutation
your program is to consider is the one following the permutation entered by the user; the permutation entered
will be the last one considered. (And yes, your square should look at least reasonably like a square when it is
displayed to the screen. Minimally acceptable ‘square’: Three lines of output, one space between numbers on
each line; fancier is fine.) Treat rotations, mirror images, etc., as unique squares; count each separately.
Program Submission: After you have created your Java/Python program, submit your completed program
file(s) using the turnin command on lectura. The submission directory is cs245h6. Instructions are available
from the brief turnin tutorial linked to the class web page. (The same tutorial explains one way to get files from
your home PC to your CS account, should you need to.) Remember to name your source code file Hmwk6.java
or hmwk6.py so that we don’t have to guess which file to compile and execute.
Additional Info:
ˆ Create your program file with your editor of choice. To compile and execute a Java program on lectura
from a terminal window, use these commands:
Compile: javac Hmwk6.java
Execute: java Hmwk6 2 1 4 3 6 5 8 7 9 ← that’s a sample starting permutation
For Python 3: python3 hmwk6.py 2 1 4 3 6 5 8 7 9
ˆ Don’t know how to get information from the command line into your program? See CmdLine.java
and/or cmdline.py, which are linked to class web page.
ˆ Permutations will be covered in class in a few weeks; having you generate them seems like a good way
to expose you to the idea. The magic square is just a fun(?) use for the generated permutations.
ˆ What will we be looking for in the way of program documentation?
http://u.arizona.edu/~mccann/classes/style.html has links to a variety of pages dealing with my
documentation expectations.
Yes, I want “a lot” of documentation. Why? Because every programmer should include detailed, useful
documentation in any program. The documentation is worth about 25-30% of your possible program
score (in this case, 3 or 4 of 14 points).