这题理解题意之后就是一简单的dfs,是每一个都相差不小于d。
首先选取一个起始点，然后对于这个点进行dfs寻找，当找到了或者不可能找到时返回，中间的相差不小于d可以把两个数换成二进制然后再比较不同的位置。实现也不算难
官方的如下，官方的就是先求出每两个数的二进制的位差，以免后面再重复求
  官方
1 There are only a few tools we need to solve this problem. First of all, we can use basic techniques to find the Nth bit of a number M: counting the least significant bit as bit 0, the next bit as bit 1, etc., we can find the value of that bit through the expression
2
3 int Nth_bit = (1 << N) & M;
4
5In other words, we are shifting the number 1 left by N spaces, and then performing a binary AND on the resulting number with our original number, which will leave either a 1 in the Nth bit or a 0. So the first thing we have to do is find out the distance between each pair of numbers within the set of all numbers with B bits (0..2B-1).
6We also know that 0 can be one of the numbers in the set, because if the minimum number in the set were N instead of 0, we could subtract N from each number in the set and they would still be the same distance apart. The limits on the problem are low enough that we can do a DFS, and as soon as we hit a solution we can output it and exit.
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <iostream.h>
11#define MAX (1 << 8 + 1)
12#define NMAX 65
13#define BMAX 10
14#define DMAX 10
15
16int nums[NMAX], dist[MAX][MAX];
17int N, B, D, maxval;
18FILE *in, *out;
19
20void findgroups(int cur, int start)  {
21 int a, b, canuse;
22 char ch;
23  if (cur == N) {
24 for (a = 0; a < cur; a++) {
25 if (a % 10)
26 fprintf(out, " ");
27 fprintf(out, "%d", nums[a]);
28 if (a % 10 == 9 || a == cur-1)
29 fprintf(out, "\n");
30 }
31 exit(0);
32 }
33 for (a = start; a < maxval; a++) {
34 canuse = 1;
35 for (b = 0; b < cur; b++)
36 if (dist[nums[b]][a] < D) {
37 canuse = 0;
38 break;
39 }
40 if (canuse) {
41 nums[cur] = a;
42 findgroups(cur+1, a+1);
43 }
44 }
45 }
46
47int main() {
48 in = fopen("hamming.in", "r");
49 out = fopen("hamming.out", "w");
50 int a, b, c;
51 fscanf(in, "%d%d%d", &N, &B, &D);
52 maxval = (1 << B);
53 for (a = 0; a < maxval; a++)
54 for (b = 0; b < maxval; b++) {
55 dist[a][b] = 0;
56 for (c = 0; c < B; c++)
57 if (((1 << c) & a) != ((1 << c) & b))
58 dist[a][b]++;
59 }
60 nums[0] = 0;
61 findgroups(1, 1);
62 return 0;
63}
64
65
|
|
常用链接
留言簿(1)
随笔分类(99)
随笔档案(71)
好友链接
搜索
最新评论
阅读排行榜
评论排行榜
|
|