check out my new blog at gmarik.info/blog

Tuesday, May 03, 2005

ShortestSquareSum

Yepp, another task solved...Cool!


<?php
/*
* @Algorithm : Shortest Sum of Squares
* @Author : mrix
* @Date : 30.04.2005
* @Ver : 1.1
*
* @Remark : not the most efficient, might be improoved
*/

/*
* $N - target numer
* @returns : stack of subcalculations
*/
function searchSSS($N){
if (1 == $N) return array(1);
$n = (int)sqrt($N);
if ($N == $n*$n) return array($n);

$solution = array();

$k = $n;
$r = $n;
while ($k > (int)$n/2){

$result = searchSSS($N - $k*$k);

if (0 == count($solution) || count($solution) > count($result)){
$solution = $result;
$r = $k;
}

if (count($solution) < start =" time();">

0 Comments:

Post a Comment

<< Home