按照人的思维方式的方法,我想效率会比较高些。
程序代码:
#include <stdio.h>
struct carray { int d[3]; };
/* *1,*2,*3的个位数 */
char tab_digit[] = {
0, 0, 0, 1, 2, 3,
2, 4, 6, 3, 6, 9,
4, 8, 2, 5, 0, 5,
6, 2, 8, 7, 4, 1,
8, 6, 4, 9, 8, 7};
/* *1,*2,*3的进位 */
char tab_carray[] = {
0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 1, 1,
0, 1, 1, 0, 1, 2,
0, 1, 2, 0, 1, 2};
int have_digit(unsigned flags, int i)
{
return (flags >> i) & 1;
}
int set_digit(unsigned *flags, struct carray *_carray, int i)
{
unsigned flags2 = 0;
int *carray = _carray->d;
int a = carray[0] + tab_digit[3*i+0];
int b = carray[1] + tab_digit[3*i+1];
int c = carray[2] + tab_digit[3*i+2];
carray[0] = tab_carray[3*i+0] + !!(a >= 10);
carray[1] = tab_carray[3*i+1] + !!(b >= 10);
carray[2] = tab_carray[3*i+2] + !!(c >= 10);
flags2 = (1 << (a >= 10 ? a - 10 : a)) |
(1 << (b >= 10 ? b - 10 : b)) |
(1 << (c >= 10 ? c - 10 : c));
if (!flags2 || (flags2 & *flags))
return 0;
return (*flags |= flags2);
}
int next_digit(unsigned flags, int i)
{
flags |= (1 << ++i) - 1;
/* 可以直接用1条汇编指令优化 */
for (; i <= 9; ++i)
if (!have_digit(flags, i))
return i;
return 0;
}
void foo(void)
{
int i, j, k;
for (i = 1; i <= 9; ++i) { /* 9次循环 */
unsigned flags0 = 0;
struct carray carray0 = {{0}};
set_digit(&flags0, &carray0, i);
for (j = 0; (j = next_digit(flags0, j)); ) { /* 6次循环 */
struct carray carray1 = carray0;
unsigned flags1 = flags0;
if (!set_digit(&flags1, &carray1, j))
continue;
k = next_digit(flags1, 0);
if (set_digit(&flags1, &carray1, k) && flags1 == 0x3FE) {
if (!(carray1.d[0] | carray1.d[1] | carray1.d[2])) {
int n = i + j * 10 + k * 100;
printf("%d %d %d\n", n, 2*n, 3*n);
}
}
}
}
}
int main(void)
{
foo();
return 0;
}
[
本帖最后由 wfoo 于 2015-4-2 15:24 编辑 ]