有趣的问题
2018-10-20 本文已影响0人
ccpjsg
今天碰到了一个问题。0-9十个数字,分成3个三位数,其中第一个三位数是第二个的一半,是第三个的1/3。求出这三个三位数。
我是在技术有限。想了好久。其实我用python的话,就很方便了搞出来。但是要用C语言。很多东西要自己去搭建。我先是想的把三位数里面百位数,十位数,个位数不重复的先筛选出来。然后用一个三重循环加判断。但是这样做的复杂度有点高。是n的3次方。首先粗略计算,满足条件的三位数有630个,意思是我最多要计算630×630×630=250,047,000次,即2亿5千零4万7千次。我的电脑当然可以计算出来,这个计算量虽然有点分量,但是现在的一般笔记本电脑是没什么压力的。但是,时间复杂度太高了,而且远远超过提交系统的规定的内存与时间限制。
我又想了第二个方法。把这三个三位数的三个数位上的数字进行了限制。效果还不错,起码第一个最小的三位数百位就不能超过3,只能是1,2,3这三个中的一个。因为第三个数是它的3倍,如果第一个数百位是4,那底第三个数至少1200,已经不是三位数了。数位的筛选还行。但是,我写循环的时候,似乎要9层,每三层选出一个三位数。也太复杂了。78968531010=36,288,000。不行,比刚才还多。
第三种,这里就要写上正确的解法。但是还没想出来。想出来了再补上。