【C】有趣的数字游戏

13*0217 发表于 2017-7-4 15:26:45

先看问题：

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

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

/*
根据公式 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 发表于 2017-7-4 17:50:48

这是一个很有意思的题！我的解法如下：
三位数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次。
由以上结论写出程序如下：

#include <stdio.h>

int main()
{
int C = { 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 发表于 2017-7-4 17:56:23

(acb+bca)+(cab+cba)的和是偶数，进一步得a是偶数且b是偶数。这结论不对!

Ayala 发表于 2017-7-4 18:11:50

本帖最后由 Ayala 于 2017-7-4 18:40 编辑

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 发表于 2017-7-4 18:55:54

4

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

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

13*0217 发表于 2017-7-4 19:56:21

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

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

Ayala 发表于 2017-7-4 21:14:25

本帖最后由 Ayala 于 2017-7-5 05:34 编辑

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

/*
根据公式 acb + bac + bca + cab + cba =2012,寻找这个三位数abc。
*/
//利用hash表降低降低乘法次数10*10*5*3 降低到10+10+5次乘法 (9+9+4)次
int tab_A={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
int tab_B={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
int tab_C ={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 + tab_B + tab_C)
{
printf("a=%d\nb=%d\nc=%d\n",a,b,c);
//goto done;
}
}
}
}
done:
return;
}

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

66ccff 发表于 2017-7-5 02:16:46

本帖最后由 66ccff 于 2017-7-5 02:24 编辑

分析：

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）

0212223242（五个数个位和）
1110908070（五个数的十位和）
2120908070（五个数的十位和）
3130908070（五个数的十位和）
4140908070（五个数的十位和）

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

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 发表于 2017-7-5 02:31:29

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

Ayala 发表于 2017-7-5 04:52:51

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

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

Ayala 发表于 2017-7-5 05:52:40

本帖最后由 Ayala 于 2017-7-5 08:14 编辑

//
int tab_A={0,122*1,122*2,122*3,122*4,122*5,122*6,122*7,122*8,122*9};
int tab_B={0,212*1,212*2,212*3,212*4,212*5,212*6,212*7,212*8,212*9};
int tab_C={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 + tab_B + tab_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 - tab_C) % 122)
{
a = (tag - tab_B - tab_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 - tab_C) % 122)
{
a = (2012 - tab_B - tab_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 发表于 2018-1-19 23:13:56

本帖最后由 ring_chen 于 2018-1-19 23:28 编辑

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

#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;
}

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

ljxin 发表于 2018-6-18 20:32:27

本帖最后由 ljxin 于 2018-6-18 20:37 编辑

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
package main

import (
"fmt"
)

func main() {
// 由個位數和可知 c 為偶數，以2步進
for c:= 0; c < 10; c+=2 {
for a:= 0; a < 10; a++ {
for b:= 0; b < 10; b++ {
if 122 * a + 212 * b + 221 * c > 2012 {
break
}else if 122 * a + 212 * b + 221 * c == 2012{
fmt.Printf("%v%v%v\n",a ,b ,c)
}
// 小於就繼續for迴圈
}
}
}
}

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

smitest 发表于 2020-2-24 16:16:26

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 代码
Sub main()
'n= 222 - 2012 Mod 222 = 208
a = 2
b = 0
c = 8
ss = 10
Do
If ss = a + b + c Then Debug.Print a; b; c
c = c + 2: If c > 9 Then c = c - 10: b = b + 1
b = b + 2: If b > 9 Then b = b - 10: a = a + 1
a = a + 2
ss = ss + 1
Loop Until a > 9
End Sub

页: [1]

技术宅的结界's Archiver

【C】有趣的数字游戏

4