RaetseL20041001 < Wissensbasis

Du bist auf dieser Seite als WikiGuest
Log In or Register
Nutzerliste

You are here: Wissensbasis Web>UtilPerlSkripteInclude>RaetseL20041001 (2004-10-08)

RDW #11 (Rätsel vom 01.10.2004)

Aufgabe
Musterlösung
Normale Lösungen
- Crian
- Esmaya
- Betterworld
- Ishka
- Renee
Golflösungen
- Dubu-Golf
- DS-Golf
- Steve
Dateien
- normale Lösungen
- Golf-Lösungen
Ergänzungen, Kommentare

Aufgabe

 RDW #11 - Raetsel der Woche Nummer 11
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


 Regeln:  * Bitte nicht vor Ablauf der ersten 72 Stunden ( = drei Tage ) nach
 ~~~~~~~    Veroeffentlichung Hinweise (Spoiler) oder Loesungen veroeffent-
            lichen!

          * Wenn diese Zeit abgelaufen ist, werde ich einen Thread mit passen-
            dem Titel erstellen, in dem die Loesungen gepostet werden und dis-
            kutiert werden koennen.

          * Die Loesungen sollten nicht nur gepostet, sondern auch an mich ge-
            mailt werden, damit ich sie testen, "bewerten"  und zusammenfassen
            kann. Die Adrese dafuer lautet:

            crian <---AT---> perl <---MINUS---> community <---DOT---> de

            Im Betreff sollte 'RDW' und die Nummer des Raetsels stehen. Hilf-
            reich waere neben dem Quellcode der Username im Forum sowie Perl-
            und OS-Version, falls Du diese kennst.

          * Verstaendnisfragen duerfen in diesem Thread gestellt werden, aber
            Tipps und (Teil-) Loesungen sind hier unerwuenscht.

          * Ich werde die eingeschickten Programme im Netz zur Verfuegung
            stellen, so dass gerade lange Quellcodes nicht (komplett)
            gepostet werden muessen.

          * Zur Verwendung von Modulen: Ich moechte diese nicht generell aus-
            schliessen, aber wenn quasi die komplette Aufgabe durch die Ver-
            wendung eines Moduls ersetzt werden kann, ist dies vielleicht nicht
            der Sinn der Aufgabe gewesen.



 Aufgabe: K G V   und   G G T
 ~~~~~~~~
          Schreiben Sie ein Programm, welches zwei natürliche Zahlen als
          Parameter (auf der Kommandozeile) entgegen nimmt und  den groessten
          gemeinsamen Teiler und das kleinste gemeinsame Vielfache berechnet
          und ausgibt.

          Beispielläufe:

              G:\privat\perl\rdw\rdw11>rdw11_crian.pl 24 60
              12 120

              G:\privat\perl\rdw\rdw11>rdw11_crian.pl 24 12
              12 24

              G:\privat\perl\rdw\rdw11>rdw11_crian.pl 245 1024
              1 250880

              G:\privat\perl\rdw\rdw11>rdw11_crian.pl 245425 1025652
              1 251720642100

Musterlösung

Ist schon fertig, wird aber erst nach Ablauf der Zeit gezeigt.

#!/usr/bin/perl
use strict;
use warnings;

die "Syntax: $0 ZAHL1 ZAHL2\n" unless @ARGV == 2;

my $Debug = 0;

my ($x, $y) = @ARGV;

my @p = p($x>$y?$x:$y);
my @x = f($x, \@p);
my @y = f($y, \@p);

print "Primfaktoren von $x : ", join(", ", @x), "\n" if $Debug;
print "Primfaktoren von $y : ", join(", ", @y), "\n" if $Debug;

my %x;
my %y;
++$x{$_}for@x;
++$y{$_}for@y;

my %ggt;
my %kgv;

my @k = (keys %x, keys %y);
my %k;
++$k{$_}for@k;

for (keys %k) {
    if (exists $x{$_} and exists $y{$_}) {
        $ggt{$_} = $x{$_}<$y{$_} ? $x{$_} : $y{$_};
        $kgv{$_} = $x{$_}<$y{$_} ? $y{$_} : $x{$_};
    }
    elsif (exists $x{$_}) {
        $kgv{$_} = $x{$_};
    }
    elsif (exists $y{$_}) {
        $kgv{$_} = $y{$_};
    }
    else {
        die "logical error";
    }
}

my @ggt = map { ($_) x $ggt{$_} } sort keys %ggt;
my @kgv = map { ($_) x $kgv{$_} } sort keys %kgv;
#@ggt = (1) unless @ggt;
#@kgv = (1) unless @kgv;
print "Primfaktoren von GGT($x, $y): ", join(", ", @ggt), "\n" if $Debug;
print "Primfaktoren von KGV($x, $y): ", join(", ", @kgv), "\n" if $Debug;

my $ggt = 1;
my $kgv = 1;
$ggt*=$_ for@ggt;
$kgv*=$_ for@kgv;

print "GGT($x, $y) = $ggt\n" if $Debug;
print "KGV($x, $y) = $kgv\n" if $Debug;
print "$ggt $kgv\n";
exit;


sub f {
    my ($z, $p) = @_;
    my @f;

    for (my $i=0; $i<=$#$p and $p->[$i]<=$z; ++$i) {
        $z /= $p->[$i], push @f, $p->[$i] while not $z % $p->[$i];
    }

    return @f;
}


# Primzahlberechnung mit Hilfe des Sieb des Eratosthenes:
sub p {
    my ($z) = @_;
    my @s   = (2..$z);

    for (my $i=0; $s[$i]<=sqrt$z; ++$i) {
        $s[$_] % $s[$i] == 0 && $s[$_] != $s[$i] && splice @s, $_, 1 for reverse 0..$#s;
    }

    return @s;
}

Die Musterlösung berechnet zunächst die Primfaktoren der beiden gegebenen Zahlen und bildet dann aus diesen das KGV und den GGT. Ich hab aber für die Lösung nirgendwo nachgesehen, sondern mein altes Schulwissen über GGT und KGV verwendet.

Normale Lösungen

Crian

siehe Musterlösung

Esmaya

#! /usr/bin/perl
use strict;
use warnings;
my ($zahl1, $zahl2, $rech1, $rech2, $rest, $gcd, $lcm);
$rech1 = $zahl1 = $ARGV[0];
$rech2 = $zahl2 = $ARGV[1];
do {    $rest = $rech1 % $rech2;
    $rech1 = $rech2;
    $rech2 = $rest;
} until $rest == 0;
$gcd = $rech1;
$lcm = $zahl1*$zahl2/$gcd;
print "$gcd $lcm\n";

Diese Lösung ist (nach meiner) die erste Lösung die ich erhalten habe. Sie verwendet wiederholte Modulobildung um den GGT zu berechnen und verwendet dann die Formel KGV = Zahl1 * Zahl2 / GGT zur Bestimmung des KGV. Diese Vorgehensweise ist kürzer und irgendwie schlauer als meine, dafür zeigt meine schön die Zusammenhänge mit den Primfaktoren.

Betterworld

#!/usr/bin/perl
use strict;
use warnings;

# http://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Der_bin.C3.A4re_euklidische_Algorithmus

if (2 != @ARGV) {
  die "bitte 2 Argumente\n";
}
if (grep !/^[1-9]\d*$/, @ARGV) {
  die "bitte nur positive Zahlen\n";
}

my ($m, $n) = map $_+0, @ARGV[0,1];
my $p = $m * $n;
my $k=0;
until (($n | $m) & 1) {
  $_ >>= 1 for $m, $n;
  $k++;
}
($m, $n) = ($n, $m) unless $n & 1;
while ($m) {
  $m >>= 1 until $m & 1;
  ($m, $n) = ($n, $m) if $m < $n;
  $m = $m-$n;
}
my $ggt = $n * (1<<$k);
my $kgv = $p / $ggt;
print "$ggt $kgv\n";

Betterworlds Lösung war die zweite, die bei mir einging, der Algorithmus stammt wie ich aus dem Kommentar entnehme aus Wikipedia: http://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Der_bin.C3.A4re_euklidische_Algorithmus

Naja, nicht wirklich stammt er von Wikipedia, sondern vielmehr von Euklid und Stein. Aber bei Wikipedia kann man ihn nachschlagen. --betterworld

Ishka

sub ggt {
    my ($flip,$flop)=@_;
    ($flip,$flop)=($flop,$flip) if $flip<$flop;
    while(1) {
        $flip %= $flop;
        ($flip,$flop)=($flop,$flip) if $flip<$flop;
        return $flip if $flop==0;
    }
}

sub kgv {
    return ($_[0]*$_[1]/ggt(@_))
}

Es fehlen die Teile zur Verarbeitung der Eingabewerte und die Ausgabe, aber das Wesentliche ist jawohl da.

Renee

#! /usr/bin/perl

use strict;
use warnings;

$_ =~ s/[^\d]//g for(@ARGV);

my ($zahl_eins,$zahl_zwei) = @ARGV;

print "Usage: $0 <zahl> <zahl>" and exit(0) unless($zahl_eins && $zahl_zwei);

my ($ggt)                  = ggt($zahl_eins,$zahl_zwei);
my ($kgv)                  = kgv($zahl_eins,$zahl_zwei);

print "Zahlen:\t$zahl_eins und $zahl_zwei\nggT:\t$ggt\nkgV:\t$kgv\n";

sub ggt{
  my ($z_eins,$z_zwei) = @_;
  my ($min,$max)       = $z_eins > $z_zwei ? ($z_zwei,$z_eins) : ($z_eins,$z_zwei);
  my $rest             = $min;
  my $rest_alt         = $min;
  while($rest != 0 && $rest != 1){
    $rest_alt = $rest;
    $rest = $max % $min;
    $max  = $min;
    $min  = $rest;
  }
  $rest_alt = "Zahlen sind teilerfremd" if($rest == 1);
  return $rest_alt;
}# end ggt

sub kgv{
  my ($z_eins,$z_zwei) = @_;
  my ($min,$max)       = $z_eins > $z_zwei ? ($z_zwei,$z_eins) : ($z_eins,$z_zwei);
  my $viel             = $min;
  while($viel % $max != 0){
    $viel += $min;
  }
  return $viel;
}# end ggt

Golflösungen

Dubu-Golf

Die erste Golflösung kommt von Dubu:

% perl -le '($x,$y)=@ARGV;$p=$x*$y;do{($x,$y)=($y,$x%$y)}while$y;print"$x ",$p/$x;' 12 15
3 60

Laut Dubu hat sie 72 Zeichen inklusive dem -l Switch.

DS-Golf

#perl -l
$c=($a=shift)*($b=shift);$a=$b,$b=$.while$.=$a%$b;print"$b ",$c/$b

68 Zeichen, ARGV

und eine "böse" für STDIN:

#!perl -lna
($a,$b)=$a?($b,$a%$b):@F;$b?redo:print"$a ",$F[0]*$F[1]/$a

62 Zeichen, STDIN

Steve

Steve hat drei Lösungen eingeschickt, alle sehr kurz, die letzte als eigentliche Golf-Lösung, aber ich stelle sie mal alle hier vor:

$g=($m=pop)*($n=pop);
while($n){($m,$n)=($n,$m)if$m<$n;($n,$m)=($m-$n,$n)}
print"$m ",$g/$m,$/

sub g{($a,$b)=@_;if(!$b){$a}else{g($b,$a%$b)}}
@_=@ARGV;print $m=&g," ",$_[0]*$_[1]/$m,$/

$v=($b=pop)*($a=pop);($a,$b)=($b,$a%$b)while$b;die"$a ".$v/$a.$/

Dateien

http://www.perl-community.de/rdw/rdw11/rdw11.txt (Aufgabentext)

normale Lösungen

Golf-Lösungen

Ergänzungen, Kommentare

Kommentare werden am besten in folgender Form vorgenommen, damit sie im Inhaltsverzeichnis angezeigt werden (natürlich ohne das <verbatim>):

---### Main.??? - 14 Jul 2003 - Betreff

-- ChristianDuehl - 01 Oct 2004, 08 Oct 2004

UtilPerlSkripteSubForm edit

Titel	RDW #11 (Rätsel vom 01.10.2004)
Autor	ChristianDuehl
Bereich	RaetselDerWoche

Topic revision: 2004-10-08, ChristophBussenius

Wissensbasis

Bitte die NutzungsBedingungen beachten.
Bei Vorschlägen, Anfragen oder Problemen mit dem PerlCommunityWiki bitten wir um WebBottomBarExample">Rückmeldung.