Datastrukturer & Algoritmer, Dat C
FOREL¯BIG UDGAVE; vil blive udvidet og rettet snarest!!
Óat
en procedure kalder sig selvÓ Ñ eller et antal procedurer kalder hinanden
rekursivt.
Meget
elegant til ting, som er rekursive af natur!
private static int
binarySearch( Comparable [ ] a, Comparable x,
int low, int high )
{ if( low > high ) return -1
int
mid = ( low + high ) / 2;
if(
a[ mid ].compareTo( x ) < 0 )
return binarySearch( a, x, mid + 1, high );
else if( a[ mid ].compareTo( x ) > 0 )
return binarySearch( a, x, low, mid - 1 );
else
return mid;}
Tidsforbrug:
log n.
Ñ Implementation ved stak (tager
compileren sig af)
Ñ Optimeringer ved bl.a.
halerekursion (compiler producerer samme kode som var det skrevet med ÓforÓ
eller ÓwhileÓ.
Eksempler
hvor rekursion er elegant
Ñ
rekursivt
definerede datastrukturer,
f.eks. et tr¾ (eksempel om et ¿jeblik)
Ñ
compilere
og sprog
<s¾tning> ::= if( <betingelse> )
<s¾tning> ;
| while(
<betingelse> ) <s¾tning> ;
| ...
Datastrukturen er syntakstr¾er;
Parser, evt. hele compiler (Pascal, men ikke Java)
er en samling rekursive procedurer, Žn for
hver syntaktisk
kategori.
Ñ
matematiske
definitioner ofte rekursive
Tr¾er:
rekursiv datastruktur og tilh¿rende rekursive algoritmer
anvendelser:
s¿getr¾er, syntakstr¾er,...
public
class TreesWithNumbers
{ private TreesWithNumbers left; private
TreesWithNumbers right;
private int value;
public TreesWithNumbers(int n)
{value = n;};
public
TreesWithNumbers(TreesWithNumbers left, int n,
TreesWithNumbers
right)
{this.left=left; value=n;
this.right=right;};
....
public static void main( String [
] args )
{ TreesWithNumbers t =
new
TreesWithNumbers( new TreesWithNumbers(5),
10,
new TreesWithNumbers( new TreesWithNumbers(8),
6,
new TreesWithNumbers(17)
)
);
System.out.println("Tr¾et " + t + " har sum " +
t.sum());
t.pp();
}
}
Rekursive
metoder til rekursive strukturer.
public String toString()
{return "(" + left.toString() + "[" +
value + "]" + right.toString() + ")";};
Denne
her er bedre:
public String toString()
{return "("
+
(left==null ? "" : left.toString())
+
"[" + value + "]"
+
(right==null ? "" : right.toString())
+
")";};
(([5])[10](([8])[6]([17])))
At
summe v¾rdierne sammen:
public int sum()
{return left.sum() + value +
right.sum();};
public int sum()
{return (left==null ? 0 : left.sum())
+
value
+
(right==null ? 0 : right.sum());};
Matematiske
definitioner,
f.eks.
n! = 1 x 2 x ... x (n-1) x n
public
class Factorial
{
public static long factorial( int n )
{if( n <= 1 ) return 1;
else return n *
factorial( n - 1 ); }
public static void main(
String [ ] args )
{for( int i = 1; i <=
10; i++ )
System.out.println( factorial( i ) );}}
Eksempel:
Fibonaccital
0,
1, 1, 2, 3, 5, 8, 13, ...
hvad er systemet?
public static int fib1(int n)
{if(n<=1) return n;
else return fib1(n-1) +
fib1(n-2);}
Elegant,
smukt, ubrugeligt
...
eksempel pŒ Ódel-og.herskÓ nŒr det ikke virker
...
vi vender tilbage til eksemplet!
Generelt
m¿nster:
public
static L¿sning l¿s(Problem p)
{
if(simpel(p)) return l¿sningen-pŒ-det-simple-problem;
split p op i
p1, ..., pn;
L1 = l¿s p1;
L2 = l¿s p2;
. . .
Ln = l¿s pn;
return
kombiner(L1, ;2, ..., Ln); }
Det
bedste eksempel: Bin¾r s¿gning:
private static int
binarySearch( Comparable [ ] a, Comparable x,
int low, int high )
{ if( low > high ) return -1;
int
mid = ( low + high ) / 2;
if(
a[ mid ].compareTo( x ) < 0 )
return binarySearch( a, x, mid + 1, high );
else if( a[ mid ].compareTo( x ) > 0 )
return binarySearch( a, x, low, mid - 1 );
else
return mid;
}
Tidsforbrug:
log n.
Andre
eksempler: Sortering, f.eks. mergesort
Generel
formel til vurdering af tidsforbrug
public
static L¿sning l¿s(Problem p)
{
if(simpel(p)) return l¿sningen-pŒ-det-simple-problem;
split p op i
p1, ..., pn;
L1 = l¿s p1;
L2 = l¿s p2;
. . .
Ln = l¿s pn;
return
kombiner(L1, ;2, ..., Ln); }
Parametre:
A,
antallet af delproblemer (n
ovenfor)
B,
mŒl for relativ st¿rrelse af delproblem (f.eks. B=2 for halvering)
k,
bestemt ved ÓoverheadÓ Theta(Nk) (= prisen for at ÓkombinereÓ)
T(N)
= { O(N logB
A) hvis A > Bk
{
O(Nk log N) for A= Bk
{
O(Nk) for A < Bk
Anvende
den pŒ bin¾r s¿gning ....
Del-og-hersk-version
af maksimum-sum-problemet
<fotokopier fra
boget s. 261 og 262>
Anvend formel ...
Princippet: Vi skal l¿se et problem
P(n)
Hvis
vi, for at l¿se P(n) fŒr brug for, direkte eller indirekte, at kende l¿sningen
pŒ P(1), P(2), ..., P(n-1),
sŒ
beregner vi dem alle fra en ende af og l¾gger dem i et array.
public static int fib2(int n) //assume
n>=2
{ int [] fibs = new int [n+1];
fibs[0] = 0; fibs[1] = 1;
for(int i=2; i<= n; i++)
fibs[i] =
fibs[i-1]+fibs[i-2];
return fibs[n];}
Eksemplet,
at give byttepenge
public
final class MakeChange
{ public static void makeChange( int [ ]
coins, int differentCoins,
int maxChange, int [ ] coinsUsed )
{ coinsUsed[ 0 ] = 0;
for( int cents = 1; cents <= maxChange; cents++ )
{ int minCoins = cents;
int newCoin = 1;
for( int j = 0; j < differentCoins; j++ )
{ if( coins[ j ] > cents
) // Cannot use coin j
continue;
if( coinsUsed[ cents - coins[ j ] ] + 1 < minCoins )
{ minCoins = coinsUsed[
cents - coins[ j ] ] + 1;
newCoin = coins[ j ];}}
coinsUsed[ cents ] = minCoins;}}
public static void main(
String [ ] args )
{ // The coins and the
total amount of change
int
numCoins = 5;
int
[ ] coins = { 1, 5, 10, 21, 25 };
int
change = 117;
int
[ ] used = new int[ change + 1 ];
makeChange( coins, numCoins, change, used );
System.out.println( "Best is " + used[ change ] + "
coins" );}}
Afsluttende
¿velse: 4 mŒder at beregne Fibonacci-tal pŒ:
// "Divide & conquer" -
not recommended
public static int fib1(int n)
{if(n<=1) return n;
else return fib1(n-1) +
fib1(n-2);}
// "Dynamic programming"
public static int fib2(int n) //assume
n>=2
{ int [] fibs = new int [n+1];
fibs[0] = 0; fibs[1] = 1;
for(int i=2; i<= n; i++)
fibs[i] =
fibs[i-1]+fibs[i-2];
return fibs[n];}
// "Memoization"
private static HashMap table = new
HashMap();
public static int fib3(int n)
{ Object resultCell;
if((resultCell =
table.get(new Integer(n)))!= null )
return
((Integer)resultCell).intValue();
else
{int
result;
if(n<=1) result=n;
else result=fib1(n-1) + fib1(n-2);
table.put(new Integer(n), new Integer(result));
return(result);};}
// "Direct algorithm"
// - can be seen as optimized DynProg or
memo
// ... however it the long run
outperformed by Memo!
public static int fib4(int n)//assume
n>=2
{int f0=0; int f1=1; int buf;
for(int i=2;i<=n;i++)
f1= f0+(f0=f1);
return f1;};
Afslutning:
Ñ Rekursion er elegant for de rigtige problemer
Ñ Del-og-hersk er en mŒde at forstŒ mange
rekursive algoritmer pŒ, f.eks. s¿gning og sortering
Ñ ÓDynamisk programmeringÓ er en lignenden, ikke
rekursiv teknik, som er god nŒr et problem splittes op i Ólignende, men mindreÓ
delproblemer.
Ñ Memoisering er kan ses som dyn.prog. med
langtidshukommelse, og som kun bberegner det, der er brug for.
Ñ kr¾ver en tungere
datastruktur, men tjener sig ind i l¾ngden