Wataru

В Си у массивов нет встроенной длины*. Массив - это обычно просто указатель на область памяти, где лежат его элементы. А сколько их там, надо как-то отдельно хранить и передавать. Можно, как в строках, помечать специальным символом конец, или можно передавать длину в отдельной переменной рядом с массивом.

Соответственно, чтобы вернуть пустой массив, надо вернуть массив длины 0. Ваша функция же как-то должна возвращать длину массива? Вот точно также, как если бы длина была 1, только 0. Или сразу первым элементом идет маркер конца массива. Или переменная длины, которую, скорее всего, придется сделать out параметром функции, будет содержать 0. Или можно NULL возвращать, как особый случай, что ничего нет.

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

Просто сгенерируйте случайную матрицу. Двумя циклами получайте коэффициенты через генератор случайных чисел. Вероятность, что она будет вырождена ничтожна. Потом сгенерируйте сулчайные значения всех переменных, подставьте в уравнения с имеющимеся теперь у вас коэффициентами и получите так правую часть уравнений. Вот и ваша СЛАУ с решением. Если хотите, чтобы решения не было, то можно случайно поменять правую часть в каких-то уравнениях. Если хотите, чтобы система была вырожденной, то замените какие-то строки случайной линейной комбинацией других строк (случайно получив коэффициенты линейной комбинации).

В C++ есть генератор случайных чисел - функция rand(). Гуглите ее, она вернет случайное целое число. Если вам нужны вещественные и возможно отрицательные коэффициенты, то эти целые числа можно использовать для получения вещественных. Гуглите "C++ случайное вещественное число".

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

Вам нужна формула размещений. От использованной формулы сочетаний отличается отсутствием k! в знаменателе.

Между вводом и проверкой в if-e надо поставить логическую операцию или (||).

По идее надо бы задать формулу кусочно для разных n, но можно все собрать в одну формулу как-то так:

(2-n)(3-n)/2*f1(n) + (n-1)(3-n)*f2(n) + (n-1)(n-2)/2*f3(n)

Далее f1(n) = b-a+1

Для нахождения f2 и f3 можно сдвинуть левую границу вправо до первого числа нужной четности, а правую границу - влево. Потом уже зная, что 2 крайних числа в промежутке между a' и b' берутся, то фромула будет (b'-a')/2+1.

Для такого сдвига надо будет смотреть на четность a и b и четность n.

В итоге:
f2(n) = ((b-b%2)-(a+a%2))/2+1
f3(n) = ((b-1+b%2)-(a+1-a%2))/2+1

Можно f2 и f3 объединить используя n%2 и операцию xor: если четность a или b не такая же как у n, то надо границу сдвигать (вычесть/прибваить 1). Иначе надо вычесть/прибавить 0. xor как раз равен 1 при неравнестве и 0 при совпадении четностей.

f23(n) = ((a+(a%2 ^ n%2))-(b-(b%2)^(n%2)))/2+1

Итоговая формула:

(2-n)(3-n)/2*(b-a+1) + ((n-1)(3-n) + (n-1)(n-2)/2)*(((a+(a%2 ^ n%2))-(b-(b%2)^(n%2)))/2+1)

А еще, если пользоваться битовыми функциями, то можно вместо (n-1)(3-n) + (n-1)(n-2)/2 использовать (n & 2)/2, в вместо первой скобки (1 - (n & 2)/2)

Формула правильно возвращает 0, если чисел в промежутке нет. Правда, она не работает, если a > b.

Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.

Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.

Не совсем понятно, а чего вы вообще пытаетесь добиться зануляя value? После деструктора весь объект и его член value уничтожаются. Любое обращение к ним - это UB. Соотвтественно вы этот новый 0 никак снаружи пощупать не сможете.

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

Единственный способ бороться с этим, кажется, это использовать умные указатели. Всякие WeakPtr, которые не уничтожают блок счетчиков при удалении объекта. Если же вы опустились до сырых указателей, то это тупо адрес (число). И просто по нему никак не понять, а что по этому адресу лежит - оригинальный объект или что-то левое.

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

А дальше, чтобы найти мультипликативную группу, придется делать полный перебор. Перебирайте все полиномы (они у вас, видимо, над полем по модулю 2, их 2^n. Можно их перебирать как биты у целого числа). Потом умножайте на текущий полином в цикле, помечая в массиве уже полученные ранее полиномы. Если получили все 2^n элементов - вы нашли нужную группу. Если наткнулись на уже ранее полученный полином раньше времени - текущий кандидат не подходит.