Programeer opdrachtenOpdracht : opdr7a_jovo.txt

Terug naar de inzendingen
Opdracht 7a,Johan Volkers
17 Dec 2009
 Mijn oplossing (ook in Perl)
 1 
*****WortelTrekken.pl*****
  
 2#! /usr/bin/perl
 3
 4=doc 
 5
 6>>>>>                       TrekWortel                         <<<<<
 7
 8Programmeeropdracht Worteltrekken
 9
 10Benodigd:    standaard installatie Perl 5
 11Gebruik:    uitvoerbaar maken via 
 12        chmod +x TrekWortel
 13        ./TrekWortel 
 14
 15Copyright (c) 2009 Johan Volkers.
 16All rights reserved. This program is free software;
 17You can redistribute it and/or modify it under the same terms as Perl itself.
 18
 19=cut
 20
 21use strict;
 22
 23package Zeef;
 24
 25use strict;
 26
 27our @Zeef;
 28
 29# Redelijk recht-toe-recht-aan implementatie van de zeef van Erasthostenes
 30#
 31# Kan efficienter qua geheugengebruik
 32# Op deze manier gebruik ik voor het berekenen van de wortel uit 10.000.000
 33# plm. 200 MB
 34#
 35# Een efficientere methode is: 
 36# - even getallen niet meenemen
 37# - via de vec()-functie bitjes gebruiken
 38# Dan kost 10.000.000 nog maar 625 KB maar het vraagt meer rekentijd
 39
 40sub InitZeef
 41{
 42    my $maxnbr=shift;
 43    @Zeef=(0,0,1,(1,0) x int(($maxnbr+1)/2));    # alle even getallen (muv 2)
 44                            # zijn al uitgepoetst
 45    my $n=3;
 46    while(1) {
 47        last if $n * $n > $#Zeef;
 48        if ($Zeef[$n]) {
 49            # we hebben een priemgetal
 50            my $n2=$n+$n;
 51
 52            # haal alle oneven veelvouden weg (de even veelvouden zijn al weg)
 53            for (my $i=$n+$n2; $i <= $#Zeef; $i+=$n2) {
 54                $Zeef[$i]=0;
 55            }
 56        }    
 57        $n+=2;
 58    }    
 59}
 60
 61# kijk of een bepaald getal priem is
 62sub IsPriem
 63{
 64    my $nbr=shift;
 65    return undef if $nbr > $#Zeef;
 66    return $Zeef[$nbr];
 67}
 68
 69# lever het eerste priemgetal > n op
 70sub VolgendPriemgetal
 71{
 72    my $nbr=shift;
 73    return 3 if $nbr == 2;
 74    return undef unless $nbr & 1;    # moet wel oneven zijn
 75    while(1) {
 76        $nbr += 2;
 77        return undef if $nbr > $#Zeef;
 78        return $nbr if $Zeef[$nbr];
 79    }    
 80
 81}
 82
 83package main;
 84
 85my $getal=shift;
 86
 87# controleer getal
 88if ($getal < 0 || $getal != int($getal)) {
 89        print STDERR "Verkeerde input\n";
 90        exit(1);
 91}
 92if ($getal < 2) {
 93    # 1*1 = 1, 0*0 = 0
 94    print "$getal\n";
 95} else {        
 96    Zeef::InitZeef($getal);
 97    print GeefUitkomst(Ontbind($getal)),"\n";
 98}
 99
 100# ontbind een getal en lever een array van factoren af (niet dalend)
 101sub Ontbind
 102{
 103    my $nbr=shift;
 104    my @factor;
 105
 106    my $deler=2;
 107    while(1) {
 108        # als wat overblijft priem is zijn we klaar
 109        return (@factor,$nbr) if Zeef::IsPriem($nbr);
 110
 111        if ($nbr % $deler == 0) {
 112            push(@factor,$deler);
 113            $nbr /= $deler;
 114        } else {
 115            # anders probeer de volgende deler
 116            $deler=Zeef::VolgendPriemgetal($deler);
 117        }
 118    }    
 119
 120}
 121
 122# input is een reeks factoren 2 2 3 5 7 7 etc
 123sub GeefUitkomst
 124{
 125    my @factor=@_;
 126    my $kwadraat=1;
 127    my $wortel=1;
 128
 129    # heeft @factor 2 of meer elementen?
 130    while(@factor >= 2) {
 131        if ($factor[0] == $factor[1]) {
 132            # twee gelijke factoren vooraan
 133            $kwadraat *= shift(@factor);
 134            shift(@factor);            # de tweede ook
 135        } else {
 136            # een enkele factor
 137            $wortel *= shift(@factor);
 138        }
 139    }
 140
 141    # effe de laatste (als die er is)
 142    $wortel *= $factor[0] if @factor;
 143
 144    # selecteer het juiste outputformaat
 145    return sprintf "wortel %d",    $wortel             if $kwadraat == 1;
 146    return sprintf "%d",        $kwadraat            if $wortel == 1;
 147    return sprintf "%d wortel %d",    $kwadraat, $wortel;
 148
 149}
 
 
Mijn commentaar
 
 Mooie manier van werken Johan, ik doe graag alles vrij rechtoe-rechtaan (ik
 programeer dan eigenlijk gewoon C)
 Mooi dat je jouw eigen implementatie hebt bedacht.
 
 Dank voor het meedoen.