Datastrukturer & Algoritmer, Dat C

Forel¾sning 1/10-2002

Henning Christiansen

FOREL¯BIG UDGAVE; vil blive udvidet og rettet snarest!!

Rekursion og Ódynamisk programmeringÓ

 

Óat en procedure kalder sig selvÓ Ñ eller et antal procedurer kalder hinanden rekursivt.

 

Meget elegant til ting, som er rekursive af natur!

 

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.

 

Ñ 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,...

 

Eksempel: Simple tr¾er med tal

 

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.

 

Det er fristende at skrive

 

 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:

 

Det er fristende at skrive

 

   public int sum()

   {return left.sum() + value + right.sum();};

 

Denne her er bedre

 

   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!

 


En programmeringsteknik: Del og hersk

 

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 ...

 


Dynamisk programmering

 

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.

 

Eksempel: Fibonacci ved dynamisk programmering

 

  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