char UpperCaseChar = (char)('A'-'a'+'z');
System.out.print(UpperCaseChar);
We then have a
System.out.println("c"+1+2+3); //output is c123
System.out.println('c'+1+2+3); //output is 105
System.out.println(1+2+3+"c"); //output is 6c
System.out.println(1+2+3+'c'); //output is 105
Notice the precedence of the computation. For the same level
operations, the computing is always from left to right. Therefore
java myprog "argument with space" second another
on the command line. Then
System.out.println("First input: " + arg[0]);
System.out.println("Second input: " + arg[1]);
System.out.println("Third input: " + arg[2]);
You will get the following output in your console window when you run your code:First input: argument with space Second input: second Third input: another
public class Euclidean2Polar {
public static void main(String[] args) {
double x = Double.parseDouble(args[0]);
double y = Double.parseDouble(args[1]);
double r = Math.sqrt(x*x + y*y);
double theta = Math.atan2(y, x) * 180 / Math.PI;
System.out.println("r = " + r);
System.out.println("theta = " + theta + " degrees");
}
}
This program can be used as a template for most of the problems in your
first assignment.
public class CosNaive {
public static void main (String[] args) {
double x = Double.parseDouble(args[0]);
int N = Integer.parseInt(args[1]);
double s = 1.0;
double t = -1;
double y = 0;
for (int i = 2; i <= N; i = i + 2) {
double p = 1.0;
for(int j = 1; j <= i; j ++)
p = p * x;
double q = 1.0;
for(int j = 1; j <= i; j ++)
q = q * j;
s = s + p / q * t;
t = -t;
}
System.out.println(s + " " + Math.cos(x));
}
}
The program takes too arguments: x and the number of iterations N.
The output of this program shows our result and the result using the system function Math.cos(x).
Try different x and N. You will find that as N becomes big this program becomes very slow.
Another big problem is that if x is greater than 1 and N is greater than some value,
the result becomes NaN!
This is because double variables p and q go out of range and become Infinity.
To solve the problem, we can merge the two inner loops together. The improved program is:
public class CosNaiveBetter {
public static void main (String[] args) {
double x = Double.parseDouble(args[0]);
int N = Integer.parseInt(args[1]);
double s = 1.0;
double t = -1;
double y = 0;
for (int i = 2; i <= N; i = i + 2) {
double p = 1.0;
for(int j = 1; j <= i; j ++)
p = p * x / j;
s = s + p * t;
t = -t;
}
System.out.println(s + " " + Math.cos(x));
}
}
Try different x and N and check the output and running speed. You will find that this program is much faster
than the previous one and we will not have the out-of-range problem. But
there are still many repetitive computations when we do the inner loop.
We can further improve the program
as
public class Cos {
public static void main (String[] args) {
double x = Double.parseDouble(args[0]);
int N = Integer.parseInt(args[1]);
double s = 1.0;
double v = -x * x / 2.0;
int i = 2;
while (i <= N) {
s = s + v;
v = -v * x * x / (i+1) / (i+2);
i += 2;
}
System.out.println(s + " " + Math.cos(x));
}
}
Now try some very large N and compare the running speed of this program with the improved naive version.
public class IsPrime {
public static void main (String[] args) {
int n = Integer.parseInt(args[0]);
boolean isPrime = true;
if (n == 1) isPrime = false;
for (int i = 2; i < n && isPrime; i++) {
if (n % i == 0)
isPrime = false;
}
System.out.println(isPrime);
}
}
The above program checks whether n has a factor that is in 2 to n-1. If it does, it must not be a prime number. In fact,
we can further improve the program by reducing the search range to [2, (int)Math.sqrt(n)]. One observation is
that there is at most one factor of n in the range [(int)Math.sqrt(n) + 1, n-1]. It is not hard to see that
(int)Math.sqrt(n) + 1 > Math.sqrt(n). Therefore, if n has two factors p and q in the range [(int)Math.sqrt(n) + 1, n-1], then
p * q must be greater than n which contradicts to the fact that p and q are factors of n (implies p * q <= n). We can further
conclude that if n is not prime, it must have a factor in the range [2, (int)Math.sqrt(n) + 1]. The improved program
is shown as follows:
public class IsPrime {
public static void main (String[] args) {
int n = Integer.parseInt(args[0]);
boolean isPrime = true;
if (n == 1) isPrime = false;
for (int i = 2; i <= (int) Math.sqrt(n) && isPrime; i++) {
if (n % i == 0)
isPrime = false;
}
System.out.println(isPrime);
}
}
public class Binary {
public static void main(String[] args) {
/*-----------------------------------------------------------
psedo-code version one:
input a number N
find the maximum power of 2 that is not greater than N
for each power of 2 that starts from the number above until it goes to 1
if the total sum is greater than N
output 0
else
output 1
include the current power of 2 to the whole sum
---------------------------------------------------------
psedo-code version two:
input a number N
v <= the maximum power of 2 that is not greater than N
s <= 0
for each m (power of 2) that is from v down to 1
if s + m > N
output 0
else
output 1
s <- s + m
----------------------------------------------------------*/
int N = Integer.parseInt(args[0]);
int v = 1;
while (v <= N/2)
v = v * 2;
int s = 0;
for(int m = v; m >= 1; m = m / 2) {
if (s + m > N)
System.out.print("0");
else {
System.out.print("1");
s = s + m;
}
}
}
}
The format of pseudo-code is not critical. You can choose whatever style you feel comfortable with.
The key is to write everything in your mind down on a paper or in an editor so that you can organize
your procedure into something
more and more similar to the final program.
public class RandomData {
public static void main(String[] args) {
int rows = Integer.parseInt(args[0]);
int cols = Integer.parseInt(args[1]);
StdOut.println(rows + " " + cols);
for (int i = 0; i < rows; i ++)
{
for (int j = 0; j < cols; j ++)
{
int r = (int)(1 + 100 * Math.random());
StdOut.printf("%-5d", r);
}
StdOut.println();
}
}
}
public class Cut {
public static void getColumn(int k, int rows, int cols) {
int count = 0;
StdOut.println(rows + " " + 1);
for (int i = 1; i <= rows; i ++)
for (int j = 1; j <= cols; j ++)
{
String s = StdIn.readString();
if (j == k)
StdOut.println(s);
}
}
public static void main(String[] args) {
int k = Integer.parseInt(args[0]);
int rows = StdIn.readInt();
int cols = StdIn.readInt();
getColume(k, rows, cols);
}
}
public class Plot {
public static void drawCurve() {
int rows = StdIn.readInt();
int cols = StdIn.readInt();
int N = rows;
if (cols > rows)
N = cols;
int width = 640;
int height = 480;
StdDraw.setCanvasSize(width, height);
StdDraw.setXscale(1, N);
StdDraw.setYscale(1, 100);
StdDraw.setPenColor(StdDraw.BLACK);
int py = 0;
for (int i = 1; i <= N; i++)
{
int cy = StdIn.readInt();
//StdOut.println(i + " " + cy);
StdDraw.point(i, cy);
if (i == 1) {
py = cy;
continue;
}
StdDraw.line(i - 1, py, i, cy);
py = cy;
}
}
public static void main(String[] args) {
drawCurve();
}
}
As shown in the class, the three programs can be connected in a pipeline to do data processing (in Unix):
java RandomData 10 10 | java Cut 5 | Java Plot
Here is the program we studied in class for removing white spaces in a string.
public class RemoveSpace {
public static String removeSpace(String s) {
if (s.equals(""))
return "";
if (s.charAt(0) == ' ')
return removeSpace(s.substring(1));
else
return s.charAt(0) + removeSpace(s.substring(1));
}
public static void main(String[] args) {
System.out.println(removeSpace(args[0]));
}
}
(1) Double each character in a string so that the length of the output string is twice as long.
(2) Reverse the sequence of a string.
(3) Replace specific character in a string with another one.
(4) Test whether a number is a power of 2.
(5) Print the base m reprentation of a number n.
Here is the slides we used in the class. You can find an illustration about how the calls are made in the recursive program for solving the problem of Towers of Hanoi. Some slides are from Prof. Sedgewick and Prof. Wayne.
Here is the code MazeSolver.java for solving a maze we talked about in the class. You can use the sample input maze.txt to test the program. To run the program in a terminal, type "java MazeSolver < maze.txt". Some functions in the program can be useful for your assignment five.
You can now download the codes for the moving balls balls.tar.gz and the enhanced maze walker maze.tar.gz. Pay attention to the difference of the object oriented version of the maze program to the procedure based one.
You can download today's class slides for linked data structures slides.ppt here. The partially finished List class in today's lecture is as follows. Try to add new methods such as "insert".
public class List {
private class Node {
Object d;
Node next;
public Node(Object d) {
this.d = d;
next = null;
}
public String toString() {
return d.toString();
}
}
Node head;
public List() {
head = null;
}
public void append(Object a) {
head = append(head, a);
}
public Node append(Node h, Object a) {
if (h == null) {
Node t = new Node(a);
return t;
}
h.next = append(h.next, a);
return h;
}
public void delete(int n) {
head = delete(head, n);
}
public Node delete(Node h, int n) {
if (h == null) return h;
if (n == 0) {
return h.next;
}
h.next = delete(h.next, n-1);
return h;
}
public void print()
{
Node t = head;
while ( t != null) {
System.out.print( t.d + " ");
t = t.next;
}
}
public static void main(String[] args) {
List list = new List();
list.append(new Integer(1));
list.append(new Integer(2));
list.append(new Integer(100));
list.print();
System.out.println();
list.delete(1);
list.print();
}
}