читайте тему с начала, обсуждалось ужеSheen писал(а):Ну да, согласен, фигня получается ... так может тогда завести одну маленькую (а можно и побольше) переменную и при добавлении значения в массив, если значение нулевой, помещать на него ссылку. Когда надо будет это нулевое значение вытащить ... [лень набирать дальше]
пусть сенсеи меня поправят, но в теории задача оптимизации это уменшить степень функции О(N), где O - время затраченное на выполнение функции в зависимости от количества элементов N. При этом константа C (т.е. в данном случае t1, t2/2) отбрасывается. оба способа, соответственно имеют O(N) = N, т.е. среднее время выполнения линейно растет с увеличением кол-ва элементов.Azazello писал(а): Способ #1: пробежать весь массив, скажем, перемножая элементы, и результат сравнить с нулём. Время на работу с одним элементом - t1. Время на выполнение ВСЕГДА - N*t1.
Способ #2: loop с выходом, если элемент равен нулю. Время на работу с одним элементом - t2. Какое, в среднем, время мы потратим на поиск нуля в произвольном элементе? На вскидку, N(1 + N)*t2/2N =~ N*t2/2.
Вывод: Если я не ошибся, пробег всего массива выгоден только если t1 < t2/2.
... Типа, что-нибудь обратно пропорциональное "цэ из эн по ка" - число сочетаний... точнее завтра напишу ...).В данном конкретном случае упоминалось, что наличие 0 маловероятно. Так что об N/2, возникающем из-за прерывания цикла, или числе комбинаций можно забыть. Остается лишь сравнить t1 и t2. Еще вспоминаем, что это embedded system. Поэтому я думаю, что это все же вопрос стоимости операции (операций) при полном проходе по циклу.Azazello писал(а):Аман, в N/2 двойка в знаменателе - следствие того, что у нас только ОДИН ноль в массиве. Тривиальный случай - все элементы массива равны нулю. Тогда Способ #2 будет ВСЕГДА занимать ровно одну операцию, в то время как способ #1 будет, по-прежнему, ВСЕГДА занимать N операций. Во втором способе число операций пропорционально не просто N, а некому отношению N к числу нулей в массиве (4 утра, я только домой вернулся - лень считать
Попробовал я тот код. Не работает. Идею не уловил, вернее я согласен, что хорошо бы использовать поразрядные операции, но ... казалось вот она идея, а посмотрел поближе - фиг. Как с вечным двигателем.sz писал(а):Сравнение двух чисел и проверка на 0 - одна фигня.tiasur писал(а):Мне кажется правильным решением будет найти наименьшее число массива и затем сравнить его с нулем. Сравнение двух чисел идёт быстрее, чем проверка на нуль? В задаче не сказано, что в массиве могут быть орицательные числа.
Но можно использовать функцию min(abs(*a)). Правильные их имплементации не содержат никаких ифов.
Но вообще-то, тот код, который я ранее написал полностью и правильно отвечает на вопрос. Я абсолютно уверен, что это именно то, что они ждут.
Не помогло. Совсем запарил себе мозги - не фига не работает.ajkj3em писал(а):v ^ ~(v-1) равно 0 if and only if v равно 0tiasur писал(а):Попробовал я тот код. Не работает. Идею не уловил, вернее я согласен, что хорошо бы использовать поразрядные операции, но ... казалось вот она идея, а посмотрел поближе - фиг. Как с вечным двигателем.
то есть sz ~ пропустил
зачем это выражение, если v и без него равно 0 когда оно равно 0? Извиняюсь за тафтологию.v ^ ~(v-1) равно 0 if and only if v равно 0
логично :)tiasur писал(а):зачем это выражение, если v и без него равно 0 когда оно равно 0? Извиняюсь за тафтологию.v ^ ~(v-1) равно 0 if and only if v равно 0
Код: Выделить всё
#include <limits.h>
int check_for_zero(int * v, size_t n)
{
int r = 0;
for (; n; v++, n--) r |= ~( (*v) | -(*v) );
return (r >> (CHAR_BIT * sizeof(int) - 1)) & 1;
}
Красивая идея. Похоже что работает - нужно еще раз продумать.ajkj3em писал(а): короче, вот правильный ответ -
PS вообще без сравнений кстати (кроме for условия)Код: Выделить всё
#include <limits.h> int check_for_zero(int * v, size_t n) { int r = 0; for (; n; v++, n--) r |= ~( (*v) | -(*v) ); return (r >> (CHAR_BIT * sizeof(int) - 1)) & 1; }
PPS фишка в том, что (x | -x) выставляет highest бит для всех значений x кроме нуля. дальше я думаю все очевидно ..
Код: Выделить всё
#include <limits.h>
int check_for_zero(int * v, size_t n)
{
int r = ~0;
for (; n; v++, n--) r &= (*v) | -(*v);
return (r == 0);
}
tiasur писал(а):Есть замечания?
Код: Выделить всё
return (r >> (CHAR_BIT * sizeof(int) - 1)) == 0;Мне кажется он излишен.ajkj3em писал(а):tiasur писал(а):Есть замечания?Код: Выделить всё
return (r >> (CHAR_BIT * sizeof(int) - 1)) == 0;
Ошибка в другом месте. В конце надо сравнивать с 0xffffffff, а не с нулем. Ну и с начальными значениями ошибся. Виноват.ajkj3em писал(а):v ^ ~(v-1) равно 0 if and only if v равно 0tiasur писал(а):Попробовал я тот код. Не работает. Идею не уловил, вернее я согласен, что хорошо бы использовать поразрядные операции, но ... казалось вот она идея, а посмотрел поближе - фиг. Как с вечным двигателем.
то есть sz ~ пропустил
не работает если массив состоит из всех степеней двойкиsz писал(а): Идея была в том, что (i-1)^i всегда дает степень двойки минус один - 1, 3, 7, 15 и тд. Причем 0xffffffff только для 0.