技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 406|回复: 11
收起左侧

【C】有趣的数字游戏

[复制链接]

31

主题

167

帖子

1555

积分

用户组: 管理员

UID
8
精华
1
威望
14 点
宅币
1340 个
贡献
15 次
宅之契约
0 份
在线时间
216 小时
注册时间
2014-1-27
发表于 2017-7-4 15:26:45 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

x
先看问题:

    我们来玩一个数字游戏,我已经想好了一个三位数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;
}

85

主题

263

帖子

3428

积分

用户组: 管理员

No. 418

UID
418
精华
13
威望
52 点
宅币
1969 个
贡献
1027 次
宅之契约
0 份
在线时间
252 小时
注册时间
2014-8-9
发表于 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次。
由以上结论写出程序如下:

[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);
            }
        }
    }
}


执行结果与楼主代码的执行结果相同。
In the beginning I was not the best.
And the world was also not the best.
But I still know that I am who I am.
Because I think that it is good.
I have been working hard.
I have been keeping growth with the world.
And it was so.

25

主题

75

帖子

1009

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
759 个
贡献
31 次
宅之契约
0 份
在线时间
186 小时
注册时间
2016-7-12
发表于 2017-7-4 17:56:23 | 显示全部楼层
(acb+bca)+(cab+cba)的和是偶数,进一步得a是偶数且b是偶数。
这结论不对!

25

主题

75

帖子

1009

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
759 个
贡献
31 次
宅之契约
0 份
在线时间
186 小时
注册时间
2016-7-12
发表于 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)

85

主题

263

帖子

3428

积分

用户组: 管理员

No. 418

UID
418
精华
13
威望
52 点
宅币
1969 个
贡献
1027 次
宅之契约
0 份
在线时间
252 小时
注册时间
2014-8-9
发表于 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不能同时为偶数,我的失误。那么接下来由你来进一步减少枚举次数。。。
这个问题交给你了。
In the beginning I was not the best.
And the world was also not the best.
But I still know that I am who I am.
Because I think that it is good.
I have been working hard.
I have been keeping growth with the world.
And it was so.

31

主题

167

帖子

1555

积分

用户组: 管理员

UID
8
精华
1
威望
14 点
宅币
1340 个
贡献
15 次
宅之契约
0 份
在线时间
216 小时
注册时间
2014-1-27
 楼主| 发表于 2017-7-4 19:56:21 | 显示全部楼层
cyycoish 发表于 2017-7-4 17:50
这是一个很有意思的题!我的解法如下:
三位数abc,a是百位,b是十位,c是个位。且acb+bac+bca+cab+cba=201 ...

这个程序更厉害,速度快了11倍!!!

25

主题

75

帖子

1009

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
759 个
贡献
31 次
宅之契约
0 份
在线时间
186 小时
注册时间
2016-7-12
发表于 2017-7-4 21:14:25 | 显示全部楼层
本帖最后由 Ayala 于 2017-7-5 05:34 编辑

[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");
}

0

主题

2

帖子

10

积分

用户组: 初·技术宅

UID
2651
精华
0
威望
1 点
宅币
6 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2017-7-5
发表于 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

[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次即可)

0

主题

2

帖子

10

积分

用户组: 初·技术宅

UID
2651
精华
0
威望
1 点
宅币
6 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2017-7-5
发表于 2017-7-5 02:31:29 | 显示全部楼层
把数字倒着来枚举只需9次就可以得到结果    可以说是极限了吧!!!

25

主题

75

帖子

1009

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
759 个
贡献
31 次
宅之契约
0 份
在线时间
186 小时
注册时间
2016-7-12
发表于 2017-7-5 04:52:51 | 显示全部楼层
66ccff 发表于 2017-7-5 02:31
把数字倒着来枚举只需9次就可以得到结果    可以说是极限了吧!!!

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

25

主题

75

帖子

1009

积分

用户组: 版主

UID
1821
精华
6
威望
57 点
宅币
759 个
贡献
31 次
宅之契约
0 份
在线时间
186 小时
注册时间
2016-7-12
发表于 2017-7-5 05:52:40 | 显示全部楼层
本帖最后由 Ayala 于 2017-7-5 08:14 编辑

[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");
}

1

主题

6

帖子

93

积分

用户组: 小·技术宅

UID
3349
精华
1
威望
4 点
宅币
74 个
贡献
0 次
宅之契约
0 份
在线时间
7 小时
注册时间
2018-1-14
发表于 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层吧,再来一次迭代也行 )
[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;
}

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

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2018-5-25 18:36 , Processed in 0.089468 second(s), 27 queries , Gzip On, Memcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表