tag:blogger.com,1999:blog-6482727957786849560.post763048710581122073..comments2023-07-01T14:24:40.214+03:00Comments on [k06a]'s Blog: Задачка про уникальность[k06a]http://www.blogger.com/profile/04937580939115849295noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-6482727957786849560.post-28389416438929818152010-06-18T13:49:13.982+04:002010-06-18T13:49:13.982+04:00Или вы имели ввиду поиск трёх уникальных значений?...Или вы имели ввиду поиск трёх уникальных значений?<br /><br />Тогда надо разбивать на диапазоны, пока не выявится 3 диапазона с ненулевой XOR-суммой.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-61947521811065304452010-06-13T02:58:00.426+04:002010-06-13T02:58:00.426+04:00Ну, например, переменных четыре))
Тогда на первом ...Ну, например, переменных четыре))<br />Тогда на первом этапе XOR-им в них диапазоны:<br />0x00000000 - 0x3FFFFFFFF<br />0x40000000 - 0x7FFFFFFFF<br />0x80000000 - 0xDFFFFFFFF<br />0xC0000000 - 0xFFFFFFFFF<br />В случае успеха 2 из XOR-ов будут ненулевыми.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-87814935298979881212010-06-13T01:44:17.388+04:002010-06-13T01:44:17.388+04:00Так что делать, если переменных три? понять, что ч...Так что делать, если переменных три? понять, что число?Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-16947166876842183032010-06-13T01:37:48.041+04:002010-06-13T01:37:48.041+04:00Это соответственно если использовать всего 2 перем...Это соответственно если использовать всего 2 переменных для подсчёта XOR-суммы. На самом деле число сумм задаёт основание логарифма. Так что лучше использовать побольше))[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-90134158961704849972010-06-12T23:55:23.561+04:002010-06-12T23:55:23.561+04:00Красиво.Красиво.Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-65096807162576567352010-06-11T23:32:48.614+04:002010-06-11T23:32:48.614+04:00Прошло достаточно времени.
Опубликую своё решение ...Прошло достаточно времени.<br />Опубликую своё решение второй задачи.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-74318515138727518872010-04-03T22:43:01.893+04:002010-04-03T22:43:01.893+04:00Что-то у меня уже глюки)) Пару сообщений назад про...Что-то у меня уже глюки)) Пару сообщений назад про логарифм сбредил. У второго алгоритма получил сложность O(n).[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-74731523032012876492010-04-03T22:34:00.412+04:002010-04-03T22:34:00.412+04:00Лучше ксора я тоже ничего не придумал на первое за...Лучше ксора я тоже ничего не придумал на первое задание. Так что думаю это и есть верный ответ. Второе задание поинтересней))[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-8114886843818169132010-04-03T21:05:39.860+04:002010-04-03T21:05:39.860+04:00Так мое решение с xor для одного числа подходит?Так мое решение с xor для одного числа подходит?Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-63510800193031839302010-04-03T20:44:21.226+04:002010-04-03T20:44:21.226+04:00Ой, это я про одно уникальное число.
Для двух чисе...Ой, это я про одно уникальное число.<br />Для двух чисел зависимость логарифмическая.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-1244842111382913172010-04-03T18:41:06.279+04:002010-04-03T18:41:06.279+04:00Существует решение, находящее ответ за константное...Существует решение, находящее ответ за константное число проходов. Тоесть сложность O(n).[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-67912091472544129422010-04-03T18:31:12.454+04:002010-04-03T18:31:12.454+04:00Для поиска одного числа:
int a[] = { 20, 31, 20, ...Для поиска одного числа:<br /><br />int a[] = { 20, 31, 20, 1, 3, 1, 3, 40, 40, 50, 50 };<br /><br />int main() {<br /> int i, c = 0;<br /> for (i = 0; i < sizeof(a)/sizeof(*a); ++i)<br /> c ^= a[i];<br /> printf("%d\n", c);<br />}<br /><br />Выводит: 31<br /><br />Для двух надо подумать еще ;-).Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-34448483864627894652010-04-03T17:29:33.636+04:002010-04-03T17:29:33.636+04:00Александр, для упрощения можно считать, что разряд...Александр, для упрощения можно считать, что разрядность чисел в массиве не превышаеть разрядности операционной системы и уж тем более разрядности процессора. Пусть это будут беззнаковые 32-хразрядные целые числа.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-67772929472343675222010-04-03T03:42:11.247+04:002010-04-03T03:42:11.247+04:00Если сами числа совершенно произвольные (например,...Если сами числа совершенно произвольные (например, даже дробные) и их не получается использовать как-то хитро как индексы массива-карты или как ключи хеш-таблицы обработанных элементов со временем доступа O(1), то остается только отсортировать массив - это время O(N*log(N)), а потом его линейно пробежать, проверяя, что каждый элемент имеет рядом равную ему пару. Это будет время O(N), то есть в этоге будет O(N*log(N)). Тут уже не важно, сколько уникальных элементов искать.<br /><br />Но это все весьма прямолинейно. Забавно, если задачу можно решить просто в один проход.Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-20047840701147993112010-04-03T03:01:39.102+04:002010-04-03T03:01:39.102+04:00Александр, на память ограничения не накладываются....Александр, на память ограничения не накладываются. Желательно использовать разумное количество памяти. Может получиться, например, прямая зависимость между используемой памятью и сложностью алгоритма(число операций), тогда это стоит отдельно обговорить в ответе.[k06a]https://www.blogger.com/profile/04937580939115849295noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-8546284071975222942010-04-03T02:41:24.131+04:002010-04-03T02:41:24.131+04:00Дополнительнию память можно использовать?Дополнительнию память можно использовать?Александрhttps://www.blogger.com/profile/03980297457924475954noreply@blogger.comtag:blogger.com,1999:blog-6482727957786849560.post-66332142153795273372010-04-02T20:19:58.946+04:002010-04-02T20:19:58.946+04:00Это из теста на С++ программиста в Gameloft...Это из теста на С++ программиста в Gameloft...Anonymoushttps://www.blogger.com/profile/15488824961340381236noreply@blogger.com