Разбить число на байты и проверить их последовательность

[Сионист]

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

[somewhere]

я бы подсказал, но мне противопоказан комп

[Сионист]

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

[Romeo]

Ну изъясняешься ты конечно. Голову сломал, пока прочёл. Особенно последний ответ...

Как хранится число? Как массив байтов?

Код: Выделить всё

unsinged char number[255];

Просто для таких больших чисел встроенного типа нет.

Самое простое - это отсортировать байты по не убыванию qsort'ом, затем однократно пройти увеличивая счётчик и сравнивая его с текущим байтом. Если все сравнения были успешны, значит говорим да, иначе - говорим нет. Количество действий N*log(N) + 2*N + С. Итого сложность алгоритма O(N) = N*log(N). Думаю, улучшить это значение без дополнительной памяти уже не получится.

[somewhere]

Можно улучшить со сложностью N, т.е. однопроходно, но это в личке =)

[Сионист]

Как хранится число? Как массив байтов?

Нет конечно.

Просто для таких больших чисел встроенного типа нет.

Восемь жалких байт - это уже большое число?

[Сионист]

Количество действий N*log(N) + 2*N + С. Итого сложность алгоритма O(N) = N*log(N).

У меня уже получилось 3N шагов цикла в худшем случае и N+1 в лучшем.

[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;
}

[Сионист]

В каком месте сказано, что число на байты уже разобрано? Я даже не использую тот факт, что байты одной переменной хранятся подряд. Они так хранятся, но это не используется.

[Romeo]

Я поэтому и спросил, первым делом, как они хранятся. А ты так и не ответил на тот вопрос. И даже сейчас ответа не дал.

Если они гарантированно хранятся подряд (а было бы странно, если бы они не подряд хранились), то просто кастишь память к unsigned char* и используешь готовую функцию.