Страница 1 из 4
Разбить число на байты и проверить их последовательность
Добавлено: 09 ноя 2015, 07:24
Сионист
Дано беззнаковое целое x. sizeof(x) строго меньше 256. Требуется проверить следующее утверждение: если разобрать число на байты, то они по разу примут все значения от ноля до sizeof(x)-1. Например, если sizeof(x) равно 8, то требуется проверить утверждение: x состоит из байтов, равных: 0, 1, 2, 3, 4, 5, 6 и 7. При этом порядок байтов значения не имеет.
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 09:04
somewhere
я бы подсказал, но мне противопоказан комп

Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 09:43
Сионист
Ну Ваш вариант угадать не сложно: написать функцию поиска в числе байта с заданным значением и функцию поиска в числе байта с заданным значением, начиная от заданной позиции байта, перебрать циклом байты числа, при этом найти максимальное из их значений и каждое значение поискать в числе обеими функциями. Иначе два костыля не получаются.
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 11:27
Romeo
Ну изъясняешься ты конечно. Голову сломал, пока прочёл. Особенно последний ответ...
Как хранится число? Как массив байтов?
Просто для таких больших чисел встроенного типа нет.
Самое простое - это отсортировать байты по не убыванию qsort'ом, затем однократно пройти увеличивая счётчик и сравнивая его с текущим байтом. Если все сравнения были успешны, значит говорим да, иначе - говорим нет. Количество действий N*log(N) + 2*N + С. Итого сложность алгоритма O(N) = N*log(N). Думаю, улучшить это значение без дополнительной памяти уже не получится.
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 12:17
somewhere
Можно улучшить со сложностью N, т.е. однопроходно, но это в личке =)
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 12:50
Сионист
Romeo писал(а):Как хранится число? Как массив байтов?
Нет конечно.
Romeo писал(а):Просто для таких больших чисел встроенного типа нет.
Восемь жалких байт - это уже большое число?
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 12:53
Сионист
Romeo писал(а):Количество действий N*log(N) + 2*N + С. Итого сложность алгоритма O(N) = N*log(N).
У меня уже получилось 3N шагов цикла в худшем случае и N+1 в лучшем.
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 13:11
Romeo
Хорошо, тогда однопроходный алгоритм, но с дополнительной памятью размера N. Решай сам, что тебе важнее: память или скорость. Я бы поставил на второе.
Код: Выделить всё
#include <iostream>
// Checks whether array contains consecutive values from 0 to nSize-1 in arbitrary order.
bool ContainsConsecutiveValues(unsigned char arrNumbers[], unsigned int nSize)
{
bool arrExists[nSize];
for (int i = 0; i < nSize; arrExists[i++] = false);
for (unsigned int i = 0; i < nSize; ++i)
{
// Value is not in range [0..nSize-1]
if (arrNumbers[i] >= nSize) return false;
if (arrExists[arrNumbers[i]])
{
// Repetition of the value
return false;
}
else
{
// Marking the value as met
arrExists[arrNumbers[i]] = true;
}
}
// If we are here, then all the checks are OK, so return true
return true;
}
int main()
{
unsigned char arrNumbers[] = { 1, 0, 3, 2 };
std::cout << (ContainsConsecutiveValues(arrNumbers, sizeof(arrNumbers)) ? "Yes" : "No") << std::endl;
return 0;
}
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 14:18
Сионист
В каком месте сказано, что число на байты уже разобрано? Я даже не использую тот факт, что байты одной переменной хранятся подряд. Они так хранятся, но это не используется.
Re: Как лучше решить подзадачу?
Добавлено: 09 ноя 2015, 14:42
Romeo
Я поэтому и спросил, первым делом, как они хранятся. А ты так и не ответил на тот вопрос. И даже сейчас ответа не дал.
Если они гарантированно хранятся подряд (а было бы странно, если бы они не подряд хранились), то просто кастишь память к unsigned char* и используешь готовую функцию.