0

我目前正在处理这个（代码高尔夫）挑战，我很难结合给定整数数量n和十进制总和的四个要求s（考虑到我们应该支持的范围：1 <= n <= 10和0 <= s <= n):

  1. 项目n都应该是随机的，并且是均匀划分的
  2. 所有项目的总和必须等于s
  3. 所有项目均不得高于 1.0
  4. 代码必须在每 1 秒内运行n <= 10，无论s

基于这个 Stackoverflow 答案，我知道如何在给定范围内统一划分项目。例如，使用，我可以在 range 中n=5, s=4.5创建一个项目列表，并带有一个额外的前导和尾随。然后我可以计算所有差异（因此所有差异的总和将等于）。这是一个可能的实现：n-1 = 4[0, 1.5]01.5s=4.5

int n=5; double s=4.5;

double[] randomValues = new double[n+1];
randomValues[n] = s;
for(int i=1; i<n; i++)
  randomValues[i] = Math.random()*s;
java.util.Arrays.sort(randomValues);
System.out.println("Random values:\n"+java.util.Arrays.toString(randomValues)+"\n");

double[] result = new double[n];
for(int i=0; i<n; i++)
  result[i] = Math.abs(randomValues[i]-randomValues[i+1]);
System.out.println("Result values:\n"+java.util.Arrays.toString(result)+"\n");

double resultSum = java.util.Arrays.stream(result).sum();
System.out.println("Sum: "+resultSum);
System.out.println("Is the result sum correct? "+(s==resultSum?"yes":"no"));

示例输出：

Random values:
[0.0, 1.3019797415889383, 1.9575834386978177, 2.0417721898726313, 4.109698885802333, 4.5]

Result values:
[1.3019797415889383, 0.6556036971088794, 0.08418875117481361, 2.0679266959297014, 0.39030111419766733]

Sum: 4.5
Is the result sum correct? yes

在线尝试。

以上符合上述四个要求中的三个（1、2 和 4）。但是，不是3。

我可以在它周围环绕一个循环，只要result-array 中的一项仍然大于 1，它就会继续：

for(boolean flag=true; flag; ){
  ... // Same code as above

  flag=false;
  for(double d:result)
    if(d>1)
      flag=true;
}

这对大多数人来说仍然相对较快，n并且s：
在线尝试（打印被删除/移动以不溢出控制台）

但是，最后四个//禁用的测试用例，预期随机值的平均值接近1，耗时太长（甚至在 TIO 上 60 秒后超时）。

所以这就是我的问题主要涉及的地方。如何像我一样统一划分值，并记住[0, 1]每个值的范围，并有良好的表现？在顶部的链接代码高尔夫挑战中，我看到了其他编程语言（如 Python 或 JavaScript）的一些工作示例，但是将更长的代码高尔夫挑战从一种编程语言移植到另一种编程语言通常不是很简单。

4

1 回答 1

0

好的，根据已经给出的 JavaScript 答案找到了解决方案。如果s*s>n我更改s为n-s并设置一个要使用的标志，1-diff而不是diff在结果数组中使用。

所以总的来说它变成：

boolean inversedFlag = 2*s>n;
double S = s;
if(inversedFlag)
  S = n-S;

double[] result = new double[n];

for(boolean flag=true; flag; ){
  double[] randomValues = new double[n+1];
  randomValues[n] = S;
  for(int i=1; i<n; i++)
    randomValues[i] = Math.random()*S;
  java.util.Arrays.sort(randomValues);

  for(int i=0; i<n; i++){
    double diff = Math.abs(randomValues[i]-randomValues[i+1]);
    result[i] = inversedFlag ? 1-diff : diff;
  }

  flag=false;
  for(double d:result)
    flag |= d>1;
}

System.out.println("Result values:\n"+java.util.Arrays.toString(result)+"\n");

double resultSum = java.util.Arrays.stream(result).sum();
System.out.println("Sum: "+resultSum );
System.out.println("Is the result sum correct? "+(s==resultSum?"yes":"no"));

System.out.println();
System.out.println("--------------------------------------------------");
System.out.println();

在线尝试。

现在我只需要再次打高尔夫球，但这与这个 Stackoverflow 问题无关。:)

于 2018-05-19T11:13:11.653 回答