√Recreation
Prove that ⌊(2 + 3)n⌋ is odd for all integer n ≥ 0.
[Source: D. O. Shklarsky, N. N. Chentzov, I. M. Yaglom, The USSR Olympiad Problem Book, Dover ed. (1993), from the W. H. Freeman edition, 1962.]
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 1
Copyright By PowCoder代写 加微信 powcoder
CS61B Lecture #3: Values and Containers
• Labs are normally due at midnight Friday. Last week’s is due tonight. • Today. Simple classes. Scheme-like lists. Destructive vs. non-
destructive operations. Models of memory.
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 2
Values and Containers
• Values are numbers, booleans, and pointers. Values never change. 3 ’a’ true
• Simple containers contain values:
Examples: variables, fields, individual array elements, parameters.
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 3
Alternative Notation
Class Object
Array Object
012 42 17 9
Empty Object
Last modified: Wed Jan 29 13:26:29 2020
CS61B: Lecture #3 4
Structured Containers
Structured containers contain (0 or more) other containers:
• Pointers (or references) are values that reference (point to) con- tainers.
• One particular pointer, called null, points to nothing.
• In Java, structured containers contain only simple containers, but pointers allow us to build arbitrarily big or complex structures any- way.
Last modified: Wed Jan 29 13:26:29 2020
CS61B: Lecture #3 5
Containers in Java
• Containers may be named or anonymous.
• In Java, all simple containers are named, all structured contain- ers are anonymous, and pointers point only to structured containers. (Therefore, structured containers contain only simple containers).
simple container (local variable)
named simple containers (fields) within structured containers
structured containers (anonymous)
• In Java, assignment copies values into simple containers.
• Exactly like Scheme and Python!
• (Python also has slice assignment, as in x[3:7]=…, which is short- hand for something else entirely.)
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 6
Defining New Types of Object
• Class declarations introduce new types of objects. • Example: list of integers:
public class IntList {
// Constructor function (used to initialize new object) /** List cell containing (HEAD, TAIL). */
public IntList(int head, IntList tail) {
this.head = head; this.tail = tail; }
// Names of simple containers (fields)
// WARNING: public instance variables usually bad style! public int head;
public IntList tail;
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 7
IntList Q, L;
L: 3 42 Q:
L: 3 43 Q:
L = new IntList(3, null); Q = L;
Q = new IntList(42, null); L.tail = Q;
L.tail.head += 1;
// Now Q.head == 43
// and L.tail.head == 43
Primitive Operations
Last modified: Wed Jan 29 13:26:29 2020
CS61B: Lecture #3 8
Side Excursion: Another Way to View Pointers
• Some folks find the idea of “copying an arrow” somewhat odd.
• Alternative view: think of a pointer as a label , like a street address.
• Each object has a permanent label on it, like the address plaque on a house.
• Then a variable containing a pointer is like a scrap of paper with a street address written on it.
• One view:
• Alternative view: last:
result: Last modified: Wed Jan 29 13:26:29 2020
CS61B: Lecture #3 9
Another Way to View Pointers (II)
• Assigning a pointer to a variable looks just like assigning an integer to a variable.
• So, after executing “last = last.tail;” we have last:
• Alternative view: last:
• Under alternative view, you might be less inclined to think that as- signment would change object #7 itself, rather than just “last”.
• BEWARE! Internally, pointers really are just numbers, but Java treats them as more than that: they have types, and you can’t just change integers into pointers.
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 10
Destructive vs. Non-destructive
Problem: Given a (pointer to a) list of integers, L, and an integer in- crement n, return a list created by incrementing all elements of the list by n.
/** List of all items in P incremented by n. Does not modify * existing IntLists. */
static IntList incrList(IntList P, int n) {
return /*( P, with each element incremented by n )*/
We say incrList is non-destructive, because it leaves the input objects unchanged, as shown on the left. A destructive method may modify the input objects, so that the original data is no longer available, as shown on the right:
After Q = incrList(L, 2): L: 3 43
Q: 5 45 Last modified: Wed Jan 29 13:26:29 2020
After Q = dincrList(L, 2) (destructive): L: 5 45
CS61B: Lecture #3 11
Nondestructive IncrList: Recursive
/** List of all items in P incremented by n. */
static IntList incrList(IntList P, int n) { if (P == null)
return null;
else return new IntList(P.head+n, incrList(P.tail, n));
• Why does incrList have to return its result, rather than just set-
• In the call incrList(P, 2), where P contains 3 and 43, which IntList
object gets created first?
Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 12
static IntList incrList(IntList P, int n) { if (P == null) <<< return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; = new IntList(P.head+n, null); last = last.tail; }return result; } An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 13 static IntList incrList(IntList P, int n) { if (P == null) return null; IntList result, last; result = last <<< = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; = new IntList(P.head+n, null); last = last.tail; }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 14 static IntList incrList(IntList P, int n) { if (P == null) return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; <<< last.tail = new IntList(P.head+n, null); last = last.tail; }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 15 return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; last.tail <<< = new IntList(P.head+n, null); last = last.tail; }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: static IntList incrList(IntList P, int n) { if (P == null) Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 16 return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; = new IntList(P.head+n, null); last = last.tail; <<< }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: static IntList incrList(IntList P, int n) { if (P == null) Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 17 return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; <<< last.tail = new IntList(P.head+n, null); last = last.tail; }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: static IntList incrList(IntList P, int n) { if (P == null) Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 18 return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; last.tail <<< = new IntList(P.head+n, null); last = last.tail; }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: static IntList incrList(IntList P, int n) { if (P == null) Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 return null; IntList result, last; result = last = new IntList(P.head+n, null); while (P.tail != null) { P = P.tail; = new IntList(P.head+n, null); last = last.tail; <<< }return result; } P: last: result: An Iterative Version An iterative incrList is tricky, because it is not tail recursive. Easier to build things first-to-last, unlike recursive version: static IntList incrList(IntList P, int n) { if (P == null) Last modified: Wed Jan 29 13:26:29 2020 CS61B: Lecture #3 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com