一道NEC的面试题，2005-10

出自求职百科

　　前些天听我同学说了一道NEC的面试题，大体内容如下：

　　找出111111111~999999999中符合以下条件的9位数：9位数的前三位数是中间三位数的2倍，是最后三位数的3倍，并且这个9位数的每位数字只能是1~9,不能有重复的数字。

　　我看到这个题目首先想到的是穷举，当然这是非常低效的算法。于是我开始想办法优化，想到了以下办法：设这个9位数的第一个三位数是i,第二个三位数是j,第三个三位数是k,那么，i=2j=3k ,i和k是偶数,并且i/3是整数。i > 300, 设i初始值是312,那么i的步长值应该是6。j和k之间的数字差别不大，不再继续优化了。

　　于时我可以用一个大体如下的三层循环来计算。

　　for (i = 312; i < 999; i+=6)

　　for ( j = 111; 2j < =i; j++)

　　for (k = 111; 3k <= i; k +=2)

　　当然以上内容还可以再优化一些，但我想总会是n^3的问题。

　　但是过了一些天，有一个新的想法使我改变了原有的肯定，可以只用一层循环来解决这个问题：

　　for ( i = 312; i < 999 ; i +=6)

　　{j =i/2;

　　k=i/3;

　　if ( i j k 没有重复数字 ) 输出正确结果（我计算的好像没有符合条件的数字）；}

参考：http://blog.csdn.net/CrazyFormat/archive/2005/10/18/508736.aspx