|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
21.09.2015, 08:52 | #1 |
Регистрация: 21.09.2015
Сообщений: 8
|
Здравствуйте.
Нужен алгоритм. Есть массив целых. Надо определить, существует ли в нем хотя-бы два не нулевых равных друг-другу числа. Пишу для микроконтроллера, поэтому желательно обойтись математикой и бинарной логикой. (В принципе, можно написать функцию на Си и оформить как ФБ. Но интуиция мне подсказывает, что есть арифметический способ. Только пока ничего не придумывается.) Спасибо. Пока у меня родилось только такое: Обнуляем аккумулятор. Берем очередное число из списка. Возводим двойку в степень этого числа получаем число в бинарном представлении взведен всего один бит, сравниваем с аккумулятором, если этот-же бит взведен, то значит такое число уже было, выходим из цикла, если нет - побитово складываем с аккумулятором. Берем следующее число... Плюсы: поиск за один проход. Возведение в степень можно заменить бинарным сдвигом. Минусы: числа ограничены диапазоном 0-31. Под мои нужды пока годится. Смущает корявость решения, и что делать, если потребуются числа больше 31? Последний раз редактировалось Utkin; 21.09.2015 в 10:06. |
21.09.2015, 10:15 | #2 | |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Стандартно оформить отдельную подпрограмму с проходом в цикле.
Цитата:
1 2 4 7 3 3 3 Прорешайте, как там получится по-Вашему алгоритму. И второй вариант - это пытаться оптимизировать под конкретную задачу (для микроконтроллера актуально). Для чего это надо? Далее есть вариант, но его надо оценить по времени. Это банальная сортировка - тогда все одинаковые числа будут рядом.
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
|
21.09.2015, 10:35 | #3 |
Регистрация: 21.09.2015
Сообщений: 8
|
Алгорим такой:
1 Обнуляем аккумулятор (регистр, переменная... не важно) "А" 2 Берем очередное число из массива. 3 Возводим двойку в степень этого числа. Получаем число, в двоичном представлении которого взведен всего один бит. "К" 4 Получившееся число "К" сравниваем с аккумулятором "А" побитово. 5 Если в аккумуляторе бит, что и в нашем числе - взведен, значит мы нашли исходное равенство - выходим из функции. 6 Складываем "К" и "А" побитово. 7 если массив не пройден, идем на пункт 2 8 Прошли весь массив и ничего не нашли - совпадающих чисел нет, вываливаемся с нулем. Получается приемлемо по скорости. Поиск за один проход, и двойка легко возводится в любую степень простым сдвигом. Но я ограничен диапазоном 0-31. (Процессор 32-х разрядный: "Motorola MPC5200") Пока мне этого диапазона хватает. Просто, возможно я изобретаю очередной велосипед с квадратными колесами, вот и решил спросить. Сортировка мне тоже пришла на ум, но на скорую руку придумалась только пузырьковая, и я её отбросил. Последний раз редактировалось Ароха; 21.09.2015 в 10:37. |
21.09.2015, 10:50 | #4 |
Регистрация: 21.09.2015
Сообщений: 8
|
Алгоритм не пригоден, количество возможных значений чисел в массиве увеличилось до 53х.
|
21.09.2015, 16:02 | #5 | ||
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Цитата:
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
||
21.09.2015, 20:46 | #6 | |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Цитата:
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
|
21.09.2015, 21:10 | #7 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
21.09.2015, 21:27 | #8 | |
Цифровой кот
Старожил
Регистрация: 29.08.2014
Сообщений: 7,629
|
Цитата:
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
|
|
21.09.2015, 21:41 | #9 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Ну а создать не один байт, а два? При чем раздельно.. Не?
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Проверка на равенство | schoolboy99 | Помощь студентам | 0 | 21.04.2015 17:31 |
Java: Дан двумерный массив чисел А размером 6х6 и одномерный массив Х из 6-ти чисел. Заменить первые три строки массива A | vikysha55 | Помощь студентам | 1 | 16.04.2014 10:50 |
сравнение массива строк и массива чисел | RevenGGe | Общие вопросы C/C++ | 21 | 03.06.2012 18:49 |
определить количество четных чисел и количество нечетных чисел массива, которые вводятся в МЕМО, вывести в поле компонента Edit. | Pyxy | Помощь студентам | 2 | 21.03.2012 23:24 |
проверка чисел на простоту | neeble | Помощь студентам | 3 | 10.03.2012 17:36 |