這題理解題意之后就是一簡單的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
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 29 | 30 | 31 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | 12 | 13 | 14 | 15 | 16 | 17 | 18 | | 19 | 20 | 21 | 22 | 23 | 24 | 25 | | 26 | 27 | 28 | 29 | 30 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
常用鏈接
留言簿(1)
隨筆分類(99)
隨筆檔案(71)
好友鏈接
搜索
最新評論
閱讀排行榜
評論排行榜
|
|