Ein auf Bitoperatoren basierter Algorithmus der das Rechnen mit Zutaten beschreibt
Wenn anhand eines gegebenen Kochrezeptes berechnet werden soll welche Zutaten dafür benötigt werden, ist das allein mit der Rezeptbezeichnung wie Erbsensuppe oder Bratkartoffeln natürlich nicht möglich, denn Rechnen geht bekanntlich nur mit Zahlen. Der vorliegende Artikel beschreibt, welche Überlegungen nötig sind, damit eine solche Rechnung möglich wird.
Jeder verfügbare Zutat wird der Wert einer Potenz von 2 zugeordnet, diese Zuordnung muss eineindeutig sein damit sie umkehrbar ist. Aneinandergereiht ergeben die Zutaten zum Beispiel folgendes Bild:
1 0 1 1 | | |_ Kartoffeln 2**0 | |___ Wasser 2**1 |_______ Speck 2**3
Was einer 4-Bit-Zahl entspricht. Wie zu sehen ist, gibt es eine Lücke für die Position 2**2
, was soviel heißt daß eine Zutat mit diesem Basiswert fürs Gesamtgericht nicht benötigt wird. Für das oben dargestellte Gericht ergibt sich somit der numerische Wert 11. Um auf diesen Wert zu kommen, werden die Werte der Zutaten bitweise UND-verknüpft: 2**0|2**1|2**3
was praktisch einer Addition gleichkommt.
Ebenfalls mit Bitoperatoren ist es nun möglich herauszukriegen welche Zutaten im Rezept mit der Wertigkeit 11
stecken. Um auf Speck zu testen, werden in der Elf drei Bits nach rechts geschoben und eine Maske darübergelegt:
print 11 >> 3 & 1; # 1
Auf diese Art und Weise lassen sich sämtliche für das Rezpt benötigten Zutaten ermitteln.
Dazu benötigen wir ein Array mit allen Gerichten die auf diese Art und Weise zusammengestellt wurden und gehen diese Liste durch. Vorher wurde über den Logarithmus die Zweierpotenz der Zutat emittelt, das ist genau die Anzahl der Bits die im numerischen Wert des Gerichts nach rechts verschoben werden müssen. Wird dann mit der Maske & 1
eine Eins ermittelt, heißt das daß die angegebene Zutat im betreffenden Gericht enthalten ist.
use strict; use warnings; # Schöner Ersatz für print sub puts{ local $, = "\n"; local $\ = "\n"; print @_; } # Logarithmus zur Basis 2 sub log2 { my $n = shift; return log($n)/log(2); } # Rechner Architektur use constant ARC => 32; # Die Basiszutaten im Dualen System # d.h., jeder Wert ist eine Potenz von 2 my %bas = ( 'Wasser' => 2**0, 'Salz' => 2**1, 'Pfeffer' => 2**2, 'Speck' => 2**3, 'Kartoffeln' => 2**4, 'Zwiebeln' => 2**5, 'Kümmel' => 2**6, 'Majoran' => 2**7, 'Petersilie' => 2**8, 'Erbsen' => 2**9, ); # Nun wird gekocht, 2 Rezepte my $Bratkartoffeln = $bas{'Kartoffeln'} | $bas{'Speck'} | $bas{'Zwiebeln'} | $bas{'Kümmel'} | $bas{'Majoran'} | $bas{'Salz'} | $bas{'Pfeffer'}; my $Erbsensuppe = $bas{'Kartoffeln'} | $bas{'Speck'} | $bas{'Zwiebeln'} | $bas{'Kümmel'} | $bas{'Majoran'} | $bas{'Salz'} | $bas{'Pfeffer'} | $bas{'Wasser'} | $bas{'Erbsen'}; # Wir sehen unterschiedliche Ergebnisse # nun schauen wir mal was drin ist # Bnötigt wird die Basis auch genau andersherum my %rbas = reverse %bas; puts "Erbsensuppe"; puts "============"; puts map{ $_->[1] } sort{ $a->[1] cmp $b->[1] } map{ [$_, $rbas{$_}] } contents( $Erbsensuppe ); puts " "; puts "Bratkartoffeln"; puts "============"; puts map{ $_->[1] } sort{ $a->[1] cmp $b->[1] } map{ [$_, $rbas{$_}] } contents( $Bratkartoffeln ); # nun schauen wir mal was drin ist # angenommen werden 16 Bit sub contents{ my $num = shift; #puts sprintf "%b", $num; my @raw = (); for my $pot( 0 .. ARC - 1 ){ my $kbit = $num >> $pot & 1; my $zk = $kbit**$pot; #puts $kbit; if( $kbit ){ push @raw, 2**$pot; } } return @raw; } my %Gerichte = ( $Erbsensuppe => 'Erbsensuppe', $Bratkartoffeln => 'Bratkartoffeln' ); # Nun wollen wir mal schauen in welchen Gerichten eine bestimmte Zutat ist puts "\n====== Gerichte mit Erbsen ====="; puts map { $Gerichte{$_} } lookup( $bas{Erbsen} ); puts "\n====== Gerichte mit Speck ====="; puts map { $Gerichte{$_} } lookup( $bas{Speck} ); sub lookup{ my $znr = shift; # Nummer der Zutat my $bits = log2 $znr; # Bits to shift my @res = (); foreach my $gericht( keys %Gerichte ){ if($gericht >> $bits & 1){ push @res, $gericht; } } return @res; } # Auf mehrere Zutaten prüfen puts "\n======== Gerichte mit Speck und Kartoffeln ===="; puts map { $Gerichte{$_} } and_lookup( $bas{Speck}, $bas{Kartoffeln} ); puts "\n======== Gerichte mit Erbsen und Kartoffeln ===="; puts map { $Gerichte{$_} } and_lookup( $bas{Erbsen}, $bas{Kartoffeln} ); # Beide Zutaten müssen enthalten sein sub and_lookup{ # Nummern der Zutaten in @_ my %res = (); my @bits = map{ log2 $_ } @_; foreach my $gericht( keys %Gerichte ){ foreach my $xbit (@bits){ if( $gericht >> $xbit & 1 ){ $res{$gericht}++; } } } # Anzahl der Zutaten gleich Anzahl derer im Gericht return grep { $res{$_} == scalar @_ } keys %res; } puts "\n===== Gerichte mit Erbsen oder Kartoffeln ======"; puts map { $Gerichte{$_} } or_lookup( $bas{Erbsen}, $bas{Kartoffeln} ); # Eine der Zutaten muss drin sein sub or_lookup{ # Nummern der Zutaten in @_ my %res = (); my @bits = map{ log2 $_ } @_; foreach my $gericht( keys %Gerichte ){ foreach my $xbit (@bits){ if( $gericht >> $xbit & 1 ){ $res{$gericht}++; } } } return keys %res; } # Das Perlscript erzeugt untenstehende Ausgabe __END__ Erbsensuppe ============ Erbsen Kartoffeln Kümmel Majoran Pfeffer Salz Speck Wasser Zwiebeln Bratkartoffeln =========== Kartoffeln Kümmel Majoran Pfeffer Salz Speck Zwiebeln ====== Gerichte mit Erbsen ===== Erbsensuppe ====== Gerichte mit Speck ===== Bratkartoffeln Erbsensuppe ======== Gerichte mit Speck und Kartoffeln ==== Bratkartoffeln Erbsensuppe ======== Gerichte mit Erbsen und Kartoffeln ==== Erbsensuppe ===== Gerichte mit Erbsen oder Kartoffeln ====== Bratkartoffeln Erbsensuppe
Datenschutzerklärung: Diese Seite dient rein privaten Zwecken. Auf den für diese Domäne installierten Seiten werden grundsätzlich keine personenbezogenen Daten erhoben. Das Loggen der Zugriffe mit Ihrer Remote Adresse erfolgt beim Provider soweit das technisch erforderlich ist. sos@rolfrost.de.