Матч 272, Расстояние Хемминга (HammingDistance)

Дивизион 2, Уровень 1

Расстоянием Хемминга между двумя строками, содержащими бинарный код числа, называется количество позиций, в которых они отличаются. Например, строки “11010” и “01100” различаются в первой, третьей и четвертой позициях, поэтому расстояние между ними равно 3.

Массив строк numbers содержит набор строк одинаковой длины. Необходимо среди них найти две строки, расстояние Хемминга между которыми наименьшее.

Класс: HammingDistance

Метод: int minDistance(vector<string> numbers)

Ограничения: numbers содержит от 2 до 50, все элементы numbers содержат одинаковое количество символов ‘0’ или ‘1’.

Вход. Массив строк numbers.

Выход. Наименьшее расстояние Хемминга между двумя строками из массива numbers.

Пример входа

numbers

{"11010", "01100"}

{"00", "01", "10", "11"}

{"000", "011", "101", "110"}

{"000000", "000111", "111000", "111111"}

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

3

1

2

3

РЕШЕНИЕ

элементарные вычисления

Перебираем все пары строк, для каждой из которой вычисляем расстояние Хемминга при помощи функции Hamming. Среди всех расстояний находим наименьшее.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

int Hamming(string a, string b)

{

int i, c;

for(c = i = 0; i < a.size(); i++)

if (a[i] != b[i]) c++;

return c;

}

class HammingDistance

{

public:

int minDistance(vector<string> numbers)

{

int i, j, temp, res = 2000000000;

for(i = 0; i < numbers.size(); i++)

for(j = i + 1; j < numbers.size(); j++)

{

temp = Hamming(numbers[i],numbers[j]);

if (temp < res) res = temp;

}

return res;

}

};