Задача с собеса в яндекс на бекенд, камрады!!!

Что произойёт с целыми переменными a,b после выполнения?

a ^= b ^= a ^ = b;

1) a станет равно 0?
2) a,b станут равны?
3) a,b поменяются значениями
4) b станет равно 0, а a станет равным b
5) Undef behavior
6) Unspec behavior

Решение: очевидно будет Undefined behavior. Компилятор имеет право вычислять подвыражения в любом порядке, так как их порядок не задан стандартом. Он может начать с самого левого a ^= b, с самого правого a ^= b, или с середины. Результат будет разным в каждом из этих случаев.

int fn(int v) {
    if (v == 1 || v == 0) {
        return 1;
    }
    if (v % 2 == 0) {
        return fn(v / 2) + 2;
    }
    return fn(v - 1) + 3;
}

fn(7)?
Решение: Вычисление fn(7):

v = 7 (нечётное):
return fn(6) + 3

v = 6 (чётное):
return fn(3) + 2

v = 3 (нечётное):
return fn(2) + 3

v = 2 (чётное):
return fn(1) + 2

v = 1:
return 1

Теперь поднимаемся обратно по цепочке вызовов:

Шаг 5: fn(1) = 1

Шаг 4: fn(2) = fn(1) + 2 = 1 + 2 = 3

Шаг 3: fn(3) = fn(2) + 3 = 3 + 3 = 6

Шаг 2: fn(6) = fn(3) + 2 = 6 + 2 = 8

Шаг 1: fn(7) = fn(6) + 3 = 8 + 3 = 11

Ответ
fn(7) = 11

// Выберите самый точный вариант вычисления суммы (предполагаем, что числа только положительные)

// Вариант 1
double sum(vector<float> &v) {
    return accumulate(v.begin(), v.end(), 0.0);
}

// Вариант 2
double sum(vector<float> &v) {
    sort(v.begin(), v.end());
    return accumulate(v.begin(), v.end(), 0.0);
}

// Вариант 3
double sum(vector<float> &v) {
    sort(v.begin(), v.end(), greater<float>());
    return accumulate(v.begin(), v.end(), 0.0);
}

Решение: Самый точный вариант — Вариант 2 (сортировка по возрастанию).

Объяснение:

При суммировании чисел с плавающей точкой возникает проблема потери точности из-за ограниченной мантиссы. Когда мы складываем числа сильно разного порядка, младшие разряды меньшего числа теряются.

Почему Вариант 2 самый точный:

Сортировка по возрастанию `(sort(v.begin(), v.end()))` означает, что мы начинаем суммировать с наименьших чисел

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

Это уменьшает потерю точности, так как числа одного порядка складываются сначала

Почему другие варианты хуже:

Вариант 1: Без сортировки — порядок суммирования произвольный, возможна значительная потеря точности

Вариант 3: Сортировка по убыванию — начинаем с самых больших чисел, и когда к ним добавляются очень маленькие числа, они могут быть полностью проигнорированы из-за ограниченной точности

@codeof_art
@codeof_art
@codeof_art