729. Расстояние Хемминга

Расстоянием Хемминга для двух битовых строк называется количество позиций, в которых эти строки различны. Рассмотрим две строки А и В:

A = 0 1 0 0 1 0 1 0 0 0

B = 1 1 0 1 0 1 0 1 0 0

A XOR B = 1 0 0 1 1 1 1 1 0 0

Расстояние Хемминга между ними равно 6, поскольку строка A XOR B содержит в бинарном представлении 6 единиц. В задаче необходимо найти все строки, которые находятся на Хемминговом расстоянии h от строки, содержащей n нулей.

Вход. Первая строка содержит количество тестов, после которой следует пустая строка. Каждый тест состоит из одной строки, содержащей длину битовых строк n и расстояние Хемминга h, 1 £ h £ n £ 16. Между тестами находится пустая строка.

Выход. Для каждого теста вывести набор всех строк длины n, находящихся на Хемминговом расстоянии h от строки, состоящей из n нулей. Строки выводить по возрастанию в лексикографическом порядке. Между тестами выводить пустую строку.

Пример входа

1

4 2

Пример выхода

0011

0101

0110

1001

1010

1100

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Для каждого теста следует сгенерировать все последовательности длины n из нулей и единиц, в которых содержится в точности h единиц.

Реализация алгоритма

Процедура hamming принимает на вход два параметра: pos – текущая позиция и h – количество единиц, которое следует еще использовать в последовательности. Последовательности генерируются в массиве m. В теле процедуры пробуем на позицию pos поставить 0 или 1. В начале процедуры проверяем условия: не стоит ли уже в массиве единиц больше чем надо (h >= 0) и число пустых мест n – pos не должно быть меньшим количества единиц h, которое следует расставить (h > n – pos). Массив m будет выводиться когда pos >= n, при этом обязательно h = 0.

void hamming(int pos,int h)

{

int i;

if ((h < 0) || (h > n - pos)) return;

if (pos >= n)

{

for(i=0;i<n;i++) printf("%d",m[i]);

printf("\n");

return;

}

for(i=0;i<=1;i++)

{

m[pos] = i;

hamming(pos+1,h-i);

}

}

Основной цикл программы. Читаем количество тестов tests. Для каждого теста вводим значения n и h и при помощи процедуры hamming генерируем все требуемые последовательности.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&h);

hamming(0,h);

if (tests) printf("\n");

}