1

我最近在休息时间一直在玩 HackerRank，在解决这个问题时遇到了一些麻烦：https ://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers有效。

问题陈述：给定两个整数X和N，找出表示为唯一自然数X的幂和的方式数。N

示例： X = 10，N = 2

只有一种方法可以使用 10 以下的2的幂得到 10 ，那就是1^2 + 3^2

我的方法

我知道这个问题可能存在一个很好的、优雅的重现；但不幸的是我找不到，所以我开始考虑其他方法。我决定收集一系列数字，[1,Z]其中Z是小于X的最大数字，当提升到N次方时。所以对于上面的例子，我只考虑[1,2,3]因为4^2 > 10，因此不能是总和为 10 的（正）数字的一部分。在收集了这个数字范围后，我将它们全部提升到N次方，然后找到所有子集的排列这个清单。所以[1,2,3]我发现[[1],[4],[9],[1,4],[1,9],[4,9],[1,4,9]]，而不是针对大初始数字范围的一系列操作（我的解决方案在最后两个hackerrank测试中超时）。最后一步是计算总和为X的子列表。

解决方案

object Solution {
    def numberOfWays(X : Int, N : Int) : Int = {
        def candidates(num : Int) : List[List[Int]] = {
            if( Math.pow(num, N).toInt > X ) 
                List.range(1, num).map(
                    l => Math.pow(l, N).toInt
                ).toSet[Int].subsets.map(_.toList).toList
            else 
                candidates(num+1)
        }
        candidates(1).count(l => l.sum == X)
    }

    def main(args: Array[String]) {
       println(numberOfWays(readInt(),readInt()))
    }
}

有没有人遇到过这个问题？如果是这样，是否有更优雅的解决方案？

4

3 回答 3

0

这可以被认为是一个动态规划问题。我仍然对动态编程问题进行命令式推理，因为那是我被教导的方式，但这可能会成为功能性的。

A.  Make an array A of length X with type parameter Integer.
B.  Iterate over i from 1 to Nth root of X.  For all i, set A[i^N - 1] = 1.
C.  Iterate over j from 0 until X.  In an inner loop, iterate over k from 0 to (X + 1) / 2.
    A[j] += A[k] * A[x - k]
D.  A[X - 1]

通过跟踪哪些索引不重要，可以稍微提高效率，但效率并不高。

于 2013-10-15T08:52:04.630 回答
0

在你建立你的正方形列表之后，你会留下我认为的一种分区问题，称为子集和问题。这是一个古老的 NP 完全问题。所以你的第一个问题的答案是“是”，第二个问题的答案在链接中给出。

于 2013-10-14T19:57:09.440 回答
0 
def numberOfWays(X: Int, N: Int): Int = {

    def powerSumHelper(sum: Int, maximum: Int): Int = sum match {
      case x if x < 1 => 0
      case _ => {
        val limit = scala.math.min(maximum, scala.math.floor(scala.math.pow(sum, 1.0 / N)).toInt)
        (limit to 1 by -1).map(x => {
          val y = scala.math.pow(x, N).toInt
          if (y == sum) 1 else powerSumHelper(sum - y, x - 1)
        }).sum
      }
    }

    powerSumHelper(X, Integer.MAX_VALUE)
  }
于 2017-07-14T02:30:04.187 回答