4

我尝试打代码打高尔夫球。

找到 的最小值∑W_i*|X-X_i|的问题减少到找到权重列表的加权中位数x[i]（w[i]定义见下文）。你将如何用一个最短、最简单、最漂亮的程序来做到这一点？

这是我的代码最初的样子（解释在问题的答案中，简短版本作为下面的答案之一发布）。

    #define zero(x) ( abs(x) < 1e-10 )  /* because == doesn't work for floats */

    float sum = 0;
    int i;

    for (i = 0; i < n; i++) 
         sum += w[i];
    while (sum > 0) 
         sum -= 2*w[--i];

    right = x[i]             // the rightmost minimum point
    left  = ( zero(sum) && zero(w[i]-w[i-1]) ) ? x[i-1] : right;
    answer = (left + right) / 2;

i（实际上，当您看到变量并重用时，它已经被大量优化sum）

规则

浮点数和整数：不同的语言有不同的浮点算术标准，所以我将问题重新表述为整数，x[i]如果你愿意，你可以返回两倍的答案值（总是整数）。您可以返回、打印或将答案分配给变量。w[i]

加权中位数的定义和说明：

  • x[i]长度排序数组的中位数n是x[n/2]或(x[n/2-1/2]+x[n/2+1/2])/2取决于n是奇数还是偶数
  • 未排序数组的中位数是排序后数组的中位数（是的，但我们的数组已排序）
  • x[i]具有整数正权重的加权中位数w[i]定义为较大数组的中位数，其中每次出现的x[i]都已更改为w[i]的出现x[i]。

我希望看到什么

询问的原因之一是我假设最合适的语言将使用 lambda 进行简单的数组求和和迭代。我认为函数式语言可能是合理的，但我不确定——所以这是问题的一部分。我希望看到类似的东西

    // standard function   add  :=  (a,b) :-> a + b 
    myreduce := w.reduce  
        with:  add  
        until: (value) :-> 2*value >= (w.reduce with:add)
    answer = x [myreduce  from:Begin] + x [myreduce  from:End]

不知道是否有任何语言可以实现并且实际上更短。

测试数据

static int n = 10;
for (int j = 0; j < n; j++) {
        w[j] = j + 1;
        x[j] = j;
}

答案：6 或 12。

static int n = 9;
int w[n], x[n] ;
for (int j = 0; j < n; j++) {
    w[j] = j + ((j<6) ? 1 : 0);
    x[j] = j + 1;
}

答案：6.5 或 13。

4

7 回答 7

5

Ĵ

继续并将其直接输入到解释器中。提示是三个空格，所以缩进的行是用户输入。

   m=:-:@+/@(((2*+/\)I.+/)"1@(,:(\:i.@#))@[{"0 1(,:(\:i.@#))@])

我在另一个答案中使用的测试数据：

   1 1 1 1 m 1 2 3 4
2.5
   1 1 2 1 m 1 2 3 4
3
   1 2 2 5 m 1 2 3 4
3.5
   1 2 2 6 m 1 2 3 4
4

添加到问题的测试数据：

   (>:,:[)i.10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8  9
   (>:m[)i.10
6
   (([+<&6),:>:)i.9
1 2 3 4 5 6 6 7 8
1 2 3 4 5 6 7 8 9
   (([+<&6)m>:)i.9
6.5

   i =: (2 * +/\) I. +/

第一个索引使得总和大于或等于累积总和的两倍。

   j =: ,: (\: i.@#)

列表及其相反。

   k =: i"1 @ j @ [

第一个索引使得- 见上文 -左参数及其相反。

   l =: k {"(0 1) j @ ]

这些索引分别从正确的参数和它的反向中提取。

   m =: -: @ +/ @ l

结果列表总和的一半。

于 2009-06-09T02:36:14.890 回答
3

所以，这就是我如何压缩自己的解决方案：，仍然留下一些空格：

    int s = 0, i = 0;
    for (; i < n; s += w[i++]) ;
    while ( (s -= 2*w[--i] ) > 0) ;
    a  =  x[i]  +  x[ !s && (w[i]==w[i-1]) ? i-1 : i ];
于 2009-06-08T21:26:26.153 回答
2

Haskell 代码，ungolfed：尝试合理的功能解决方案。

import Data.List (zip4)
import Data.Maybe (listToMaybe)

mid :: (Num a, Ord a) => [a] -> (Int, Bool)
mid w = (i, total == part && maybe False (l ==) r) where
    (i, l, r, part):_ = dropWhile less . zip4 [0..] w v $ map (2*) sums
    _:sums = scanl (+) 0 w; total = last sums; less (_,_,_,x) = x < total
    v = map Just w ++ repeat Nothing

wmedian :: (Num a, Ord a) => [a] -> [a] -> (a, Maybe a)
wmedian w x = (left, if rem then listToMaybe rest else Nothing) where
    (i, rem) = mid w; left:rest = drop i x

> w 中位数 [1,1,1,1] [1,2,3,4]
（2，就3）
> w 中位数 [1,1,2,1] [1,2,3,4]
（3，无）
> w 中位数 [1,2,2,5] [1,2,3,4]
（3，只有 4 个）
> w 中位数 [1,2,2,6] [1,2,3,4]
（4，无）

> w 中位数 [1..10] [0..9]
（6，无）
> wmedian ([1..6]++[6..8]) [1..9]
（6个，就7个）

我最初的 J 解决方案是对上述 Haskell 代码的直接翻译。

这是当前 J 代码的 Haskell 翻译：

{-# LANGUAGE ParallelListComp #-}
import Data.List (find); import Data.Maybe (fromJust)
w&x=foldr((+).fst.fromJust.find((>=sum w).snd))0[f.g(+)0$map
    (2*)w|f<-[zip x.tail,reverse.zip x]|g<-[scanl,scanr]]/2

是的……请不要写这样的代码。

> [1,1,1,1]&[1,2,3,4]
2.5
> [1,1,2,1]&[1,2,3,4]
3
> [1,2,2,5]&[1,2,3,4]
3.5
> [1,2,2,6]&[1,2,3,4]
4
> [1..10]&[0..9]
6
> ([1..6]++[6..8])&[1..9]
6.5
于 2009-06-08T22:58:08.950 回答
2

简短，并且做你所期望的。不是特别节省空间。

def f(l,i):
   x,y=[],sum(i)
   map(x.extend,([m]*n for m,n in zip(l,i)))
   return (x[y/2]+x[(y-1)/2])/2.

这是使用 itertools 的常量空间版本。它仍然必须迭代 sum(i)/2 次，因此它不会击败索引计算算法。

from itertools import *
def f(l,i):
   y=sum(i)-1
   return sum(islice(
       chain(*([m]*n for m,n in zip(l,i))),
       y/2,
       (y+1)/2+1
   ))/(y%2+1.)
于 2009-06-19T19:03:10.640 回答
1

Python：

a=sum([[X]*W for X,W in zip(x,w)],[]);l=len(a);a[l/2]+a[(l-1)/2]
于 2009-06-28T04:12:28.837 回答
0

像这样的东西？O(n) 运行时间。

for(int i = 0; i < x.length; i++)
{
sum += x[i] * w[i];
sums.push(sum);
}

median = sum/2;

for(int i = 0; i < array.length - 1; i++)
{
    if(median > sums[element] and median < sums[element+1]
         return x[i];
    if(median == sums[element])
         return (x[i] + x[i+1])/2
}

不确定如何获得中位数的两个答案，您的意思是 sum/2 是否完全等于边界？

编辑：查看您的格式化代码后，我的代码基本上做同样的事情，您想要更有效的方法吗？

EDIT2：搜索部分可以使用修改后的二进制搜索来完成，这会使其稍微快一些。

index = sums.length /2;
finalIndex = binarySearch(index);

int binarySearch(i)
{
    if(median > sums[i+1])
    {
        i += i/2
        return binarySearch(i);
    }
    else if(median < sums[i])
    {
        i -= i/2
        return binarySearch(i);
    }
    return i;
}

将不得不做一些检查以确保它不会在边缘情况下无限地继续下去。

于 2009-06-08T20:54:34.597 回答
-5

只是对您的代码的评论：我真的希望我不必维护它，除非您还编写了此处所需的所有单元测试:-)

当然，这与您的问题无关，但通常，“最短的编码方式”也是“最难维护的方式”。对于科学应用来说，它可能不是一个炫耀的东西。但对于 IT 应用程序来说，确实如此。

我觉得不得不说。祝一切顺利。

于 2009-06-08T20:49:41.423 回答