Среднее число из 3 длинных целых чисел

Ответ 1

Этот код будет работать, но это не так.

Сначала он делит все три значения (он накладывает значения, поэтому вы теряете "остаток" ), а затем делит остаток:

long n = x / 3
         + y / 3
         + z / 3
         + ( x % 3
             + y % 3
             + z % 3
           ) / 3

Обратите внимание, что приведенный выше пример не всегда работает должным образом при наличии одного или нескольких отрицательных значений.

Как обсуждалось с Улугбеком, поскольку число комментариев взломается ниже, вот текущее решение BEST как для положительных, так и для отрицательных значений.

Благодаря ответам и комментариям Улугбек Умиров, Джеймс С., KevinZ, Марк Ван Леувен, gnasher729, это текущая решение:

static long CalculateAverage(long x, long y, long z)
{
    return (x % 3 + y % 3 + z % 3 + 6) / 3 - 2
            + x / 3 + y / 3 + z / 3;
}

static long CalculateAverage(params long[] arr)
{
    int count = arr.Length;
    return (arr.Sum(n => n % count) + count * (count - 1)) / count - (count - 1)
           + arr.Sum(n => n / count);
}

Ответ 2

NB - Патрик уже дал отличный ответ. Расширяясь на этом, вы можете сделать общую версию для любого количества целых чисел, например:

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

long[] arr = { x, y, z };
var avg = arr.Select(i => i / arr.Length).Sum() 
        + arr.Select(i => i % arr.Length).Sum() / arr.Length;

Ответ 3

Патрик Хофман опубликовал отличное решение. Но при необходимости он может быть реализован несколькими другими способами. Использование алгоритма здесь У меня есть другое решение. Если он будет тщательно реализован, он может быть быстрее, чем несколько делений в системах с медленными аппаратными делителями. Его можно дополнительно оптимизировать, используя делить на константы технику из хакерского восторга

public class int128_t {
    private int H;
    private long L;

    public int128_t(int h, long l)
    {
        H = h;
        L = l;
    }

    public int128_t add(int128_t a)
    {
        int128_t s;
        s.L = L + a.L;
        s.H = H + a.H + (s.L < a.L);
        return b;
    }

    private int128_t rshift2()  // right shift 2
    {
        int128_t r;
        r.H = H >> 2;
        r.L = (L >> 2) | ((H & 0x03) << 62);
        return r;
    }

    public int128_t divideby3()
    {
        int128_t sum = {0, 0}, num = new int128_t(H, L);
        while (num.H || num.L > 3)
        {
            int128_t n_sar2 = num.rshift2();
            sum = add(n_sar2, sum);
            num = add(n_sar2, new int128_t(0, num.L & 3));
        }

        if (num.H == 0 && num.L == 3)
        {
            // sum = add(sum, 1);
            sum.L++;
            if (sum.L == 0) sum.H++;
        }
        return sum; 
    }
};

int128_t t = new int128_t(0, x);
t = t.add(new int128_t(0, y));
t = t.add(new int128_t(0, z));
t = t.divideby3();
long average = t.L;

В C/С++ на 64-битных платформах это намного проще с __int128

int64_t average = ((__int128)x + y + z)/3;

Ответ 4

Вы можете вычислить среднее значение чисел, основанное на различиях между числами, а не на использовании суммы.

Пусть говорят, что x - max, y - медиана, z - min (как у вас есть). Назовем их max, медианными и минимальными.

Условная проверка добавлена ​​в соответствии с комментарием @UlugbekUmirov:

long tmp = median + ((min - median) / 2);            //Average of min 2 values
if (median > 0) tmp = median + ((max - median) / 2); //Average of max 2 values
long mean;
if (min > 0) {
    mean = min + ((tmp - min) * (2.0 / 3)); //Average of all 3 values
} else if (median > 0) {
    mean = min;
    while (mean != tmp) {
        mean += 2;
        tmp--;
    }
} else if (max > 0) {
    mean = max;
    while (mean != tmp) {
        mean--;
        tmp += 2;
    }
} else {
    mean = max + ((tmp - max) * (2.0 / 3));
}

Ответ 5

Поскольку C использует разделение на основе пола, а не эвклидовое подразделение, легче вычислить правильно округленное среднее из трех значений без знака, чем три подписанных. Просто добавьте 0x8000000000000000UL к каждому номеру, прежде чем принимать значение без знака, вычтите его после принятия результата и используйте непроверенный откат до Int64, чтобы получить среднее значение.

Чтобы вычислить значение беззнакового среднего, вычислите сумму верхних 32 бит трех значений. Затем вычислите сумму нижних 32 битов трех значений плюс сумму сверху, плюс одну [плюс, чтобы получить округленный результат]. Среднее будет 0x55555555 умножить на первую сумму плюс одну треть второго.

Производительность на 32-битных процессорах может быть увеличена за счет создания трех "суммарных" значений, каждая из которых имеет длину 32 бита, так что конечный результат равен ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; возможно, это будет еще больше улучшено путем замены sumL/3 на ((sumL * 0x55555556UL) >> 32), хотя последнее будет зависеть от оптимизатора JIT [он может знать, как заменить деление на 3 с помощью умножения, и его код может быть фактически более эффективным, чем явная операция умножения].

Ответ 6

Можно использовать тот факт, что вы можете записать каждое из чисел как y = ax + b, где x является константой. Каждый a будет y / x (целая часть этого деления). Каждое b будет y % x (остальное/по модулю этого деления). Если вы выберете эту константу разумным способом, например, выбрав квадратный корень из максимального числа в качестве константы, вы можете получить среднее число x без проблем с переполнением.

Среднее значение произвольного списка чисел можно найти, найдя:

( ( sum( all A ) / length ) * constant ) + 
( ( sum( all A ) % length ) * constant / length) +
( ( sum( all B ) / length )

где % обозначает по модулю, а / обозначает "целую" часть деления.

Программа будет выглядеть примерно так:

class Program
{
    static void Main()
    {
        List<long> list = new List<long>();
        list.Add( long.MaxValue );
        list.Add( long.MaxValue - 1 );
        list.Add( long.MaxValue - 2 );

        long sumA = 0, sumB = 0;
        long res1, res2, res3;
        //You should calculate the following dynamically
        long constant = 1753413056;

        foreach (long num in list)
        {
            sumA += num / constant;
            sumB += num % constant;
        }

        res1 = (sumA / list.Count) * constant;
        res2 = ((sumA % list.Count) * constant) / list.Count;
        res3 = sumB / list.Count;

        Console.WriteLine( res1 + res2 + res3 );
    }
}

Ответ 7

Исправление Patrick Hofman с исправлением supercat, я даю вам следующее:

static Int64 Avg3 ( Int64 x, Int64 y, Int64 z )
{
    UInt64 flag = 1ul << 63;
    UInt64 x_ = flag ^ (UInt64) x;
    UInt64 y_ = flag ^ (UInt64) y;
    UInt64 z_ = flag ^ (UInt64) z;
    UInt64 quotient = x_ / 3ul + y_ / 3ul + z_ / 3ul
        + ( x_ % 3ul + y_ % 3ul + z_ % 3ul ) / 3ul;
    return (Int64) (quotient ^ flag);
}

И случай элемента N:

static Int64 AvgN ( params Int64 [ ] args )
{
    UInt64 length = (UInt64) args.Length;
    UInt64 flag = 1ul << 63;
    UInt64 quotient_sum = 0;
    UInt64 remainder_sum = 0;
    foreach ( Int64 item in args )
    {
        UInt64 uitem = flag ^ (UInt64) item;
        quotient_sum += uitem / length;
        remainder_sum += uitem % length;
    }

    return (Int64) ( flag ^ ( quotient_sum + remainder_sum / length ) );
}

Это всегда дает слово() среднего значения и исключает все возможные случаи ребер.

Ответ 8

Если вы знаете, что у вас есть N значений, можете ли вы просто разделить каждое значение на N и суммировать их вместе?

long GetAverage(long* arrayVals, int n)
{
    long avg = 0;
    long rem = 0;

    for(int i=0; i<n; ++i)
    {
        avg += arrayVals[i] / n;
        rem += arrayVals[i] % n;
    }

    return avg + (rem / n);
}

Ответ 9

Эта функция вычисляет результат в двух делениях. Он должен хорошо делиться на другие делители и размеры слов.

Он работает, вычисляя результат сложения с двойным словом, а затем разрабатывая разделение.

Int64 average(Int64 a, Int64 b, Int64 c) {
    // constants: 0x10000000000000000 div/mod 3
    const Int64 hdiv3 = UInt64(-3) / 3 + 1;
    const Int64 hmod3 = UInt64(-3) % 3;

    // compute the signed double-word addition result in hi:lo
    UInt64 lo = a; Int64 hi = a>=0 ? 0 : -1;
    lo += b; hi += b>=0 ? lo<b : -(lo>=UInt64(b));
    lo += c; hi += c>=0 ? lo<c : -(lo>=UInt64(c));

    // divide, do a correction when high/low modulos add up
    return hi>=0 ? lo/3 + hi*hdiv3 + (lo%3 + hi*hmod3)/3
                 : lo/3+1 + hi*hdiv3 + Int64(lo%3-3 + hi*hmod3)/3;
}

Ответ 10

Math

(x + y + z) / 3 = x/3 + y/3 + z/3

(a[1] + a[2] + .. + a[k]) / k = a[1]/k + a[2]/k + .. + a[k]/k

код

long calculateAverage (long a [])
{
    double average = 0;

    foreach (long x in a)
        average += (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

    return Convert.ToInt64(Math.Round(average));
}

long calculateAverage_Safe (long a [])
{
    double average = 0;
    double b = 0;

    foreach (long x in a)
    {
        b = (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

        if (b >= (Convert.ToDouble(long.MaxValue)-average))
            throw new OverflowException ();

        average += b;
    }

    return Convert.ToInt64(Math.Round(average));
}

Ответ 11

Я также попробовал это и придумал более быстрое решение (хотя только в 3 ~ 4 раза). Он использует одно разделение

public static long avg(long a, long b, long c) {
    final long quarterSum = (a>>2) + (b>>2) + (c>>2);
    final long lowSum = (a&3) + (b&3) + (c&3);
    final long twelfth = quarterSum / 3;
    final long quarterRemainder = quarterSum - 3*twelfth;
    final long adjustment = smallDiv3(lowSum + 4*quarterRemainder);
    return 4*twelfth + adjustment;
}

где smallDiv3 является делением на 3 с использованием умножения и работает только для небольших аргументов

private static long smallDiv3(long n) {
    assert -30 <= n && n <= 30;
    // Constants found rather experimentally.
    return (64/3*n + 10) >> 6;
}

Вот весь код, включая тест и контрольную отметку, результаты не впечатляют.

Ответ 12

Попробуйте следующее:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);