变态的算法题

koolcoy

改一行代码：typedef Integer<4> Bigint
{:3_189:}
witch:~/Documents/workspace/Flower$ time ./a.out 31
1927890457142960697580636236639
2309092682616190307509695338915
1145037275765491025924292050346

real        2m55.434s
user        2m52.737s
sys        0m0.200s

koolcoy

把sprintf调用去掉后竟然{:3_182:}{:3_182:}{:3_190:}{:3_190:}

witch:~/Documents/workspace/Flower$ time ./a.out 21
449177399146038697307
128468643043731391252

real        0m2.424s
user        0m2.030s
sys        0m0.003s
witch:~/Documents/workspace/Flower$ time ./a.out 31
1927890457142960697580636236639
2309092682616190307509695338915
1145037275765491025924292050346

real        0m26.691s
user        0m26.639s
sys        0m0.020s

1. 
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. #include <cstdlib>
   
5. 
   
6. template<int LENGTH>
   
7. class Integer {
   
8.         typedef unsigned int U32;
   
9.         typedef unsigned long long U64;
   
10. public:
    
11.         Integer() {
    
12.                 for (int i = 0; i < LENGTH; ++i) {
    
13.                         data[i] = 0;
    
14.                 }
    
15.         }
    
16. 
    
17.         Integer(U32 that) {
    
18.                 copy(that);
    
19.         }
    
20. 
    
21.         const Integer& operator = (U32 that) {
    
22.                 copy(that);
    
23.                 return *this;
    
24.         }
    
25. 
    
26.         const Integer& operator += (const Integer& that) {
    
27.                 int carry = 0;
    
28.                 for (int i = 0; i < LENGTH; ++i) {
    
29.                         data[i] += that.data[i] + carry;
    
30.                         if (data[i] > BASE) {
    
31.                                 carry = data[i] / BASE;
    
32.                                 data[i] = data[i] % BASE;
    
33.                         } else {
    
34.                                 carry = 0;
    
35.                         }
    
36.                 }
    
37.                 return *this;
    
38.         }
    
39. 
    
40.         const Integer& operator *= (U32 that) {
    
41.                 U64 carry = 0;
    
42.                 for (int i = 0; i < LENGTH; ++i) {
    
43.                         U64 tmp = (U64)data[i] * (U64)that + carry;
    
44.                         if (tmp > BASE) {
    
45.                                 carry = tmp / BASE;
    
46.                                 data[i] = tmp % BASE;
    
47.                         } else {
    
48.                                 carry = 0;
    
49.                                 data[i] = tmp;
    
50.                         }
    
51.                 }
    
52.                 return *this;
    
53.         }
    
54. 
    
55.         Integer operator + (const Integer& that) const {
    
56.                 Integer tmp = *this;
    
57.                 return tmp += that;
    
58.         }
    
59. 
    
60.         Integer operator * (U32 that) const {
    
61.                 Integer tmp = *this;
    
62.                 return tmp *= that;
    
63.         }
    
64. 
    
65.         bool operator > (const Integer& that) const {
    
66.                 for (int i = LENGTH - 1; i >= 0; --i) {
    
67.                         if (data[i] > that.data[i]) {
    
68.                                 return true;
    
69.                         } else if (data[i] < that.data[i]) {
    
70.                                 return false;
    
71.                         }
    
72.                 }
    
73.                 return false;
    
74.         }
    
75. 
    
76.         bool operator < (const Integer& that) const {
    
77.                 return std::memcmp(data, that.data, sizeof(data)) != 0
    
78.                                 && !(*this > that);
    
79.         }
    
80. 
    
81.         void validate(char digit[9]) const {
    
82.                 char decimal[LENGTH * WIDTH + 1];
    
83.                 toString(decimal);
    
84. 
    
85.                 char actual[10] = {0};
    
86.                 for (int i = 0; i < WIDTH * LENGTH; ++i) {
    
87.                         ++actual[decimal[i] - '0'];
    
88.                 }
    
89.                 if (std::memcmp(actual + 1, digit, 9) == 0) {
    
90.                         output(decimal);
    
91.                 }
    
92.         }
    
93. 
    
94.         void toString(char* decimal) const {
    
95.                 for (int i = 0; i < LENGTH; ++i) {
    
96.                         convertChunk(data[LENGTH - i - 1], decimal + WIDTH * i);
    
97.                 }
    
98.                 decimal[LENGTH * WIDTH] = 0;
    
99.         }
    
100. 
     
101. private:
     
102.         enum {
     
103.                 BASE = 1000000000, /* This is 10^9 */
     
104.                 WIDTH = 9
     
105.         };
     
106.         U32 data[LENGTH];
     
107. 
     
108.         static void output(const char* decimal) {
     
109.                 int i = 0;
     
110.                 while (decimal[i] == '0') {
     
111.                         ++i;
     
112.                 }
     
113.                 printf("%s\n", decimal + i);
     
114.         }
     
115. 
     
116.         static void convertChunk(U32 digit, char* decimal) {
     
117.                 for (int i = 0; i < WIDTH; ++i) {
     
118.                         decimal[WIDTH - 1 - i] = digit % 10 + '0';
     
119.                         digit /= 10;
     
120.                 }
     
121.         }
     
122. 
     
123.         void copy(U32 that) {
     
124.                 data[0] = that % BASE;
     
125.                 data[1] = that / BASE;
     
126.                 for (int i = 2; i < LENGTH; ++i) {
     
127.                         data[i] = 0;
     
128.                 }
     
129.         }
     
130. };
     
131. 
     
132. typedef Integer<SIZE> Bigint;
     
133. 
     
134. Bigint MIN;
     
135. Bigint MAX;
     
136. Bigint** TABLE;
     
137. 
     
138. void createSumTable(int length) {
     
139.         TABLE = new Bigint*[9];
     
140.         for (int i = 0; i < 9; ++i) {
     
141.                 TABLE[i] = new Bigint[length];
     
142. 
     
143.                 TABLE[i][0] = i + 1;
     
144.                 for (int j = 1; j < length; ++j) {
     
145.                         TABLE[i][0] *= (i + 1);
     
146.                 }
     
147. 
     
148.                 for (int j = 1; j < length; ++j) {
     
149.                         TABLE[i][j] = TABLE[i][0] * (j + 1);
     
150.                 }
     
151.         }
     
152. }
     
153. 
     
154. void initialize(int length) {
     
155.         MIN = 10;
     
156.         for (int i = 0; i < length - 2; ++i) {
     
157.                 MIN *= 10;
     
158.         }
     
159.         MAX = MIN * 10;
     
160. 
     
161.         createSumTable(length);
     
162. }
     
163. 
     
164. void search(int left, int index, Bigint partialSum, char* digit) {
     
165.         if (index < 8 && left > 0) {
     
166.                 search(left, index + 1, partialSum, digit);
     
167.         }
     
168.         for (int count = 1; count < left + 1; ++count) {
     
169.                 digit[index] = count;
     
170.                 Bigint sum = partialSum + TABLE[index][count - 1];
     
171. 
     
172.                 if (sum > MAX) {
     
173.                         break;
     
174.                 }
     
175.                 if (sum > MIN) {
     
176.                         sum.validate(digit);
     
177.                 }
     
178.                 if (index < 8 && left > count) {
     
179.                         search(left - count, index + 1, sum, digit);
     
180.                 }
     
181.         }
     
182.         digit[index] = 0;
     
183. }
     
184. 
     
185. int main(int argc, char** argv) {
     
186.         int length = 0;
     
187.         if (argc != 2 || sscanf(argv[1], "%d", &length) != 1 || length <= 0) {
     
188.                 std::fprintf(stderr, "Usage: %s <length>\n", argv[0]);
     
189.         }
     
190. 
     
191.         initialize(length);
     
192.         char* digit = (char*)std::calloc(length, 1);
     
193.         search(length, 0, Bigint(0), digit);
     
194.         return 0;
     
195. }
     

复制代码

koolcoy

回复 89# KBTiller


    显然不一样，按这种方法穷举的话，其复杂度是O(N^9)，如果按各个数位上的数字来枚举的话，复杂度O(9^N)，一个是多项式级的复杂度，另外一个是指数级的复杂度。复杂度跟解空间是等价的。

koolcoy

两种算法的组合数是不一样的，这两种算法有着本质的区别。
如果按照“各个数位上的数字来枚举”的话，即10楼的算法，数字 123XXXX和321XXXX是两种不同的情况，需要计算两次。
如果按照“1出现的次数为n1，2出现的次数n2，3出现的次数为n3...”这种方法来枚举的话123XXXX和321XXXX是同一种情况，只需要计算一次。

koolcoy

回复 94# KBTiller

但是有个问题，按照10楼得算法，当你验证后发现123XXXX不满足条件，怎么知道321XXXX是否满足条件呢？如果不知道的话，那么你就还要验证321XXXX是否满足条件。也就是说对于123XXXX和321XXXX这两个数字你需要验证两次。但是按照我的那种算法，如果发现123XXXX不满足条件后，我就可以肯定321XXXX不满足条件。

ps: 对于21位的数字，俺已经突破1.4秒了{:3_203:}

koolcoy

回复 97# KBTiller

Pentium(R) Dual-Core  CPU  E5700  @ 3.00GHz 32位cygwin