suche N.Wirth,Algorithmen..,rekursion,"problem der stabilen heirat",source-txt

[andijota]

Guten Morgen ,
hab mein Wirth-Buch nicht dabei , und braeuchte dringend den source-txt "Das Problem der stabilen Heirat" aus Nicolaus Wirth , Algorithmen und datenstrukturen , das muesste im Rekursions - kapitel gleich hinter dem "Problem mit den 8 Damen" (auf nem schachbrett, die sich nicht gegenseitig angreifen) stehen. Modula - Version oder Pascal is egal

hier habe ich aber das Buch:
Robert Sedgewick, Algorithmen in C++, Teil 1-4
( erst gestern gekauft , den Wirth gab es auf die schnelle nicht ). Das hat ja viel Gemeinsamkeiten mit Wirth, (zB. die tuerme von hanoi ) aber das "Problem der stabilen Heirat" hab ich noch nicht in 10 minuten gefunden , und weiss einfach noch nicht ob es auch im Robert Sedgewick, Algorithmen.. -Buch versteckt ist (..und frecher-weise ist nichtmal ´ne CD dabei , dass man schnell was findet , da kann ich mich nur wundern). Alternativ ist auch das "Rucksack-Programm" auf Seite 230 drinn, aber ich bin mir nicht sicher inwieweit ich von diesem Loesungsansatz den gesuchten Loesungs-code fuer das "Problem der stabilen Heirat" ableiten kann. ( die Heirat ist in etwa als stabil zu bezeichnen , wenn in einer Menge von Paaren moeglichst viele Partner zusammen sind , die sich gegenseitig oben auf der eigenen Liste der bevorzugten Partner fuehren ; sonst wuerden die sich zu jemand anderem mehr hingezogen fuehlen und es koennte sein , dass die Partnerwahl nicht stabil bleibt , sondern sich welche trennen).

Also meine Bitte waere an jemanden der das Buch hat , die drei seiten mal kurz vor die digitalkamera zu halten , die bilddateien durchs OCR -programm zu jagen , und den txt hier reinschicken , oder mailen .

ich wuerde mir jedenfalls fuer jemand anderen die 5 min zeit nehmen , in der ueberzeugung , dass gegenseitige hilfe gut ist.

also DANKE , hoffe auf den source.txt

viele gruesse aus berlin

andi

[andijota]

PS
. . aber klar , wenn es dann nach 9:30 wird , werde ich mich natuerlich selber mit digicam in eine bibliothek oder buchladen auf den weg machen . . entweder humboldt-uni oder theodor heuss platz faellt mir da ein..

[andijota]

// PS PS

// .. der vollstaendigkeit halber , fuer alle die die Buecher nicht parat haben
// und trotzdem wissen moechten worum es geht , das Rucksack - programm:

// Die optimale Packung ist die wir fuer den kleinsten Rucksack der Groesse
//____ cap - items[i].size finden werden.
// rucksack-fassungsvermoegen , Abmessung
// da soll moeglichst viel Gesamt-Wert rein ,
// in Form von Gegenstaenden mit Abmessung und Wert
// typedef struct {int size; int val;}Item ____array von
// N Gegenstaenden items , des typ Item

// wir speichern jeden berechneten Funktionswert ,
// rufen dann die gespeicherten Werte ab wenn wir sie benoetigen
// (wobei wir einen Markierungswert verwenden ,
// um unbekannte Werte darzustellen ) anstatt Rekursion.
// Wir speichern den Index des Gegenstands , sodass wir den Inhalt des
// Rucksacks nach der Berechnung rekonstruieren koennen , wenn gewuenscht.
//____ itemKnown[M] is im Rucksack ,
// und der restliche Inhalt ist der gleiche , wie fuer den
// optimalen Rucksack der Groesse
// M- items[M].size sodass
// itemKnown[M- items[M].size] ____im Rucksack ist . . . . . .

//____0____1____2____3____4
//____A____B____C____D____E____item
//____3____4____7____8____9____size
//____4____5___10___11___13____val

// erste Loesung rekursiv : :

int knap(int cap)
{ int i, space, max, maxi =0 , t;
if(maxKnown[M] !=unknown)return maxKnown[M];

for(i =0; max =0; i< N; i++)
if((space< cap -items[i].size) >=0)
if((t =knap(space) +items[i].val) >max)
{ max =t; }

return max;
}

// und dann ohne , weil schneller ,
// weil Neuberechnungen gespart werden : :

int knap(int M)
{ int i, space, max, maxi =0 , t;
if(maxKnown[M] !=unknown)return maxKnown[M];

for(i =0; max =0; i< N; i++)
if((space =M-items[i].size) >=0)
if((t =knap(space) +items[i].val) >max)
{ max =t; maxi =i;}

maxKnown[M] =max; itemKnown[M] =items[maxi];
return max;
}

// Dynamisches programmieren verringert die Laufzeit einer rekursiven Funktion
// auf hoechstens die Zeit , die erforderlich ist um die Funktion fuer
// alle Argumente kleiner oder gleich dem gegebeneb Argument auszuwerten ,
// wobei die Kosten eines rekursiven Aufrufs als konstant behandelt werden.

// forum
// http://www.c-plusplus.net/forum/viewforum-var-f-is-8.html

[andijota]

DANKE !
an Florian Lutz von der fh-regensburg.de , der sandte mir den link
http://home.zhwin.ch/~frp/ADS/Unterlagen/07_Backtracking.pdf

, und das ist ein VOLLTREFFER!

merci
andi

[hehehe]