Определение максимального значения выражения (анти-сортировка)

#cpp #алгоритм

Дано число n. Далее задана последовательность n чисел. Определить 
максимальное значение этого выражения: 


  |M1 - M2| + |M2 - M3| + ... + |Mn-1 - Mn|.


Пример:  


  Ввод:  5 1 3 5 7 9
  
  Вывод: 22  
  
  Максимальное значение 22, так как:  
  
  |3 - 9| + |9 - 1| + |1 - 7| + |7 - 5| = 22


Мой пример решения  (иногда выдает не правильный ответ) 

Идея решения : Сначала я упорядочил массив методом пузырька.
Всего пар  ( |M1 - M2| , |M2 - M3|, ... , |Mn-1 + Mn| ) будет n-1. Если в выражении
раскрыть модуль, то: 

Если a >= b : |a - b| = a - b
Если a < b : |a - b| = b - a.

То есть возле каждого числа стоит + или -. Их равное количество и равняется n-1.
Каждое число используется в выражении дважды (кроме первого и последнего (M1, Mn)
). Чтобы сумма вышла максимальной возле больших чисел ставил +, возле меньших -.

#include 
#include 
using namespace std;

int main()
{
  int n,plus,minus;
  cin>>n;
  double s = n;
  plus = n-1;
  minus=n-1;
  int sum = 0;
  int arr[n];
  for(int i = 0; i < n; i++)
      {
          cin>>arr[i];
      }
  for(int i = 0; i < n-1; i++)
      {
          for(int j = 0; j < n-i-1; j++)
              {
                  if(arr[j]>arr[j+1])
                  swap(arr[j],arr[j+1]);
              }
      }

      for(int i = 0; i < n-round((s-1)/2+0.1); i++)
          {
              sum-=arr[i];
              minus--;
          }


      for(int i = 0; i < n; i++)
          {
              if(minus>0)
              {
                  sum-=arr[i];
                  minus--;
              }

              if(minus>0)
              {
                  sum-=arr[i];
                  minus--;
              }
          }
          for(int i = n-1; i >=0; i--)
          {
              if(plus>0)
              {
                  sum +=arr[i];
                  plus--;
              }

              if(plus>0)
              {
                  sum +=arr[i];
                  plus--;
              }
          }

          cout<

Ответы
Ответ 1

"Жадный" алгоритм, уверенности в оптимальности которого пока нет:


Сортируем значения по возрастанию
 
    M1, M2, ..., Mn
Обходим ("прыгаем") значения в порядке туда-сюда снаружи-к-центру:
 
    M1, Mn, M2, Mn-1, M3, Mn-2...
 
пока не придем в последнюю вершину M[n/2]
Из нее "прыгаем" в M1, тем самым замыкая цикл
Из полученного цикла обхода вершин удаляем самое короткое ребро, т.е. ребро (i, j)
с минимальным значением |Mi-Mj|. Это будет либо последний прыжок с шага 2, либо прыжок
с шага 3
Оставшаяся цепь дает максимальную сумму (предположительно) 




Однако алгоритм пока не верен. Если следовать той же самой интуиции, то нам надо
попробовать те же самые "прыжки", но начиная с последнего элемента массива. Например,
на входе { 2, 4, 5, 7, 9 } вышеприведенный алгоритм даст 

|5 - 2| + |2 - 9| + |9 - 4| + |4 - 7| = 18


в то время как начиная "прыжки" с последнего элемента мы можем получить

|5 - 9| + |9 - 2| + |2 - 7| + |7 - 4| = 19


Другими словами, рассмотреть вышеприведенным алгоритмом следует как отсортированный
по возрастанию набор чисел, так и отсортированный по убыванию. Есть подозрение, что
рассмотрев оба варианта и выбрав лучший из двух, мы все таки найдем максимум. 

(Интуиция и эксперимент подсказывают, что такое явление может наблюдаться только
на наборах с нечетным количеством элементов. Это, по-идее, должно быть несложно доказать.
Также, в случае нечетного количества элементов скорее всего есть критерий, позволяющий
заранее увидеть, какой из двух вариантов лучше, не прогоняя всего алгоритма. Но пока,
на всякий случай, будем честно проверять оба варианта всегда.)

Интенсивное тестирование в сравнении с переборным алгоритмом пока не выявило нарушений.



#include 
#include 
#include 
#include 

int max_sum(const int a[], int n)
{
  int w_sum = 0;

  int 
    j_last = n / 2, 
    i_last = j_last + (n % 2 == 0 ? -1 : +1);
  int
    w_last = std::abs(a[j_last] - a[i_last]), 
    w_closing = std::abs(a[j_last] - a[0]);

  bool plus = false;

  if (w_closing > w_last)
  {
    std::cout << "|" << a[j_last] << " - " << a[0] << "|";
    w_sum += w_closing; 
    plus = true;
  }

  for (int i = 0, step = n - 1, j = i + step; j != j_last; 
         i = j, step = -step - (step < 0) + (step > 0), j = i + step)
  {
    std::cout << (plus ? " + " : "") << "|" << a[i] << " - " << a[j] << "|";
    w_sum += std::abs(a[j] - a[i]); 
    plus = true;
  }

  if (w_closing <= w_last)
  {
    std::cout << (plus ? " + " : "") << "|" << a[i_last] << " - " << a[j_last] << "|";
    w_sum += w_last; 
  }

  std::cout << " = " << w_sum << std::endl;

  return w_sum;
}

int main()
{
  int a[] = { 2, 4, 5, 7, 9 };
  int n = std::size(a);

  std::sort(a, a + n);
  int sum1 = max_sum(a, n);

  std::reverse(a, a + n);
  int sum2 = max_sum(a, n);

  std::cout << "Best = " << std::max(sum1, sum2) << std::endl;
}


Ответ 2

ЧАСТНЫЕ СЛУЧАИ

В частных случаях решение можно получить перебором всех возможных комбинаций.



Программа (C#):

    public static int[] FactGen(int n)
    {
        int[] fact = new int[n + 1];

        fact[0] = 1;
        for (int i = 1; i < n + 1; i++)
            fact[i] = i * fact[i - 1];

        return fact;
    }

    public static int[] PermsGenerator(int[] arr, int num, int[] fact)
    {
        int i, j, f, newind, newnum, newval, size = arr.Length;
        int[] result = new int[size];

        Array.Copy(arr, result, size);
        for (i = 0, newnum = num; i < size - 1; i++)
        {
            newind = newnum / (f = fact[size - 1 - i]);
            newnum = newnum - newind * f;
            newval = result[i + newind];
            for (j = i + newind; j > i; j--)
                result[j] = result[j - 1];
            result[i] = newval;
        }

        return result;
    }

    public static int SumAbs(int[] arr)
    {
        int sum = 0, prev = arr[0];

        foreach (int value in arr)
        {
            sum += Math.Abs(value - prev);
            prev = value;
        }

        return sum;
    }

    public static int[] MaxArr(int[] arr, bool detprn)
    {
        int i, j, sum, smax = -1, size = arr.Length;
        int[] perm, result = new int[size], fact = FactGen(size),
            sorted = new int[size], empire = new int[size];

        Array.Copy(arr, sorted, size);
        Array.Sort(sorted);
        for (i = 0; i < fact[size]; i++)
        {
            if ((sum = SumAbs(perm = PermsGenerator(sorted, i, fact))) > smax) {
                smax = sum;
                result = perm;
            }
            if (detprn)
            {
                Console.Write("\nПерестановка:  ");
                foreach (int value in perm)
                    Console.Write(value + "  ");
                Console.Write("    Сумма:  {0}   Максимальная сумма: {1}", sum, smax);
            }
        }
        Console.Write("\nИсходная выборка:  ");
        foreach (int value in arr)
            Console.Write(value + "  ");
        Console.Write("\nОтсортированная выборка:  ");
        foreach (int value in sorted)
            Console.Write(value + "  ");
        Console.Write("\nЛучшая перестановка:  ");
        foreach (int value in result)
            Console.Write(value + "  ");
        Console.WriteLine("\nМаксимальная сумма:  {0}", smax);
        empire[0] = sorted[i = size / 2 - 1];
        empire[1] = sorted[i + 2];
        empire[size - 1] = sorted[i + 1];
        for (i = 2, j = 0; i < size - 1; i++, j = (size) - 1 + ((i + 1) & 1) - j)
            empire[i] = sorted[j];
        Console.Write("Эвристический алгоритм:  ");
        foreach (int value in empire)
            Console.Write(value + "  ");
        Console.WriteLine("\nСумма:  {0}", SumAbs(empire));
        return result;
    }

    static void Main(string[] args)
    {
        bool binc;
        int i, j, n, nmax = 10;
        int[] arr;
        Random rand = new Random();

        MaxArr(new int[] { 1, 2, 3, 4 }, false);
        MaxArr(new int[] { 1, 2, 3, 4, 5 }, false);
        for (n = 6; n < nmax + 1; n++)
        {
            arr = new int[n];
            for (i = 0; i < n;)
            {
                arr[i] = rand.Next(1, 5 * n);
                binc = true;
                for (j = 0; j < i; j++)
                    binc &= (arr[i] != arr[j]);
                if (binc)
                    i++;
            }
            MaxArr(arr, false);
        }
    }




Результаты:


Исходная выборка:  1  2  3  4
Отсортированная выборка:  1  2  3  4
Лучшая перестановка:  2  4  1  3
Максимальная сумма:  7
Эвристический алгоритм:  2  4  1  3
Сумма:  7

Исходная выборка:  1  2  3  4  5
Отсортированная выборка:  1  2  3  4  5
Лучшая перестановка:  2  4  1  5  3
Максимальная сумма:  11
Эвристический алгоритм:  2  4  1  5  3
Сумма:  11

Исходная выборка:  26  10  21  4  27  5
Отсортированная выборка:  4  5  10  21  26  27
Лучшая перестановка:  10  26  4  27  5  21
Максимальная сумма:  99
Эвристический алгоритм:  10  26  4  27  5  21
Сумма:  99

Исходная выборка:  34  3  32  16  28  27  26
Отсортированная выборка:  3  16  26  27  28  32  34
Лучшая перестановка:  26  28  3  32  16  34  27
Максимальная сумма:  97
Эвристический алгоритм:  26  28  3  34  16  32  27
Сумма:  97

Исходная выборка:  27  3  34  38  18  29  31  39
Отсортированная выборка:  3  18  27  29  31  34  38  39
Лучшая перестановка:  29  34  3  38  18  39  27  31
Максимальная сумма:  128
Эвристический алгоритм:  29  34  3  39  18  38  27  31
Сумма:  128

Исходная выборка:  40  27  4  9  32  35  41  39  2
Отсортированная выборка:  2  4  9  27  32  35  39  40  41
Лучшая перестановка:  32  2  39  4  40  9  41  27  35
Максимальная сумма:  223
Эвристический алгоритм:  27  35  2  41  4  40  9  39  32
Сумма:  221

Исходная выборка:  41  35  45  27  34  33  18  24  16  25
Отсортированная выборка:  16  18  24  25  27  33  34  35  41  45
Лучшая перестановка:  27  34  16  35  18  41  24  45  25  33
Максимальная сумма:  150
Эвристический алгоритм:  27  34  16  45  18  41  24  35  25  33
Сумма:  150


Таким образом:


Нашлась более удачная комбинация для исходного массива.
Контрпример для эвристического алгоритма нашёлся не сразу.




ОБЩЕЕ РЕШЕНИЕ (10.02.2018)

Пусть
a = {a0 = M1, a1 = M2, …, an-2 = Mn-1, an-1 = Mn} -
 исходная последовательность,
b = {b0, b1, …, bn-2, bn-1} -та же последовательность в порядке возрастания,
с = {c0, c1, …, cn-2, cn-1} -требуемая последовательность.

Рассмотрим по отдельности случаи чётного и нечётного n.



Случай n = 2k

S(a) = Sц(a)  - |an-1 - a0|, где
Sцa) = |a0 - a1| + |a1 - a2| + … + |an-3 - an-2| + |an-2 - an-1| + |an-1 - a0|.

Sц(a) - это алгебраическая сумма, которая содержит каждый исходный элемент ai дважды,
и её максимальное значение равно

Sц_max = 2∑i = 0, …, k-1 (hi - bi),
где hi = bi+k, i = 0…k-1.

Это значение достигается в двух вариантах перестановок:
1) c2i ∈ h (все наибольшие элементы имеют чётные индексы);
2) c2i + 1 ∈ h (все наибольшие элементы имеют нечётные индексы).

В то же время, минимум |an-1 - a0| = bk - bk-1 достигается при размещении пары медианных
элементов на краях последовательности c.

Максимум суммы S равен
Smax = 2∑i = 0, …, k-2 (bi+k - bi) + bk-1 - bk, или

Smax = 2∑i = 0, …, k-2 (bn-1-i - bi) + bn-k - bk-1,

и достигается в тех случаях, когда последовательность с содержит наибольшие элементы
в шахматном порядке, причём медианные элементы bk-1 и bk находятся на краях последовательности.
Количество таких перестановок при попарно различных ai составляет 2(k-1)!2.



Случай n = 2k+1

Аналогичное рассмотрение показывает, что максимум S равен

Smax = 2∑i=0…k-2 (bk+2+i - bk) + bk+1 - bk-1 + max (bk+1 - bk, bk - bk-1), или

Smax = 2∑i=0…k-2 (bn-1-i - bi) + bn-k - bk-1 + max (bk+1 - bk, bk - bk-1),

и достигается в тех случаях, когда элементы с индексами больше k идут в шахматном
порядке, а на краях последовательности оказываются медианный и ближайший к нему элемент.
Количество таких перестановок при попарно различных ai не меньше, чем (k-1)!k! (если
медиана отличается от ближайших по значению соседей на одинаковую величину, то перестановок
вдвое больше).



ПРОГРАММА (C#):

    public static void T(string text, Stopwatch timer)
    {
        TimeSpan ts = timer.Elapsed;
        string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
            ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
        Console.Write(text + elapsedTime);
    }

    public static int[] FactGen(int n)
    {
        int[] fact = new int[n + 1];

        fact[0] = 1;
        for (int i = 1; i < n + 1; i++)
            fact[i] = i * fact[i - 1];

        return fact;
    }

    public static int[] PermsGenerator(int[] arr, int num, int[] fact)
    {
        int i, j, f, newind, newnum, newval, size = arr.Length;
        int[] result = new int[size];

        Array.Copy(arr, result, size);
        for (i = 0, newnum = num; i < size - 1; i++)
        {
            f = fact[size - 1 - i];
            newind = i;
            while (newnum >= f)
            {
                newind++;
                newnum -= f;
            }
            newval = result[newind];
            for (j = newind; j > i; j--)
                result[j] = result[j - 1];
            result[i] = newval;
        }

        return result;
    }

    public static int SumAbs(int[] arr)
    {
        int sum = 0, prev = arr[0];

        foreach (int value in arr)
        {
            sum += Math.Abs(value - prev);
            prev = value;
        }

        return sum;
    }

    public static int CalcOptQuant (int n)
    {
        int k = (n - 1) / 2, k2 = Math.Max(k-2, 0);
        int[] fact = FactGen(k + 2);

        return 2*fact[k] * ((n - k - k < 2) ? fact[k-1] : fact[k]);
    }

    public static int CalcMaxSum(int[] brr)
    {
        int i, size = brr.Length, k = size / 2, sum = 0;

        for (i = 0; i < k - 1; i++)
            sum += brr[size - 1 - i] - brr[i];
        sum = 2 * sum + brr[size - k] - brr[k - 1];
        if (size - 2 * k > 0) sum += Math.Max(brr[k+1] - brr[k], brr[k] - brr[k-1]);

        return sum;
    }

    public static int[] MaxArr(int[] arr, bool detprn)
    {
        int i, j, sum, smax = -1, size = arr.Length;
        int[] perm, result = new int[size], fact = FactGen(size),
            sorted = new int[size], empire = new int[size];
        Stopwatch sw = new Stopwatch();

        Console.WriteLine("\nИсходная выборка:  ");
        foreach (int value in arr)
            Console.Write(value + "  ");
        sw.Restart();
        for (i = 0; i < fact[size]; i++)
        {
            perm = PermsGenerator(arr, i, fact);
            sum = SumAbs(perm);
            if (sum > smax) {
                smax = sum;
                result = perm;
            }
        }
        if (detprn)
            Console.Write("\nЛучшие перестановки");
        for (i = 0, j = 0; i < fact[size]; i++)
        {
            perm = PermsGenerator(arr, i, fact);
            sum = SumAbs(perm);
            if (sum == smax)
            {
                j++;
                if (detprn)
                {
                    Console.Write("\n#{0}:  ", j);
                    foreach (int value in perm)
                        Console.Write(value + "  ");
                }
            }
        }
        Array.Copy(arr, sorted, size);
        Array.Sort(sorted);
        Console.WriteLine("\nОтсортированная выборка:  ");
        foreach (int value in sorted)
            Console.Write(value + "  ");
        Console.Write("\nФакт     Наибольшая сумма: {0}   Лучших перестановок: {1}" +
            "\nРасчёт   Наибольшая сумма: {2}   Лучших перестановок, не менее: {3}", 
            smax, j, CalcMaxSum(sorted), CalcOptQuant(size));
        T("\nRuntime = ", sw);
        sw.Reset();

        return result;
    }

    static void Main(string[] args)
    {
        bool binc;
        int i, j, n, nmax = 12;
        int[] arr =  new int[0];
        Random rand = new Random();

        MaxArr(new int[] { 0, 1, 2, 3, 4, 5 }, true);
        MaxArr(new int[] { 5, 1, 3, 5, 7, 9 }, true);
        MaxArr(new int[] { 0, 1, 2, 3, 4 }, true);
        MaxArr(new int[] { 0, 1, 2, 3 }, true);
        MaxArr(new int[] { 0, 1, 2 }, true);
        for (n = 3; n <= nmax; n++)
        {
            Array.Resize(ref arr, n);
            for (i = 0; i < n;)
            {
                arr[i] = rand.Next(10, 99);
                binc = true;
                for (j = 0; j < i; j++)
                    binc &= (arr[i] != arr[j]);
                if (binc)
                    i++;
            }
            MaxArr(arr, false);
        }
    }




РЕЗУЛЬТАТЫ:


Исходная выборка:
0  1  2  3  4  5
Лучшие перестановки
#1:  2  4  0  5  1  3
#2:  2  4  1  5  0  3
#3:  2  5  0  4  1  3
#4:  2  5  1  4  0  3
#5:  3  0  4  1  5  2
#6:  3  0  5  1  4  2
#7:  3  1  4  0  5  2
#8:  3  1  5  0  4  2
Отсортированная выборка:
0  1  2  3  4  5
Факт     Наибольшая сумма: 17   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 17   Лучших перестановок, не менее: 8
Runtime = 00:00:00.01
Исходная выборка:
5  1  3  5  7  9
Лучшие перестановки
#1:  5  1  7  3  9  5
#2:  5  1  9  3  7  5
#3:  5  3  7  1  9  5
#4:  5  3  9  1  7  5
#5:  5  7  1  9  3  5
#6:  5  7  3  9  1  5
#7:  5  9  1  7  3  5
#8:  5  9  3  7  1  5
#9:  5  1  7  3  9  5
#10:  5  1  9  3  7  5
#11:  5  3  7  1  9  5
#12:  5  3  9  1  7  5
#13:  5  7  1  9  3  5
#14:  5  7  3  9  1  5
#15:  5  9  1  7  3  5
#16:  5  9  3  7  1  5
Отсортированная выборка:
1  3  5  5  7  9
Факт     Наибольшая сумма: 24   Лучших перестановок: 16
Расчёт   Наибольшая сумма: 24   Лучших перестановок, не менее: 8
Runtime = 00:00:00.01
Исходная выборка:
0  1  2  3  4
Лучшие перестановки
#1:  1  3  0  4  2
#2:  1  4  0  3  2
#3:  2  0  4  1  3
#4:  2  1  4  0  3
#5:  2  3  0  4  1
#6:  2  4  0  3  1
#7:  3  0  4  1  2
#8:  3  1  4  0  2
Отсортированная выборка:
0  1  2  3  4
Факт     Наибольшая сумма: 11   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 11   Лучших перестановок, не менее: 4
Runtime = 00:00:00.01
Исходная выборка:
0  1  2  3
Лучшие перестановки
#1:  1  3  0  2
#2:  2  0  3  1
Отсортированная выборка:
0  1  2  3
Факт     Наибольшая сумма: 7   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 7   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
0  1  2
Лучшие перестановки
#1:  0  2  1
#2:  1  0  2
#3:  1  2  0
#4:  2  0  1
Отсортированная выборка:
0  1  2
Факт     Наибольшая сумма: 3   Лучших перестановок: 4
Расчёт   Наибольшая сумма: 3   Лучших перестановок, не менее: 2
Runtime = 00:00:00.01
Исходная выборка:
25  51  87
Отсортированная выборка:
25  51  87
Факт     Наибольшая сумма: 98   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 98   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
78  10  34  64
Отсортированная выборка:
10  34  64  78
Факт     Наибольшая сумма: 166   Лучших перестановок: 2
Расчёт   Наибольшая сумма: 166   Лучших перестановок, не менее: 2
Runtime = 00:00:00.00
Исходная выборка:
23  26  93  16  45
Отсортированная выборка:
16  23  26  45  93
Факт     Наибольшая сумма: 195   Лучших перестановок: 4
Расчёт   Наибольшая сумма: 195   Лучших перестановок, не менее: 4
Runtime = 00:00:00.00
Исходная выборка:
85  12  11  13  90  88
Отсортированная выборка:
11  12  13  85  88  90
Факт     Наибольшая сумма: 382   Лучших перестановок: 8
Расчёт   Наибольшая сумма: 382   Лучших перестановок, не менее: 8
Runtime = 00:00:00.00
Исходная выборка:
82  43  28  55  29  39  18
Отсортированная выборка:
18  28  29  39  43  55  82
Факт     Наибольшая сумма: 206   Лучших перестановок: 24
Расчёт   Наибольшая сумма: 206   Лучших перестановок, не менее: 24
Runtime = 00:00:00.00
Исходная выборка:
64  20  43  89  47  94  52  71
Отсортированная выборка:
20  43  47  52  64  71  89  94
Факт     Наибольшая сумма: 300   Лучших перестановок: 72
Расчёт   Наибольшая сумма: 300   Лучших перестановок, не менее: 72
Runtime = 00:00:00.02
Исходная выборка:
45  53  81  17  76  97  26  50  51
Отсортированная выборка:
17  26  45  50  51  53  76  81  97
Факт     Наибольшая сумма: 337   Лучших перестановок: 288
Расчёт   Наибольшая сумма: 337   Лучших перестановок, не менее: 288
Runtime = 00:00:00.23
Исходная выборка:
55  51  36  12  82  63  89  58  14  22
Отсортированная выборка:
12  14  22  36  51  55  58  63  82  89
Факт     Наибольшая сумма: 420   Лучших перестановок: 1152
Расчёт   Наибольшая сумма: 420   Лучших перестановок, не менее: 1152
Runtime = 00:00:02.46
Исходная выборка:
96  95  67  49  65  69  53  78  35  55  94
Отсортированная выборка:
35  49  53  55  65  67  69  78  94  95  96
Факт     Наибольшая сумма: 348   Лучших перестановок: 11520
Расчёт   Наибольшая сумма: 348   Лучших перестановок, не менее: 5760
Runtime = 00:00:29.21
Исходная выборка:
50  43  39  64  59  18  81  16  44  12  15  77
Отсортированная выборка:
12  15  16  18  39  43  44  50  59  64  77  81
Факт     Наибольшая сумма: 463   Лучших перестановок: 28800
Расчёт   Наибольшая сумма: 463   Лучших перестановок, не менее: 28800
Runtime = 00:06:26.81




АНАЛИЗ РЕЗУЛЬТАТОВ

Во всех рассмотренных случаях тестирование полностью подтвердило предлагаемое общее
решение.


Ответ 3

Предлагаю следующий алгоритм:


Сортируем входной массив
Поочередно берем элементы с конца его первой половины и с конца его второй половины
Если длина массива нечетная, берем самый центральный элемент и помещаем его в начало
или в конец, в зависимости от того, где больше разница с ним - слева или справа


Код на C#:

static void Main(string[] args)
{
    //var input = new[] { 1, 2, 3, 4, 5 };
    //var input = new[] { 1, 2, 3, 100, 200 };
    //var input = new[] { 1, 2, 100, 200, 300 };
    //var input = new[] { 22, 26, 48, 37, 47, 13, 9, 19 };
    var input = new[] { 40, 27, 4, 9, 32, 35, 41, 39, 2 };
    var combine = GetCombine(input);
    var sum = GetSum(combine);
    Console.WriteLine(string.Join(" ", combine));
    Console.WriteLine(sum);
}

static int[] GetCombine(int[] input)
{
    var len = input.Length;
    var sorted = input.OrderBy(x => x).ToArray();
    var output = new int[len];
    var d = 0;
    if (len % 2 == 1)
    {
        if (sorted[len / 2] - sorted[len / 2 - 1] >
            sorted[len / 2 + 1] - sorted[len / 2]) d = 1;
        output[(len - 1 + d) % len] = sorted[len / 2];
    }
    for (int i = 0; i < len / 2; ++i)
    {
        output[2 * i + d] = sorted[len / 2 - 1 - i];
        output[2 * i + 1 + d] = sorted[len - 1 - i];
    }
    return output;
}

static int GetSum(int[] combine)
{
    int sum = 0;
    for (int i = 0; i < combine.Length - 1; ++i)
        sum += Math.Abs(combine[i] - combine[i + 1]);
    return sum;
}


Проверить

Python. Чем на самом деле является print?

#python #python_2x #print #expressions

Почему функция/оператор/набор символов (или что оно на самом деле) print не может
работать в выражениях?

Python 2.7.9 (default, Jun 29 2016, 13:08:31) 
[GCC 4.9.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> print('hahaha')
hahaha
>>> 0 or print('hahaha')
  File "", line 1
    0 or print('hahaha')
             ^
SyntaxError: invalid syntax
>>> def test(): print('hahaha')
... 
>>> 0 or test()
hahaha
>>> 

    

Ответы

Ответ 1

В Python 2.X print является ключевым словом (вроде return во многих языках), по этому
после него выражение не обязательно должно быть заключено в скобки. И оно не является
функцией и не может возвращать значения (даже None). По этому оно не может быть частью
логического выражения:

0 or return("hahaha")


В Pyton 3.X это фнукция. По этому там требуется ее аргументы заключать в скобки,
и она возвращает None (который в логическом контексте действует как False), по этому
такое логическое выражение не вызовет ошибок.

Xml сериализация объектов со свойствами только для чтения

#c_sharp #xml #сериализация

При сериализации массива из объектов этого класса все атрибуты игнорируются, если
у них нет setter'а. Вопрос: как решить проблему с этим явлением; класс не предусмотрен
для изменения данных.

/// 

/// Представляет поля и методы для работы с абстракцией осциллятора.
/// 
[Serializable]
public class Oscillator : IMixer
{
    private Boolean enable;
    /// 

    /// Состояние вкл / выкл.
    /// 
    [XmlAttribute]
    public Boolean Enable
    {
        get
        {
            return enable;
        }
        set
        {
            enable = value;
        }
    }


    private Int32 volume;
    /// 

    /// Процентная громкость.
    /// 
    [XmlAttribute]
    public Int32 Volume
    {
        get
        {
            return volume;
        }
    }



    public Oscillator()
    {

    }


    public Oscillator(Boolean enable, Int32 volume)
    {
        this.enable = enable;
        this.volume = volume;
    }
}


    //Вот, сама сериализация, если интересно.
    /// 

    /// Сохраняет пресет в Xml-файл.
    /// 
    /// 
    /// Путь к файлу.
    /// 
    /// 
    /// Массив осцилляторов для записи его в пресет.
    /// 
    public void SavePreset(String fileName, Oscillator[] oscs)
    {
        try
        {
            XmlSerializer serializer = new XmlSerializer(typeof(Oscillator[]));
            using (Stream stream = new FileStream(fileName, FileMode.Create, FileAccess.Write))
            {
                serializer.Serialize(stream, oscs);
                //for (Int32 i = 0; i < oscs.Length; i++)
                //{
                //    serializer.Serialize(stream, oscs[i]);
                //}
            }
        }
        catch
        {
            throw new PresetException(PresetException.SaveError);
        }
    }

    

Ответы

Ответ 1

Никак, это ограничение XmlSerializer. 


  Only public properties and fields can be serialized. Properties must
  have public accessors (get and set methods). If you must serialize
  non-public data, use the DataContractSerializer class rather than XML
  serialization.


В оригинальном ответе, как и в документации, советуют воспользоваться более гибким
DataContractSerializer.



Вариант с вырожденным сеттером, думаю, рассматривать не будем.


Ответ 2

Никак. Но вам это и не нужно. Вы должны иметь отдельные классы для сериализации/десериализации
(и вообще любой транспортировки данных - DTO) и для бизнес-логики (POCO). И я рекомендую
вам реализовать такое разделение как можно раньше, это позволит избежать глобальных
ломающих изменений по мере развития проекта. Ссылка по теме: Наглядный пример различия
DTO, POCO (POJO) и Value Object

Что конкретно делает метод Thread.SpinWait?

#c_sharp #net

Из документации откровенно говоря ничего непонятно, все очень сумбурно. Что именно
делает этот метод?
    

Ответы

Ответ 1

Русский машинный перевод не очень хорош, лучше смотреть в свежий английский оригинал:


  SpinWait essentially puts the processor into a very tight loop, with the loop count
specified by the iterations parameter. The duration of the wait therefore depends on
the speed of the processor.


то есть


  SpinWait на самом деле просто выполняет холостой цикл, количество итераций которого
равно параметру iterations. Продолжительность ожидания, таким образом, зависит от скорости
процессора.


Для чего такое может понадобиться? Например, для оптимизации блокировки: если заблокированный
ресурс скорее всего будет через несколько тактов процессора освобождён, то имеет смысл
перед уходом на ожидание в режим ядра (что является медленной операцией) прокрутить
несколько холостых циклов в надежде, что ресурс за это время освободится. Именно это
делает lock/Monitor.Enter.

Почему не работает подключение SVG файла c помощью img?

#html #css #css3 #svg #анимация

Сделал такой логотип с помощью SVG

Сохранил в формате .svg, а потом попытался добавить на страницу с помощью тега img
таким образом:




По какой-то причине логотип не хочет добавляться, путь 100% правильный, имя файла
тоже 100% правильное.
 Если же добавлять тот же самый код на страницу без сохранения в SVG файл, то все
работает.
    

Ответы

Ответ 1

Всё дело в том, что вы попали в ловушку разницы работы парсеров Html и xml
Первый не выдает сообщение об ошибке отсутствия указания Namespaces. А файл svg не
будет работать без указания Namespaces    

Для проверки попробуйте сохранить код вашего лого в файл с расширением *.svg.    

Код не будет выполнен и парсер xml выдаст сообщение об ошибке. 


Поэтому всегда добавляйте в шапке svg Namespaces


  
Указывая ширину и высоту можно дополнительно регулировать размер
лого.


Следующий ваш вопрос будет почему не работает анимация при наведении.

Потому что вы вызываете svg файл через  

  

Более подробно о других способах подключения файлов svg здесь

Как сделать статическое свойство класса в питоне?

#python #ооп

Пробую так:

class ChatCodes:

   _chat = 'cht'

   @property
   def chat(self):
      return self._chat


если использую так:

print(ChatCodes.chat + 'any_str')


то появляется ошибка:


  unsupported operand type(s) for +: 'property' and 'str'


как правильно создать статическое свойство?
    

Ответы

Ответ 1

В принципе, объявленный параметр класса со значением - уже может использоваться как
статическое свойство

>>> class MyClass:
...     param = "value"
...
>>> MyClass.param
'value'
>>>


Это же значение будет доступно и для экземпляра класса. Разве что у экземпляра есть
опасность, что значение свойства изменится в процессе работы. Тут стоит позаботиться,
чтоб этот параметр не изменялся и/или чтоб обращение к свойству шло исключительно через
имя класса, а не экземпляра.

Можно использовать статический метод - объявляется с помощью аннотации @staticmethod.
Правда и обращаться к нему придётся как к методу, а не свойству

>>> class MyClass:
...     @staticmethod
...     def param():
...             return "value"
...
>>> MyClass.param

>>> MyClass.param()
'value'
>>>


Если достаточно ленивой инициализации (то есть обращаться к свойству будем через
экземпляр класса), то можно использовать аннотацию @property

>>> class MyClass:
...     @property
...     def param(self):
...             return "value"
...
>>> MyClass.param

>>> MyClass.param()
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'property' object is not callable
>>>
>>> m = MyClass()
>>> m.param
'value'


Ну и вариант на любителя (на случай, когда значение свойства нужно вычислить):

>>> class MyClass:
...     def _method_to_create_static_prop():
...             return "value"
...     param = _method_to_create_static_prop()
...     del _method_to_create_static_prop
...
>>> MyClass.param
'value'
>>> MyClass._method_to_create_static_prop
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: class MyClass has no attribute '_method_to_create_static_prop'
>>>


Ответ 2

Если вы хотите, чтобы C.class_property вызывало бы метод класса, можно метакласс
__getattr__ метод определить:

#!/usr/bin/env python3
import random

class ClassPropertyMeta(type):
    def __getattr__(cls, key):
        if key == 'class_property':
            return cls._get_class_property()
        raise AttributeError(f"<{cls!r}.{key!r}>")

class C(metaclass=ClassPropertyMeta):
    @classmethod
    def _get_class_property(cls):
        return random.random()

print(C.class_property)
# -> 0.333495437410268


Аналогично для модулей в Питоне 3.7 (PEP 562):

#!/usr/bin/env python3
import random


def __getattr__(name):
    print(name)
    return random.random()


if __name__ == '__main__':
    import module_attr
    print(module_attr.module_property)
    # -> module_property
    # -> 0.420563286888762

Влияет ли размер css файла на загрузку страницы?

#html #css #вёрстка

К примеру у меня в css файле написано более 1к строк или к примеру файл весит более
1 мб... Может ли это повлиять на загрузку страницы?

Если к примеру для каждой страницы(к примеру) писать отдельный css файл, получается
страница будет быстрее загружаться?
    

Ответы

Ответ 1

Вес всего, что вы размещаете на странице будет влиять на её загрузку. Однако, есть
и вторая сторона вопроса. Разбив файл на множество мелких, подгружая их в каждом нужном
разделе, вы увеличиваете количество запросов, необходимых для чтения этих файлов.

Что же делать, в такой ситуации?

1) Используйте сжатие. Пример, тут.

2) Уменьшайте количество стилей путем переноса в нужные страницы, но, только там,
где страницы не индексируются или находится единичный элемент. 

Пример:


Код формы или страницы регистрации можно вынести в отдельный файл. В общем-то, для
всех служебных участков, которые закрыты от индексации можно писать отдельные стили.
Если основной слайдер на главной странице более нигде не размещается, тогда вынесите
его стили в inline.


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

3) Некоторым стилям задавайте отдельные классы и используйте их при работе с HTML.

Например:

Запишите transition: all .5s; таким образом:

.transition {
 -webkit-transition: all .5s;
 -o-transition: all .5s;
 transition: all .5s;
}


Затем подставляйте этот класс непосредственно при работе с кодом страницы.

...


Таким образом вы существенно уменьшите количество повторов для таких стилей как user-select,
элементов Flexbox и других.

Все эти советы применимы и к файлам JS.

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

Если кто-то что-то добавит, будет вообще супер!


Ответ 2

Конечно влияет. Но только при первом обращении, далее любой нормальный браузер просто
закеширует его. Если хотите чтобы уж очень быстро, используйте inline стили, но это
сами понимаете не очень красиво и тем более не очень удобно и практично. Хотя я использовал
такой подход при работе с Vue.js например для разработки админ панели. Если для вас
важно СЕО, думаю это не очень хорошая идея. Насчет разбить на страницы, можно с точки
зрения удобства разработки, но не забывайте что это повлечет за собой и увелечение
кол-ва запросов к серверу.
Хотя если вы используете какой нибудь Webpack то это не проблема насколько я знаю.


Ответ 3

Может ли это повлиять на загрузку страницы?


Логически да, практически (и да и нет).


Сжатие.


Если у вас в css комментарии, пробелы, переносы строк, то первое о
чем вам стоит задуматься, это об оптимизации css, а точнее о его
сжатии, максимальном. Т.е. когда вы откроете файл, там все будет в 1
строку, без лишних пробелов и т.д и т.п.

Кэширование статических файлов.


Как мы знаем, браузеры умеют хранить кэш веб-страниц. Вот тут то там и поможет как
минимум ускорить загрузку страниц, так это кэширование файлов которые часто используются,
но не часто изменяются, или совсем никогда.