Зимни Математически Състезания 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
|