Square into Squares. 大平方数转小平方数之和

问题描述:像是把一个大的正方形分割成几个小的正方形块一样,把一个数分成由几个比他小的数字,要求其平方和相等。如把 50 分成 “1,3,5,8,49”。
额外要求:
1、要求数字序列严格递增:比如 “1,1,4,9,49” 就不符合要求。
2、要求返回具有最大可能值的结果:比如11可以分为[1,2,4,10]和[2,6,9],则返回[1,2,4,10]。

思路1:解题步骤可以分为两步,拿50举例
1、从50-1开始往下循环,获取“最大的数”。如果49的组合不成立,则尝试48,以此类推。
2、将剩余部分再继续拆分。

class Sq2Squares {
  public static function decompose($n) {
    for($i=$n-1;$i>0;$i--) {
      $array = [];
      $sum = pow($n,2) - pow($i,2);
      //将数插到数组头部,实现输出形式为递增
      array_unshift($array,$i);
      //剩余部分循环的开始
      $start = intval(sqrt($sum));
      while($start>0) {
        $reset = 0;
        for($j=$start;$j>0;$j--) {
          if($sum - pow($j,2) > 0 && $j < $array[0]) {
            $sum -= pow($j,2);
            array_unshift($array,$j);
          } elseif ($sum - pow($j,2) == 0 && $j < $array[0]) {
            array_unshift($array,$j);
            return $array;
          }
          $reset = 1;
        }
        //假设不成立,回滚
        if($reset == 1) {
          $array = [];
          $sum = pow($n,2) - pow($i,2);
          array_unshift($array,$i);
          $start--;
        }
      }
    }
    return null;
  }
}

思路2:使用递归函数。分析可得,每个小数至少比上一个大数小1,每次都是以大数的平方减去小数的平方和为判断。

class Sq2Squares {
  public static $array = [];
  public static function getLast($last,$rest) {
    //若$rest为0,则递归成立,将数添加到数组中;若小于0,则失败,继续循环。
    if($rest <= 0) return $rest == 0;
    for($i = $last - 1; $i > 0; $i--) {
      //如果递归成立,将数添加到数组中
      if(self::getLast($i, $rest - $i * $i)) {
        array_push(self::$array,$i);
        return true;
      }
    }
    return false;
  }
  public static function decompose($n) {
    self::$array = [];
    return self::getLast($n, $n * $n) ? self::$array : null;
  }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注