Rätsel der Woche 2007/4

Aufgabe

Die Aufgabe:
~~~~~~~~~~~~
         Gib zu einer gegebenen Zahl möglichst wenige Quadratzahlen aus,
         deren Summe diese Zahl ergibt.

Beispiel:
~~~~~~~~~
         Eingabe:
         7
         Ausgabe:
         4+1+1+1
         Eingabe:
         23
         Ausgabe:
         9+9+4+1
         Eingabe:
         179
         Ausgabe:
         121+49+9

Forumsdiskussion

Teilnehmer (alphabetisch nach Nickname)

1. betterworld
2. der_Martin (in java)
3. docsnyder
4. Ishka (regulär&golf)
5. topeg
6. Vayu

Übersicht über die Lösungen

Die Lösungen im einzelnen

betterworld

#!/usr/bin/perl
use strict;
#use warnings;
use Getopt::Long;
use List::Util qw(reduce);

GetOptions('verbose'=>\my $verbose) or die;

my ($input) = @ARGV;

die 'number expected' unless $input =~ /^\d+\z/;

my $shortest;

sub new_shortest {
    my ($depth) = @_;
    if (!defined $shortest or $shortest > $depth) {
        $shortest = $depth;
        warn "shortest: $shortest\n" if $verbose;
    } else {
        warn "optimization br0ken ($shortest, $depth)\n";
    }
}

sub zerlegen {
    my ($sum, $max, $depth) = @_;
    unless ($sum) {
        new_shortest($depth);
        return [];
    }

    # Nur zur Optimierung
    return () if defined $shortest and $depth+1 >= $shortest;

    my $start = int sqrt($sum);

    # Nur zur Optimierung
    if ($start * $start == $sum) {
        new_shortest($depth+1);
        return [$sum];
    }
    # Nur zur Optimierung
    return () if defined $shortest and $depth+2 >= $shortest;

    my @zerlegungen;
    for my $i (reverse 1..$start) {
        my $quadrat = $i*$i;
        next if $quadrat > $max;
        my $rest = $sum - $quadrat;
        push @zerlegungen, [$i*$i, @$_] for zerlegen($rest, $quadrat, $depth+1);
    }
    return @zerlegungen;
}

my @zerlegungen = $input ? zerlegen($input, $input, 0) : [0];

use Data::Dumper;
print Dumper \@zerlegungen if $verbose;

print join '+', @{scalar reduce {@$a < @$b ? $a : $b} @zerlegungen};
print "\n";

der_Martin

import java.util.*;

/**
 * Lösung fÃr RÃtsel der Woche
 *
 * Suchen der Zerlegung in eine Summe von Quadratzahlen einer natÃrlichen
 * Zahl
 * 
 * Lösung durch Backtracking (nur kleinere Optimierungen)
 **/
class Test {

        //Diese Liste von Quadratzahlen ist nur fÃr eine Schnellere Suche
        List<Integer> quadratZahlen = new ArrayList<Integer>();


        //Sucht die nÃchst kleinere Quadratzahl zu n
        //und gibt den Index fÃr obige Liste zurÃck
        int findLargestSquare(int n)
        {
                //Ist die Zahl schon in der Liste?
                if ((quadratZahlen.size() > 0) && (quadratZahlen.get(quadratZahlen.size()-1) > n))
                        {
                        //Suche (binÃre Suche):
                        if (n == 1)
                                return 0;
                        int low = 0;
                        int high = quadratZahlen.size()-1;
                        int mid = (low + high)/2;

                        while (high - low > 1)
                                {
                                int no = quadratZahlen.get(mid);
                                if (no == n)
                                        return mid;
                                if (no > n)
                                        high = mid;
                                else low = mid;
                                mid = (low + high)/2;
                                }
                        return low;
                        }
                //Nein, Liste verlÃngern:
                for (int i = quadratZahlen.size(); (i+1)*(i +1)< n; i++)
                        quadratZahlen.add((i+1)*(i+1));
                return quadratZahlen.size()-1;
        }

        /**
         * Hiermit wird die Zerlegung durchgefÃhrt:
         * @param n Die zu zerlegende Zahl
         * @param max Die gröÃ
         *      darf, um mehrfach die gleiche Lösung zu vermeiden
         * @return niemals null, eine Liste mit allen benötigten Zahlen (die GröÃ
         * @throws Exception Wenn einer der Parameter kleiner als 0 ist
         **/
        List<Integer> zerlegen(int n, int max) throws Exception
        {
        //Hier ein paar patologische FÃlle abprÃfen
        if (n == 0) //Ergebniss gefunden ...
                return new ArrayList<Integer>();

        //Welcher Depp gibt negative Zahlen an???
        if ((n < 0) || (max < 0))
                throw new Exception("Irgendwas ist schief gegangen ...");

        //Es macht nur Sinn nach Zahlen zu suchen, die auch kleiner
        //als die Zielzahl sind ...
        if (max > n)
                max = n;

        //Wer alles etwas gesprÃchiger möchte:
        //System.out.println("Versuche: "+n+" gröÃ

        //Sonderfall: nur noch die Zahl 1 erlaubt
        if (max == 1)
                {
                ArrayList<Integer> res = new ArrayList<Integer>();
                for (int i = 0; i < n; i++)
                        res.add(1);
                return res;
                }

        //GröÃ
        int idx = findLargestSquare(max);

        List<Integer> result = null;

        //Jetzt diese Zahl, und alle kleineren probieren, 
        //so dass das gewÃnschte Ergebniss rauskommt
        for (int i = idx; i >= 0; i--)
                {
                //Wenn es eine Lösung gibt, die mit weniger Zahlen auskommt, als
                //mit der Zahl i minimal notwenidig wÃren, ist eine 
                //Lösung gefunden
                if ((result != null) && (n/quadratZahlen.get(i) > result.size()))
                        return result;

                //Zerlegen des Rests:
                List<Integer> res = zerlegen(n - quadratZahlen.get(i), quadratZahlen.get(i));

                //Wenn Besser als vorherige Versuche, diese Variante verwenden:
                if ((result == null) || (res.size() + 1 < result.size()))
                        {
                        res.add(quadratZahlen.get(i));
                        result = res;
                        }
                }
        return result;
        }

        /**
         * Das Programm braucht als einigen Parameter, die zu zerlegende Zahl, und gibt eine 
         * Meldung aus, die die Zerlegung darstellt
         **/
        public static void main(String [] args) throws Exception
        {
        //Wenn kein Parameter, dann Hinweis ausgeben
        if (args.length < 1)
        {
        System.out.println("Um eine Zahl zu zerlegen, bitte dieses Programm mit dieser Zahl als Parameter aufrufen");
        return;
        }

        //Zahl lesen:
        int no = Integer.parseInt(args[0]);

        //Zahl zerlegen:
        List <Integer> result = new Test().zerlegen(no,no);

        //Und ausgeben:
        System.out.println("Die Zerlegung lautet: "+result);
        }
}

docsnyder

#!/usr/bin/perl

use warnings;
use strict;

my($min) = my($n) = shift;
my(@vals, @arr, @res, %sums);

map { my($rt)=sqrt($_); push(@vals, $_) if ( $rt == int($rt) ) } (reverse(1..$n) );

sub partition {
  if ( ($_[0] >= 0) && (@arr <= $min) ) {
    if ( ! $_[0] ) {
      push(@{$res[$min=@arr]}, join('+', sort { $b <=> $a } @arr) . "\n");
    }
    else { map { push(@arr, $_); partition($_[0]-$_); pop(@arr) } @vals }
  }
}

partition($n);

map { print if ( ! $sums{$_}++ ) } @{$res[$min]};

Ishka

#!/usr/bin/perl

use strict;
use warnings;
use Math::BigInt lib => 'GMP';

my $zahl = $ARGV[0];

die "Kann nur eine positive Ganzzahl als Summe von Quadraten darstellen.\n"
  unless $zahl =~ m#^\d+$#;

print quad4($zahl), "\n";
exit;

sub quad4
{    # stelle eine gegebene Zahl als Summe von 4 oder weniger Quadratzahlen dar
    my $i = new Math::BigInt( $_[0] );
    return "0" if 0 == $i;
    if ( zahlbraucht4($i) ) {
        my $weg = wurzel($i);
        while ( zahlbraucht4( $i - $weg * $weg ) ) { $weg-- }
        $weg *= $weg;
        return "$weg+" . quad3( $i - $weg, 1 );
    }
    else { return quad3($i) }
}

sub quad3
{    # versuche die Zahl in 3 oder weniger Quadratzahlen darzustellen
    my $i   = new Math::BigInt( $_[0] );
    my $qua = wurzel($i);
    unless ( $_[1] ) {
        return $i if $qua * $qua == $i;    # Fall: 1 Quadratzahl
        my $j = quad2($i);                 # Fall: 2 Quadratzahlen
        return $j if $j;
    }
    my $r  = undef;
    my $rq = undef;
    my $t  = undef;
    while (1) {
        $r = $i - $qua * $qua;
        $t = quad2($r);
        if ($t) { $qua *= $qua; return "$t+$qua" }
        $qua--;
    }
}

sub quad2
{    # versuche die Zahl als genau 2 Quadratzahlen darzustellen
    my $i   = new Math::BigInt( $_[0] );
    my $qua = wurzel($i);
    my $r   = undef;
    my $rq  = undef;
    while ( $qua > 0 ) {
        $r  = $i - $qua * $qua;
        $rq = wurzel($r);
        if ( $rq * $rq == $r ) { $qua *= $qua; return "$qua+$r" }
        $qua--;
    }
    return undef;
}

sub zahlbraucht4
{   # kann die Zahl nur durch vier Quadrate dargestellt werden?
    my $was = new Math::BigInt( $_[0] );

    my $ge = 0;
    while ( not( $was % 2 ) ) {
        $ge++;
        $was /= 2;
    }

    if   ( not( $ge % 2 ) && 7 == $was % 8 ) { return 1 }
    else                                     { return 0 }
}

sub wurzel
{    # Die Wurzelimplementation von Math::BigInt ist auf manchen Systemen kaputt
    my $von     = $_[0];
    my $schritt = 1;
    until ( $schritt * $schritt <= $von && ( $schritt + 1 ) * ( $schritt + 1 ) > $von) {
        $schritt = ( $schritt + $von / $schritt ) / 2;
    }
    return $schritt;
}

Golflösung

perl -le '$*=pop;$*[$u=0]++,$h=join"+",map{$*[$u]=$*[$u+1]++if$_>$*;$u++;$_*$_}@*while$*-eval$h;print$h||0'

topeg

#!/usr/bin/perl

use strict;
use warnings;


sub quadsum($)
{
 my $zahl=shift(@_);
 my @o;
 for my $c (2..int($zahl**.5))
 {
  my @l;
  my $z=$zahl;
  for (grep{$_**=2}reverse(1..$c))
  {
   if($z>=$_)
   {
    $z-=$_;
    push(@l,$_);
    redo;
   }
   last if($z<=0);
  }
  push(@o,\@l);
 }
 return join('+',@{(sort{@$a<=>@$b}@o)[0]});
}


print quadsum(shift(@ARGV) or 42)."\n";

Vayu

#!/usr/bin/perl
# written by Ben Herfurth

use strict;
use warnings;

my $zahl = $ARGV[0];
my $zahl2 = $zahl;
my @zahlen = computeSquares();

$zahl = $ARGV[0];
if(odd($zahl/2)) {
   $zahl2 = ($zahl/2)-0.5; 
} else {
   $zahl2 = $zahl/2;
}
my @zahlen1 = computeSquares();

if ($#zahlen < $#zahlen1) {
   printArray(@zahlen);
} else {
   printArray(@zahlen1);
}

sub odd {
   my $odd = shift;
   if($odd =~ /\./) {
      return 1;
   }
}

sub printArray {
   foreach my $i (0..$#_) {
      print "+" if $i > 0;
      print $_[$i];
   }
}

sub computeSquares {
   my @ar;
   while($zahl) {
      if(sqrt($zahl2) !~ /\./) {
         $zahl -= $zahl2;
         push @ar, $zahl2;
         $zahl2 = $zahl;
         next;
      }
      $zahl2--;
   }
   return @ar;
}

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