 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Генерация тестов
|
|
1.3.1. Генерация последовательности всех подмножеств заданного множества
Подача на вход алгоритма последовательности всех подмножеств некоторого множества X может потребоваться для полного тестирования алгоритма или для решения задачи полным перебором в случаях, когда эффективного алгоритма не существует. Если мощность множества |X| = n, мощность множества всех его подмножеств — булеана (общее количество тестов) |2X| = 2n.
Если n ≤ 32, последовательность подмножеств проще всего получить в форме машинных слов по очевидному алгоритму:
for (w = 0; w < 2n; w++) yield (w).
Здесь и далее yield (w) — некоторая функция, использующая множество w.
Для практических целей часто бывает удобнее, чтобы каждое подмножество в последовательности отличалось от предыдущего появлением или исчезновением ровно одного элемента (n-битный код Грея). Такую последовательность можно получить небольшой модификацией указанного выше алгоритма:
for (int i = 0; i < 2n; i++) { w = i ^ (i ≫ 1); yield (w); }.
1.3.2. Генерация перестановок
Некоторые алгоритмы требуют подачи на вход полного множества X в виде последовательности, отличающейся порядком расположения элементов. Пример такого алгоритма — проверка двух графов одинаковой мощности на изоморфизм, заключающаяся в подборе такой нумерации вершин второго графа, чтобы его рёбра совпали с рёбрами первого графа. Функция Neith() генерирует все перестановки множества чисел от 1 до n в виде последовательности, в которой на каждом шаге меняются местами два смежных элемента.
inline void Swap(int &p, int &q) { int r (p); p = q; q = r; }
void Neith(int n)
{ int *X = new int[ n ], *C = new int[ n ], *D = new int[ n ], i, j, k, x;
for (i = 0; i < n; i++) // Инициализация
{ X[ i ] = i + 1; C[ i ] = 0; D[ i ] = 1; }
yield (X);
C[n – 1] = –1; i = 0;
while (i < n – 1) // Цикл перестановок
{ i = 0; x = 0;
while (C[ i ] == (n – i – 1))
{ D[ i ] =!D[ i ]; C[ i ] = 0; if (D[ i ]) x++; i++; }
if (i < n – 1) // Вычисление позиции k и перестановка смежных
{ k = D[ i ]? C[ i ] + n: n – i – C[ i ] + x – 2; Swap(X[ k ], X[k + 1]); }
yield (X);
C[ i ]++;
}
}.
1.3.3. Генерация случайного подмножества
Если тестирование алгоритма ведётся вручную, его выполняют не полным перебором, а подачей на вход алгоритма некоторого разумного количества случайных тестов, генерацию которых тоже можно поручить машине. Для получения случайного машинного слова можно использовать функцию rand() из стандартной библиотеки stdlib. Функция возвращает псевдослучайное целое в интервале 0…32767. Случайное слово из n битов можно получить, выделив его из возвращаемого значения:
w = rand() %2n
или просто положить w = rand() и игнорировать лишние биты.
Для получения слова типа long можно использовать функцию дважды и объединить возвращаемые значения:
w = (long) (rand() ≪ 16) | rand().
Массив случайных битов получить ещё проще:
for (int i = 0; i < n; i++) X[ i ] = rand() % 2.
Следует отметить, что датчик rand() даёт не случайные, а псевдослучайные числа. При каждом новом запуске программы последовательность этих чисел будет повторяться. Это очень удобно для отладки, но когда отладка закончена, в начало функции main() нужно вставить строку srand(time(NULL)), которая обеспечит запуск датчика со случайной точки, зависящей от текущего времени. Время запрашивается функцией time() из стандартной библиотеки time.h.
Получить случайную строку тоже проще всего генерированием последовательности битов:
int k = 0;
for (int i = 0; i < m; i++) if (rand()%2) S[k++] = f(i).
Результат — строка символов S — множество со случайной мощностью k ∈ [0…m – 1].
Все рассмотренные генераторы создают множества, в которых каждый элемент универсума появляется с вероятностью 0,5. Может получиться и пустое, и полное множество, но в среднем мощность получается близкой к m/2. Если требуется получать множества почти пустые или почти полные, нужно сделать так, чтобы вероятности появления 0 или 1 различались. Так, в общем случае генератор массива битов может выглядеть так:
for (int i = 0; i < m; i++) X[ i ] = (rand() % p > q).
В этом генераторе вероятность появления 1 зависит от соотношения значений констант p и q. Так, например, при p = 5 датчик будет давать с равной вероятностью элементы множества {0, 1, 2, 3, 4}, и при q = 3 вероятность генерации 1 будет 0,2, а при q = 0— 0,8.
1.3.4. Случайное подмножество заданной мощности
Все рассмотренные ранее датчики генерировали множество случайной мощности. Если же требуется случайное подмножество заданной мощности k, например, в форме массива, его иногда пытаются получить следующим алгоритмом:
for (int i = 0; i < k; i++) X[ i ] = rand() % m.
Этот способ не годится, потому что он даёт не множество, а последовательность, в которой возможны повторы, и их будет много, если k близко к m, т. е. фактическая мощность множества будет меньше заданного k.
Можно усовершенствовать этот алгоритм: повторять генерацию очередного элемента множества до тех пор, пока не кончатся совпадения с уже имеющимися. Способ рекомендуется при больших m(k ≪ m). Если же m не намного больше k, то с ростом k вероятность получить новый элемент множества очень быстро уменьшается, а при k = m алгоритм может вообще никогда не остановиться.
Способ, рекомендуемый для небольших m: сформировать в памяти для результата массив — универсум, на каждом шаге убирать сгенерированный элемент множества в его начало и разыгрывать оставшиеся. Результат будет получен за время O (k).
for (int i = 0; i < m; i++) X[ i ] = i + 1; //Формирование универсума {1 … m}
for (int i = 0; i < k; i++) // Генерация подмножества мощностью k
{ int p = rand() % (m – i); // Случайный выбор среди оставшихся
if (p) Swap (X[ i + p ], X [ p ]); } // Если p ≠ 0, обменять местами.
Результат — первые k элементов массива X. Способ легко приспособить для генерации последовательности подмножеств нарастающей мощности: использовать массив X в качестве теста после каждого добавления в него очередного элемента. Если взять k = m – 1, получается алгоритм генерации случайной перестановки. Без ограничения общности он может использовать очередную перестановку для генерации следующей, не требуя в этом случае для новой перестановки обязательного перезапуска датчика случайных чисел.
1.3.5. Практикум по теме
Преобразовать ранее созданные программы так, чтобы исходные множества генерировались автоматически.
1.3.6. Контрольные вопросы
1. Можно ли применить для тестирования вашего алгоритма генератор множества всех подмножеств?
2. Какой из способов генерации случайного множества вы считаете самым удобным?
3. Целесообразно ли для вашего варианта обработки множеств применять несимметричный генератор тестов?
4. Можно ли применять для генерации подмножества заданной мощности генерацию случайных битов с остановкой по достижении нужного их количества?
Дата публикования: 2015-02-20; Прочитано: 499 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
