Last active
October 28, 2017 00:55
-
-
Save pallove/e5bf9c75560e2c40ee16 to your computer and use it in GitHub Desktop.
计算123456789,所有3位数加法的组合。看了Milo Yip大神的知乎答案,赶忙来补充一下他的,以前写的可真烂。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
static int num_ten[] = { | |
1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000 | |
}; | |
int get_num(n, s, e) { | |
int d = num_ten[9 - e]; | |
int r = num_ten[e - s + 1]; | |
return n / d % r; | |
} | |
void puzzle_1(int n) { | |
// abc + def = ghi | |
int abc = get_num(n, 1, 3); | |
int def = get_num(n, 4, 6); | |
int ghi = get_num(n, 7, 9); | |
if (abc + def == ghi) { | |
printf("%d + %d = %d\n", abc, def, ghi); | |
} | |
} | |
void puzzle_2(int n) { | |
// ab - cd = ef = g * hi | |
int ab = get_num(n, 1, 2); | |
int cd = get_num(n, 3, 4); | |
int ef = get_num(n, 5, 6); | |
int g = get_num(n, 7, 7); | |
int hi = get_num(n, 8, 9); | |
if (ab - cd == ef && ef == g * hi) { | |
printf("%d - %d = %d = %d * %d\n", ab, cd, ef, g, hi); | |
} | |
} | |
void puzzle_3(int n) { | |
// abc:def:ghi = 1:2:3 | |
int abc = get_num(n, 1, 3); | |
int def = get_num(n, 4, 6); | |
int ghi = get_num(n, 7, 9); | |
if (abc * 2 == def && abc * 3 == ghi) { | |
printf("%d:%d:%d\n", abc, def, ghi); | |
} | |
} | |
void f(int i, int m, int r, void (*output)(int)) { | |
if (i == 0) { | |
output(r); | |
} | |
else { | |
for (int j = 1; j < 10; j++) { | |
if (((1 << j) & m) == 0) { | |
f(i - 1, m | (1 << j), r * 10 + j, output); | |
} | |
} | |
} | |
} | |
int main() { | |
f(9, 1, 0, puzzle_1); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <time.h> | |
struct result | |
{ | |
int _100a, _100b, _100c; | |
int _10a, _10b, _10c; | |
int _a, _b, _c; | |
}; | |
inline int check_num(char *nums, int value) | |
{ | |
return nums[value] != '0'; | |
} | |
inline void take_num(char *nums, int value) | |
{ | |
nums[value] = '0'; | |
} | |
inline void set_num(char *nums, int value) | |
{ | |
nums[value] = value; | |
} | |
inline int check_value(struct result *r) | |
{ | |
int a = r->_100a * 100 + r->_10a * 10 + r->_a; | |
int b = r->_100b * 100 + r->_10b * 10 + r->_b; | |
int c = r->_100c * 100 + r->_10c * 10 + r->_c; | |
/*return a < b && a + b == c;*/ | |
return a + b == c; | |
} | |
int count = 0; | |
void check_exp(char *nums, int add, struct result *r, int level) | |
{ | |
int i = 1; | |
for(; i < 10; i++) { | |
int j = 1; | |
if (check_num(nums, i)) { | |
for(; j < 10; j++) { | |
/*if (j == i) continue;*/ | |
if (j == i) continue; | |
if (level == 1) { | |
if (j > i) continue; | |
if (j + i > 9) continue; | |
} | |
int k = 1; | |
if (check_num(nums, j)) { | |
for(; k < 10; k++) { | |
if (k == j || k == i) continue; | |
if (check_num(nums, k)) { | |
int addten = add == 1 ? 10 : 0; | |
int plus = 0; | |
int ok = 0; | |
if (i + j == k + addten) { | |
ok = 1; | |
} | |
else if (i + j == k - 1 + addten) { | |
ok = level != 3; | |
plus = 1; | |
} | |
if (ok) { | |
take_num(nums, i); | |
take_num(nums, j); | |
take_num(nums, k); | |
switch(level) { | |
case 1: | |
r->_100a = i; | |
r->_100b = j; | |
r->_100c = k; | |
check_exp(nums, plus, r, level + 1); | |
break; | |
case 2: | |
r->_10a = i; | |
r->_10b = j; | |
r->_10c = k; | |
check_exp(nums, plus, r, level + 1); | |
break; | |
case 3: | |
r->_a = i; | |
r->_b = j; | |
r->_c = k; | |
/*if (check_value(r)) {*/ | |
++count; | |
/*printf("result:%d%d%d + %d%d%d = %d%d%d\n", r->_100a, r->_10a, r->_a, r->_100b, r->_10b, r->_b, r->_100c, r->_10c, r->_c);*/ | |
/*}*/ | |
break; | |
} | |
// return flag | |
set_num(nums, i); | |
set_num(nums, j); | |
set_num(nums, k); | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
int main() | |
{ | |
clock_t start, end; | |
char nums[] = "0123456789"; | |
struct result r; | |
int times = 1000; | |
start = clock(); | |
while(times--) { | |
check_exp(nums, 0, &r, 1); | |
} | |
end = clock(); | |
printf("count:%d, use time:%lu\n", count, end - start); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
果然。。。