【C】有趣的数字游戏

13*0217

先看问题：

    我们来玩一个数字游戏，我已经想好了一个三位数abc（a是百位，b是十位，c是个位）。并且告诉你acb、bac、bca、cab、cba的和是2012。
你知道我所想的那个数是多少吗？


可以自己试着猜下。
贴下我自己的代码：

[C] 纯文本查看 复制代码

/*
   根据公式 acb + bac + bca + cab + cba =2012,寻找这个三位数abc。
*/

#include <stdio.h>
int sum(int );

int main(void)
{
    int i;
    for(i = 100; i <= 999; ++i)
    {
        if(sum(i) == 2012)
        {
            printf("\n The three-bit number is :%d",i);
        }
    }
    return 0;
}

int sum(int x)
{
    int a = x/100;
    int b = x%100/10;
    int c = x%100%10;
    int sum = (b+c+a+b+a) + 10*(c+a+c+a+b) + 100*(a+b+b+c+c);
    return sum;
}

cyycoish

这是一个很有意思的题！我的解法如下：
三位数abc，a是百位，b是十位，c是个位。且acb+bac+bca+cab+cba=2012。求a,b,c,各为多少。
如果使用穷举法，要猜测899遍。所以我们考虑减少猜测次数。在899个可能答案的集合中再次筛选更小的子集。
我们观察等式 acb+bac+bca+cab+cba=2012，
可得：acb+bac+bca+cab+cba的结果是偶数。
因为：(acb+cab)+(bca+cba)+bac是偶数，
所以：c是偶数。且bac是偶数。
又：2012-bac=(acb+bca)+(cab+cba) 中 2012是偶数且bac是偶数，所以
(acb+bca)+(cab+cba)的和是偶数，进一步得a是偶数且b是偶数。
根据题意：abc是三位数，所以a不等于0。
综上所述：令集合A为a可能的值，集合B为b可能的值，集合C为c可能的值，则：
A={2,4,6,8}
B={0,2,4,6,8}
C=B
那么我们所需要的尝试次数为 |A| * |B| * |C|=100次！比原先估计的899次少799次。
由以上结论写出程序如下：

[C] 纯文本查看 复制代码

#include <stdio.h>

int main()
{
    int C[5] = { 0, 2, 4, 6, 8 }; // 10以内的偶数集合。
    int * B = C; // B=C
    int * A = C + 1; // A = {2,4,6,8}
    int a, b, c, i, j, k;
    for (i = 0; i < 4; ++i)
    {
        for (j = 0; j < 5; ++j)
        {
            for (k = 0; k < 5; ++k)
            {
                // 因为sum = (b+c+a+b+a) + 10 * (c+a+c+a+b) + 100 * (a+b+b+c+c);
                // => sum = 2a+2b+c + 10(2a+2c+b) + 100(2b+2c+a)
                // 在以上等式的右边 a b c 的2倍值频繁出现，所以将abc分别事先左移1位。
                // 左移运算效率高于乘以2，但是乘以10或100只能使用乘法运算。
                a = ((int) *(A + i)) << 1;
                b = ((int) *(B + j)) << 1;
                c = ((int) *(C + k)) << 1;
                if (2012 == (b + a + (c >> 1) + 10 * (a + c + (b >> 1)) + 100 * (b + c + (a >> 1))))
                    printf("%d%d%d\n", a >> 1, b >> 1, c >> 1);
            }
        }
    }
}

执行结果与楼主代码的执行结果相同。

Ayala

(acb+bca)+(cab+cba)的和是偶数，进一步得a是偶数且b是偶数。

这结论不对!

Ayala

acb + bac + bca +  cab + cba
=
a*2+a*20+a*100 +
b*2+b*10+b*200 +
c*1+c*20+c*200
=
122*a+212*b+221*c=2012
c是偶数
a∈{0,1,2,3,4,5,6,7,8,9}
b∈{0,1,2,3,4,5,6,7,8,9}
c∈{0,2,4,6,8}
3层循环 乘法计算量 10*10*5 * 3次
乘法转变位运算
122*a = 128*a - 4 *a - 2 * a
212*b = 256*b - 32*b - 8 * b - 4 * b
221*c = 256*c - 32*c - 2 * c - 1 * c
或
122*a = 64*a + 32*a + 16*a + 8*a + 2*a
212*b = 128*b + 64*b + 16*b + 4 *b
221*c = 128*c + 64*c + 16*c + 8 *c + 4*c +1*c

(8*a + 2*a + 4*b + 4 *c + 1 *c) and (8+4+2+1) = (8 + 4)

cyycoish

Ayala 发表于 2017-7-4 18:11
acb + bac + bca +  cab + cba
=
a*2+a*20+a*100 +

不错，ab不能同时为偶数，我的失误。那么接下来由你来进一步减少枚举次数。。。
这个问题交给你了。

13*0217

cyycoish 发表于 2017-7-4 17:50
这是一个很有意思的题！我的解法如下：
三位数abc，a是百位，b是十位，c是个位。且acb+bac+bca+cab+cba=201 ...

这个程序更厉害，速度快了11倍！！！

Ayala

[C] 纯文本查看 复制代码

//利用hash表降低降低乘法次数10*10*5*3 降低到10+10+5次乘法
int tab_A[10]={122*0,122*1,122*2,122*3,...};
int tab_B[10]={212*0,212*1,212*2,212*3,...};
int tab_C[5] ={221*0,221*2,221*4,221*6,...};

[C] 纯文本查看 复制代码

/*
   根据公式 acb + bac + bca + cab + cba =2012,寻找这个三位数abc。
*/
//利用hash表降低降低乘法次数10*10*5*3 降低到10+10+5次乘法 (9+9+4)次
int tab_A[10]={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
int tab_B[10]={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
int tab_C[5] ={0,221*2,221*4,221*6,221*8};


//
void foo(int tag)
{
	int c,b,a;
	for (c=0;c<10;c+=2)//5次加法 5次比较(减法)
	{
		for (b=0;b<10;b++)//5*10次加法 5*10次比较(减法)
		{
			for (a=0;a<10;a++)//5*10*10次加法 5*10*10次比较(减法)
			{
				//5*10*10*3次加法 5*10*10*3次比较(减法) 5*10*10*3次查找数据
				if (tag == tab_A[a] + tab_B[b] + tab_C[c>>1])
				{
					printf("a=%d\nb=%d\nc=%d\n",a,b,c);
					//goto done;
				}
			}
		}
	}
done:
	return;
}

int main()
{
	foo(2012);
	system("pause");
}

66ccff

分析：

bac		bca
	acb
cab		cba

五个数相加等于2012  易证得这五个数的十位和2*a+2*c+b>1   则五个数个位和c+2*b+2*a的个位必有2   则c+2*b+2*a可能等于02（舍） 12 22 32 42（5*9=45 要小于45）

（五个数个位和）
（五个数的十位和）
（五个数的十位和）
（五个数的十位和）
（五个数的十位和）

02	12	22	32	42
11	10	90	80	70
21	20	90	80	70
31	30	90	80	70
41	40	90	80	70

由上表图可得五个数个位和=02可舍去   而五个数个位和=22 32 42时 五个数的十位和均超过45故舍去   故c+2*b+2*a=12

[C] 纯文本查看 复制代码

void test()
{
	int c = 0,b = 0,a = 0;
	for (; c < 9; c++)
	{
		for (; b < 9; b++)
		{
			a = (12 - 2 * b - c) / 2;
			//printf("%d\n", (((2 * b + 2 * c + a) * 100) + ((2 * a + 2 * c + b) * 10)));
			if ((((2 * b + 2 * c + a) * 100) + ((2 * a + 2 * c + b) * 10)) == 2000)
				printf("a:%d, b:%d, c:%d\n", a, b, c);
		}
		b = 0;
	}
}

以81次即可算出结果（实际上72次即可）

66ccff

把数字倒着来枚举只需9次就可以得到结果    可以说是极限了吧！！！

Ayala

66ccff 发表于 2017-7-5 02:31
把数字倒着来枚举只需9次就可以得到结果    可以说是极限了吧！！！

9*9 * 2次乘法
忽略*2 以及除2的乘法 显示算法乘法次数太多 虽然循环次数很少 构造hash表也较难

Ayala

[C] 纯文本查看 复制代码

//
int tab_A[10]={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
int tab_B[10]={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
int tab_C[10]={0,221*1,221*2,221*3,221*4,221*5,221*6,221*7,221*8,221*9};

//
void foo(int tag)
{
	int c,b,a,t;
	for (c=0,t=(tag&1)?1:2;c<10;c+=t)// c与tag奇偶性相同 10/t次加法 10/t次比较(减法)
	{
		for (b=0;b<10;b++)//10/t*10次加法 10/t*10次比较(减法)
		{
			for (a=0;a<10;a++)//10/t*10*10次加法 10/t*10*10次比较(减法)
			{
				//10/t*10*10*3次加法 10/t*10*10*3次比较(减法) 10/t*10*10*3次查找数据
				if (tag == tab_A[a] + tab_B[b] + tab_C[c])
				{
					printf("a=%d\nb=%d\nc=%d\n",a,b,c);
					//goto done;
				}
			}
		}
	}
done:
	return;
}
//看起来循环次数很少 但是因为做了除法实际运行时间会比上一个更长
void foo2(tag)
{
	int c,b,a,t;
	for (c=0,t=(tag&1)?1:2;c<10;c+=t)// c与tag奇偶性相同 10/t次加法 10/t次比较(减法)
	{
		for (b=0;b<10;b++)//10/t*10次加法 10/t*10次比较(减法)
		{
			//10/t*10次除法
			if (0 == (tag - tab_B[b] - tab_C[c]) % 122) 
			{
				a = (tag - tab_B[b] - tab_C[c]) / 122;
				printf("a=%d\nb=%d\nc=%d\n",a,b,c);
				//goto done;
			}

		}
	}
done:
	return;
}
//没通用性的算法3 循环次数更少 但是更不可取 因为花了大量时间去做了不等式证明
void foo3()
/*
   122*a+212*b+221*c=2012
   0<=a<=9 ==> 0 <= 122*a <= 122*9=1098
   0<=b<=9 ==> 0 <= 212*b <= 212*9=1908
   0<=c<=9 ==> 0 <= 221*c <= 221*9=1989
   
   122*a=2012 - (212*b + 221*c)
   
   0<=2012 - (212*b + 221*c)<=1098
   212*b + 221*c >=2012 - 1098 = 914

   212*b + 212*c + 9*c >=914
   
   212*b + 212*c >=914-9*9=833
   
   b + c >= 833/212
   b + c >= 4
   
   a  = (2012-(212*b+221*c))/122 = 2012/122 - (212*b/122+221*c/122)
   16.4 < 2012/122 < 16.5
   
   16.5 > 212*b/122+221*c/122 >1.73*b + 1.81*c > 4*1.73=6.92
   
   16.5 / 1.73 < 9.54
   b+1.046*c <9.54
   
   0 <=0.046*c <=0.046*9=0.414
   b+c <=9 
*/
{
	int c,b,a;

	for (c=0;c<10;c+=2)
	{
		for (b=(c<=4)?(4-c):0;b+c<=9;b++)
		{
			if (0 == (2012 - tab_B[b] - tab_C[c]) % 122) 
			{
				a = (2012 - tab_B[b] - tab_C[c]) / 122;
				printf("a=%d\nb=%d\nc=%d\n",a,b,c);
				//goto done;
			}
		}
	}
done:
	return;
}
int main()
{
	foo(2012);
	foo2(2012);
	foo3();
	system("pause");
}

human_rights

我也来发一个。
0.随便挑一个三位整数，比如213。
1.把它的每一位按照从大到小的顺序排列->321。
2.然后再倒过来->123。
3.用321-123得到差->198。
把189作为新的三位整数代入步骤0。
不断迭代若干次后得到495。
任何除了999的三位整数经过若干次迭代后都会变成495。
（大概也就4+5+9层吧，再来一次迭代也行 ）

[C] 纯文本查看 复制代码

#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b)) // 返回较大的那个数
#define swap(a, b) ((b) = (a) + (b), (a) = (b) - (a), (b) -= (a)) // 交换两数

// 将三位整数的每一位按照从大到小的顺序排序
int max_seq(int h, int b, int t)
{
    if (max(h, b) == b)
        swap(h, b);
    if (max(h, t) == t)
        swap(h, t);
    if (max(b, t) == t)
        swap(b, t);
    return h * 100 + b * 10 + t;
}

// 将三位整数的每一位按照逆序重排
int rev_max_seq(int n)
{
    int h, b, t;
    h = n / 100;
    t = n / 10 - h * 10;
    b = n % 10;
    return b * 100 + t * 10 + h;
}

// 迭代器
int num_iterator(int n)
{
    int x, y;
    int h, b, t;
    h = n / 100;
    t = n / 10 - h * 10;
    b = n % 10;
    x = max_seq(h, b, t);
    y = rev_max_seq(x);   // 把每一位从大到小排序过的整数减去它的逆序
    printf("%d ", x -= y);
    return x;
}

int main(void)
{
    int i, j, n;
    
    for (j = 100; j < 1000; ++j)
    {
        printf("%d\n", j);
        for (n = j, i = 0; i < 30; ++i)
        {
            n = num_iterator(n);
        }
        putc(10, stdout);
    }
    
    return 0;
}

如果有读者能找到相关资料望告知。