【C】有趣的数字游戏

13*0217

先看问题：

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


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

1. /*
   
2.    根据公式 acb + bac + bca + cab + cba =2012,寻找这个三位数abc。
   
3. */
   
4. 
   
5. #include <stdio.h>
   
6. int sum(int );
   
7. 
   
8. int main(void)
   
9. {
   
10.     int i;
    
11.     for(i = 100; i <= 999; ++i)
    
12.     {
    
13.         if(sum(i) == 2012)
    
14.         {
    
15.             printf("\n The three-bit number is :%d",i);
    
16.         }
    
17.     }
    
18.     return 0;
    
19. }
    
20. 
    
21. int sum(int x)
    
22. {
    
23.     int a = x/100;
    
24.     int b = x%100/10;
    
25.     int c = x%100%10;
    
26.     int sum = (b+c+a+b+a) + 10*(c+a+c+a+b) + 100*(a+b+b+c+c);
    
27.     return sum;
    
28. }
    

复制代码

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次。
由以上结论写出程序如下：

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int C[5] = { 0, 2, 4, 6, 8 }; // 10以内的偶数集合。
   
7.     int * B = C; // B=C
   
8.     int * A = C + 1; // A = {2,4,6,8}
   
9.     int a, b, c, i, j, k;
   
10.     for (i = 0; i < 4; ++i)
    
11.     {
    
12.         for (j = 0; j < 5; ++j)
    
13.         {
    
14.             for (k = 0; k < 5; ++k)
    
15.             {
    
16.                 // 因为sum = (b+c+a+b+a) + 10 * (c+a+c+a+b) + 100 * (a+b+b+c+c);
    
17.                 // => sum = 2a+2b+c + 10(2a+2c+b) + 100(2b+2c+a)
    
18.                 // 在以上等式的右边 a b c 的2倍值频繁出现，所以将abc分别事先左移1位。
    
19.                 // 左移运算效率高于乘以2，但是乘以10或100只能使用乘法运算。
    
20.                 a = ((int) *(A + i)) << 1;
    
21.                 b = ((int) *(B + j)) << 1;
    
22.                 c = ((int) *(C + k)) << 1;
    
23.                 if (2012 == (b + a + (c >> 1) + 10 * (a + c + (b >> 1)) + 100 * (b + c + (a >> 1))))
    
24.                     printf("%d%d%d\n", a >> 1, b >> 1, c >> 1);
    
25.             }
    
26.         }
    
27.     }
    
28. }
    

复制代码

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

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

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

复制代码

1. 
   
2. /*
   
3.    根据公式 acb + bac + bca + cab + cba =2012,寻找这个三位数abc。
   
4. */
   
5. //利用hash表降低降低乘法次数10*10*5*3 降低到10+10+5次乘法 (9+9+4)次
   
6. int tab_A[10]={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
   
7. int tab_B[10]={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
   
8. int tab_C[5] ={0,221*2,221*4,221*6,221*8};
   
9. 
   
10. 
    
11. //
    
12. void foo(int tag)
    
13. {
    
14.         int c,b,a;
    
15.         for (c=0;c<10;c+=2)//5次加法 5次比较(减法)
    
16.         {
    
17.                 for (b=0;b<10;b++)//5*10次加法 5*10次比较(减法)
    
18.                 {
    
19.                         for (a=0;a<10;a++)//5*10*10次加法 5*10*10次比较(减法)
    
20.                         {
    
21.                                 //5*10*10*3次加法 5*10*10*3次比较(减法) 5*10*10*3次查找数据
    
22.                                 if (tag == tab_A[a] + tab_B[b] + tab_C[c>>1])
    
23.                                 {
    
24.                                         printf("a=%d\nb=%d\nc=%d\n",a,b,c);
    
25.                                         //goto done;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.         }
    
30. done:
    
31.         return;
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.         foo(2012);
    
37.         system("pause");
    
38. }

复制代码

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

1. void test()
   
2. {
   
3.         int c = 0,b = 0,a = 0;
   
4.         for (; c < 9; c++)
   
5.         {
   
6.                 for (; b < 9; b++)
   
7.                 {
   
8.                         a = (12 - 2 * b - c) / 2;
   
9.                         //printf("%d\n", (((2 * b + 2 * c + a) * 100) + ((2 * a + 2 * c + b) * 10)));
   
10.                         if ((((2 * b + 2 * c + a) * 100) + ((2 * a + 2 * c + b) * 10)) == 2000)
    
11.                                 printf("a:%d, b:%d, c:%d\n", a, b, c);
    
12.                 }
    
13.                 b = 0;
    
14.         }
    
15. }

复制代码

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

66ccff

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

Ayala

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

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

Ayala

1. //
   
2. int tab_A[10]={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
   
3. int tab_B[10]={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
   
4. int tab_C[10]={0,221*1,221*2,221*3,221*4,221*5,221*6,221*7,221*8,221*9};
   
5. 
   
6. //
   
7. void foo(int tag)
   
8. {
   
9.         int c,b,a,t;
   
10.         for (c=0,t=(tag&1)?1:2;c<10;c+=t)// c与tag奇偶性相同 10/t次加法 10/t次比较(减法)
    
11.         {
    
12.                 for (b=0;b<10;b++)//10/t*10次加法 10/t*10次比较(减法)
    
13.                 {
    
14.                         for (a=0;a<10;a++)//10/t*10*10次加法 10/t*10*10次比较(减法)
    
15.                         {
    
16.                                 //10/t*10*10*3次加法 10/t*10*10*3次比较(减法) 10/t*10*10*3次查找数据
    
17.                                 if (tag == tab_A[a] + tab_B[b] + tab_C[c])
    
18.                                 {
    
19.                                         printf("a=%d\nb=%d\nc=%d\n",a,b,c);
    
20.                                         //goto done;
    
21.                                 }
    
22.                         }
    
23.                 }
    
24.         }
    
25. done:
    
26.         return;
    
27. }
    
28. //看起来循环次数很少 但是因为做了除法实际运行时间会比上一个更长
    
29. void foo2(tag)
    
30. {
    
31.         int c,b,a,t;
    
32.         for (c=0,t=(tag&1)?1:2;c<10;c+=t)// c与tag奇偶性相同 10/t次加法 10/t次比较(减法)
    
33.         {
    
34.                 for (b=0;b<10;b++)//10/t*10次加法 10/t*10次比较(减法)
    
35.                 {
    
36.                         //10/t*10次除法
    
37.                         if (0 == (tag - tab_B[b] - tab_C[c]) % 122)
    
38.                         {
    
39.                                 a = (tag - tab_B[b] - tab_C[c]) / 122;
    
40.                                 printf("a=%d\nb=%d\nc=%d\n",a,b,c);
    
41.                                 //goto done;
    
42.                         }
    
43. 
    
44.                 }
    
45.         }
    
46. done:
    
47.         return;
    
48. }
    
49. //没通用性的算法3 循环次数更少 但是更不可取 因为花了大量时间去做了不等式证明
    
50. void foo3()
    
51. /*
    
52.    122*a+212*b+221*c=2012
    
53.    0<=a<=9 ==> 0 <= 122*a <= 122*9=1098
    
54.    0<=b<=9 ==> 0 <= 212*b <= 212*9=1908
    
55.    0<=c<=9 ==> 0 <= 221*c <= 221*9=1989
    
56.    
    
57.    122*a=2012 - (212*b + 221*c)
    
58.    
    
59.    0<=2012 - (212*b + 221*c)<=1098
    
60.    212*b + 221*c >=2012 - 1098 = 914
    
61. 
    
62.    212*b + 212*c + 9*c >=914
    
63.    
    
64.    212*b + 212*c >=914-9*9=833
    
65.    
    
66.    b + c >= 833/212
    
67.    b + c >= 4
    
68.    
    
69.    a  = (2012-(212*b+221*c))/122 = 2012/122 - (212*b/122+221*c/122)
    
70.    16.4 < 2012/122 < 16.5
    
71.    
    
72.    16.5 > 212*b/122+221*c/122 >1.73*b + 1.81*c > 4*1.73=6.92
    
73.    
    
74.    16.5 / 1.73 < 9.54
    
75.    b+1.046*c <9.54
    
76.    
    
77.    0 <=0.046*c <=0.046*9=0.414
    
78.    b+c <=9
    
79. */
    
80. {
    
81.         int c,b,a;
    
82. 
    
83.         for (c=0;c<10;c+=2)
    
84.         {
    
85.                 for (b=(c<=4)?(4-c):0;b+c<=9;b++)
    
86.                 {
    
87.                         if (0 == (2012 - tab_B[b] - tab_C[c]) % 122)
    
88.                         {
    
89.                                 a = (2012 - tab_B[b] - tab_C[c]) / 122;
    
90.                                 printf("a=%d\nb=%d\nc=%d\n",a,b,c);
    
91.                                 //goto done;
    
92.                         }
    
93.                 }
    
94.         }
    
95. done:
    
96.         return;
    
97. }
    
98. int main()
    
99. {
    
100.         foo(2012);
     
101.         foo2(2012);
     
102.         foo3();
     
103.         system("pause");
     
104. }
     

复制代码

human_rights

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

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define max(a, b) ((a) > (b) ? (a) : (b)) // 返回较大的那个数
   
5. #define swap(a, b) ((b) = (a) + (b), (a) = (b) - (a), (b) -= (a)) // 交换两数
   
6. 
   
7. // 将三位整数的每一位按照从大到小的顺序排序
   
8. int max_seq(int h, int b, int t)
   
9. {
   
10.     if (max(h, b) == b)
    
11.         swap(h, b);
    
12.     if (max(h, t) == t)
    
13.         swap(h, t);
    
14.     if (max(b, t) == t)
    
15.         swap(b, t);
    
16.     return h * 100 + b * 10 + t;
    
17. }
    
18. 
    
19. // 将三位整数的每一位按照逆序重排
    
20. int rev_max_seq(int n)
    
21. {
    
22.     int h, b, t;
    
23.     h = n / 100;
    
24.     t = n / 10 - h * 10;
    
25.     b = n % 10;
    
26.     return b * 100 + t * 10 + h;
    
27. }
    
28. 
    
29. // 迭代器
    
30. int num_iterator(int n)
    
31. {
    
32.     int x, y;
    
33.     int h, b, t;
    
34.     h = n / 100;
    
35.     t = n / 10 - h * 10;
    
36.     b = n % 10;
    
37.     x = max_seq(h, b, t);
    
38.     y = rev_max_seq(x);   // 把每一位从大到小排序过的整数减去它的逆序
    
39.     printf("%d ", x -= y);
    
40.     return x;
    
41. }
    
42. 
    
43. int main(void)
    
44. {
    
45.     int i, j, n;
    
46.    
    
47.     for (j = 100; j < 1000; ++j)
    
48.     {
    
49.         printf("%d\n", j);
    
50.         for (n = j, i = 0; i < 30; ++i)
    
51.         {
    
52.             n = num_iterator(n);
    
53.         }
    
54.         putc(10, stdout);
    
55.     }
    
56.    
    
57.     return 0;
    
58. }
    

复制代码

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

ljxin

acb、bac、bca、cab、cba的和是2012。
個位數 = 2a + 2b + c = 10d + 2
十位數 = 2a + b + 2c + d = 10e + 1
百位數 = a + 2b + 2c + e = 20
將e = 20 - (a + 2b + 2c) 帶回，最後得到 122a + 212b + 221c = 2012

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5. )
   
6. 
   
7. func main() {
   
8.         // 由個位數和可知 c 為偶數， 以2步進
   
9.         for c:= 0; c < 10; c+=2 {
   
10.                 for a:= 0; a < 10; a++ {
    
11.                         for b:= 0; b < 10; b++ {
    
12.                                 if 122 * a + 212 * b + 221 * c > 2012 {
    
13.                                         break
    
14.                                 }else if 122 * a + 212 * b + 221 * c == 2012{
    
15.                                         fmt.Printf("%v%v%v\n",a ,b ,c)
    
16.                                 }
    
17.                                 // 小於就繼續for迴圈
    
18.                         }
    
19.                 }
    
20.         }
    
21. }
    

复制代码

追加: 第二層的for忘了添加break條件

smitest

222(a+b+c)-abc=2012  即 222(a+b+c)=2012+abc  等式右边为222的倍数
所以abc直接从222-MOD(2012,222)=208开始排查，每次增量222,而对应的a+b+c只需要从10（=2220/222）开始,依次加1去验证。
VB 代码

1. Sub main()
   
2. 'n= 222 - 2012 Mod 222 = 208
   
3. a = 2
   
4. b = 0
   
5. c = 8
   
6. ss = 10
   
7. Do
   
8. If ss = a + b + c Then Debug.Print a; b; c
   
9. c = c + 2: If c > 9 Then c = c - 10: b = b + 1
   
10. b = b + 2: If b > 9 Then b = b - 10: a = a + 1
    
11. a = a + 2
    
12. ss = ss + 1
    
13. Loop Until a > 9
    
14. End Sub

复制代码