Текущ брой на Списание ИнфоМан
 


Зимни Математически Състезания 2005, Задача B3. СИГНАЛИ

Уловието на задачата може да прочетете тук.

Решение

Тъй като задачата е с релативно оценяване, могат да бъдат написани различни решения, някои от които намират по-добри отговори, а други - не толкова. Възможно е например да се използва рекурсия или грийди стратегия за намиране на отговора за малките стойности на N. Друг лесен подход е да направим следното: вземаме всички floor(N/2) – битови числа и ги удвояваме (всеки бит го написваме по 2 пъти). Така например ако искаме да намерим отговора за 4, вземаме всички двоични числа с2 бита, т.е.

00

01

10

11

и ги удвояваме, получавайки:

0000

0011

1100

1111

Ако N e 5, тогава отново вземаме 2-битовитечисла и прибавяме в началото произволен бит, например 1, т.е. за N=5 ще имаме

10000

10011

11100

11111

Това решение гарантира 2n/2 числа.

Оптималното решение, известно до момента, може да бъде прочетено в статията на N.J.A. Sloane “On Singe-Deletion-Correction Codes”. Там е доказано, че оптимален за малки стойности на N е следният алгоритъм:

1.      На всяко двоично число Xс N бита x1, x2, …, xn съпоставяме едно число T, което се дава по формулата

T = (1*x1+ 2*x 2 + 3*x3 + … + n*xn) mod (n+1)

2.      Разделяме N-битовите числа на групи в зависимост от числото T, което им е съпоставено. Така се получават n+1 групи. Гарантирано е, че във всяка от групите числата не са противоречиви. Освен това е изпълнено, че групата от числа, които дават остатък 0, е най голяма. Тогава е очевидно, че в нея има поне 2n/(n+1) числа.

Сложността на това решение е O(n*2n)– за всяко n-битово число намираме стойността T и в зависимост от тази стойност го извеждаме или не.

Примерна реализация:

#include <stdio.h>

int N;
char filename[128];
int r[1024*1024];
int count = 0;

int main () {

	int i;
	int j;
	int T;

	FILE *f;

	scanf("%d\n%s",&N, filename);

	f = fopen ( filename, "w");

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

		int pos = 1;
		int X = i;

		T = 0;

		while (X!=0) {

			T+=(X%2) * pos;
			pos++;
			T%=(N+1);
			X/=2;

		}

		if (T==0) {

			r[count++] = i;

		}

	}

	fprintf(f,"%d\n",count);

	for (i = 0;i<count;i++) {

		int X = r[i];

		for (j = 0;j<N;j++) {
			
			fprintf(f,"%d",X%2);
			X/=2;

		}

		fprintf(f,"\n");

	}

	return 0;
}

Автор: Слави Маринов


обратно към брой 27