1 2005 7 22 22 (sakai.keiichi@kochi sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2005/index.html tech.ac.jp/k1sakai/lecture/alg/2005/index.html
f(0) = 1, f(x) = x! = x*f(x 1) f(0) = 1, f(1) = 1, f(x) = f(x 2) + f(x 1) f(0) f(1)
public class Factorial public static int factorial(int atarget) if(0 > atarget) throw new IllegalArgumentException(); System.out.println("factorial(" + atarget + ") "); if(0 == atarget) System.out.println("factorial(0) : 1"); return 1; int total = atarget * Factorial.factorial(aTarget - 1); System.out.println("factorial(" + atarget + ") : " + total); return total; public static int factorialwithoutrecursion(int atarget) if(0 > atarget) throw new IllegalArgumentException(); if(0 == atarget) return 1; int total = atarget; for(int count = atarget - 1; 0 < count; count--) total *= count; return total;
public class Fibonatti public static int fibonatti(int atarget) if(0 > atarget) throw new IllegalArgumentException(); System.out.println("fibonatti(" + atarget + ") "); if((0 == atarget) (1 == atarget)) System.out.println("fibonatti(" + atarget + ") : 1"); return 1; int total = fibonatti(atarget - 2) + fibonatti(atarget - 1); System.out.println("fibonatti(" + atarget + ") : " + total); return total; f(0) f(x) f(x 1) f(x 2) 2 public static int fibonattiwithoutrecursion(int atarget) if(0 > atarget) throw new IllegalArgumentException(); if((0 == atarget) (1 == atarget)) return 1; int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= atarget; count++) total = old1 + old2; old2 = old1; old1 = total; return total;
[sakai@star 13]$ java FactorialTest 720 factorial(6) factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0) factorial(0) : 1 factorial(1) : 1 factorial(2) : 2 factorial(3) : 6 factorial(4) : 24 factorial(5) : 120 factorial(6) : 720 [sakai@star 13]$ [sakai@star 13]$ java FibonattiTest 8 fibonatti(5) fibonatti(3) fibonatti(1) fibonatti(1) : 1 fibonatti(2) fibonatti(0) fibonatti(0) : 1 fibonatti(1) fibonatti(1) : 1 fibonatti(2) : 2 fibonatti(3) : 3 fibonatti(4) fibonatti(2) fibonatti(0) fibonatti(0) : 1 fibonatti(1) fibonatti(1) : 1 fibonatti(2) : 2 fibonatti(3) fibonatti(1) fibonatti(1) : 1 fibonatti(2) fibonatti(0) fibonatti(0) : 1 fibonatti(1) fibonatti(1) : 1 fibonatti(2) : 2 fibonatti(3) : 3 fibonatti(4) : 5 fibonatti(5) : 8 [sakai@star 13]$
public class Disk public Disk(int asize) if(1 > asize) throw new IllegalArgumentException(); this.size = asize; public int size() return this.size; private int size = 0;
import java.util.stack; public class Tower public Tower() this.stack = new Stack(); public Disk get() return (Disk)this.stack.pop(); public Disk get(int anindex) return (Disk)this.stack.get(anIndex); public int size() return this.stack.size(); public boolean put(disk adisk) if(this.stack.isempty()) this.stack.push(adisk); return true; int topsize = ((Disk)this.stack.peek()).size(); if(adisk.size() < topsize) this.stack.push(adisk); return true; return false; private Stack stack;
public class Hanoi private Tower[] tower = new Tower[] new Tower(), new Tower(), new Tower() ; private int disks; public Hanoi(int adisks) this.disks = adisks; for(int count = adisks; 0 < count; count--) this.tower[0].put(new Disk(count)); this.printall(); public void dohanoi() this.dohanoi(this.disks, 0, 1, 2); private void dohanoi (int adisks, int afrom, int ato, int another) if(1 == adisks) Disk disk = this.tower[afrom].get(); this.tower[ato].put(disk); this.printall(); else this.dohanoi(adisks - 1, afrom, another, ato); Disk disk = this.tower[afrom].get(); this.tower[ato].put(disk); this.printall(); this.dohanoi(adisks - 1, another, ato, afrom);
private void printall() int[] towersizes = tower[0].size(), tower[1].size(), tower[2].size() ; int towersizetotal = (towersizes[0] + towersizes[1] + towersizes[2]); int[] sizes = towersizes[0], towersizes[1], towersizes[2]; for(int count = 0; count < towersizetotal; count++) for(int tcount = 0; tcount < 3; tcount++) if((towersizetotal - towersizes[tcount]) <= count) Disk disk = this.tower[tcount].get(--sizes[tcount]); System.out.print(" t"); for(int disks = 0; disks < disk.size();disks++) System.out.print("-"); System.out.print(" t"); else System.out.print(" t t"); System.out.println(""); System.out.println("-------------------------------------------------"); System.out.println("");
1. 2. 3. 4. 29 20 32 14 24 30 48 7 19 21 31
public void printtreerecursive() this.printtreerecursive(this.root, 0); private void printtreerecursive(mynode alocalrootnode, int depth) if(null == alocalrootnode) return; this.printtreerecursive(alocalrootnode.getright(), depth+1); for(int i=0; i < depth; i++) System.out.print(" t"); System.out.println(aLocalRootNode.getData().toString()); this.printtreerecursive(alocalrootnode.getleft(), depth+1); (29, " ") (20, " ") (14, " ") (32, " ") (30, " ") (24, " ") ( 7, " ") (21, " ") (48, " ") (31, " ") (19, " ") (17, " ") (23, " ") (28, " ") (48' ) (32' ) (31' ) (30' ) (29' ) (28' ) (24' ) (23' ) (21' ) (20' ) (19' ) (17' ) (14' ) (7' )
(48' ) (32' ) (31' ) (30' ) (29' ) (28' ) (24' ) (23' ) (21' ) (20' ) (19' ) (17' ) (14' ) (7' ) this.printtreerecursive((23, this.printtreerecursive((17, " "), ), " "), ), 4); 4); this.printtreerecursive((31, this.printtreerecursive((28, this.printtreerecursive((19, this.printtreerecursive((21, 7, " "), " "), ), ), " "), ), 3); 3); this.printtreerecursive((48, this.printtreerecursive((30, this.printtreerecursive((24, this.printtreerecursive((14, " "), ), " "), " "), ), ), 2); 2); this.printtreerecursive((32, this.printtreerecursive((20, " "), ), 1); 1); this.printtreerecursive((29, " "), ), 0);
LIFO
CPU 1. 2. 3. 4.
public void printtreeloop() MyNode node, currentrootnode = this.root; int depth = 0, todo = 0; Stack stack = new Stack(); while(true) switch(todo++) case 0: node = currentrootnode.getright(); if(node!= null) stack.push(currentrootnode); currentrootnode = node; stack.push(new Integer(todo)); todo = 0; depth++; break; case 1: for(int i=0; i < depth; i++) System.out.print(" t"); System.out.println(currentRootNode.getData().toString()); break; //
case 2: node = currentrootnode.getleft(); if(node!= null) stack.push(currentrootnode); currentrootnode = node; stack.push(new Integer(todo)); todo = 0; depth++; break; case 3: if(stack.empty()) return; todo = ((Integer)stack.pop()).intValue(); currentrootnode = (MyNode)stack.pop(); depth--; 1. 2. 3. 4.