笔试算法题（20）：寻找丑数 & 打印1到N位的所有的数

出题：将只包含2,3,5的因子的数称为丑数（Ugly Number），要求找到前面1500个丑数；

分析：

解法1：依次判断从1开始的每一个整数，2,3,5是因子则整数必须可以被他们其中的一个整除，如果不包含任何其他因子则最终的结果为1；
解法2：小丑数必然是某个大丑数的因子，也就是乘以2,3，或者5之后的值，所以可以利用已经找到的丑数来寻找下一个丑数，使用数组有序保存已经找到的丑数，并且当前最大丑数值为M；用大于M/2的丑数乘以2得到M1，用大于M/3的丑数乘以3得到M2，用大于M/5的丑数乘以5得到M3，最后M1，M2 和M3中最小的数就是下一个丑数；
此题让人联想到素数的求解，素数解法中是从小到大将等于小数倍数的数去除，最后剩下的就是素数；而本题是需要找到这些从小到大等于小数倍数的数，因为仅需2,3,5作为因子才能满足要求；

解题：

 bool IsUglyNumber(int n) {

         while(n% == )

                 n/=;

         while(n% == )

                 n/=;

         while(n% == )

                 n/=;

         if(n == )

                 return true;

         else

                 return false;

 }

 void BetterVersion(int limit) {

         /**

          * 创建数组array有序存储找到丑数

          * */

         int array[limit]; int length=;

         array[]=;array[]=;array[]=;

         int M1, M2, M3,M;

         for(int j=;j<limit-;j++) {

                 /**

                  * 寻找大于已找到最大丑数，并且以小丑数和2，3或5

                  * 为因子的丑数

                  * */

                 for(int i=;i<length;i++) {

                         if(array[i]*>array[length]) {

                                 M1=array[i]*;break;

                         }

                 }

                 for(int i=;i<length;i++) {

                         if(array[i]*>array[length]) {

                                 M2=array[i]*;break;

                         }

                 }

                 for(int i=;i<length;i++) {

                         if(array[i]*>array[length]) {

                                 M3=array[i]*;break;

                         }

                 }

                 /**

                  * 使用最小值作为下一个丑数

                  * */

                 M=M1;

                 if(M>M2) M=M2;

                 if(M>M3) M=M3;

                 array[++length]=M;

                 printf("\n%d",M);

         }

 }

出题：输入数字N，N表示十进制数的位数，要求按序从1开始输出最大到N位的十进制数；

分析：

解法1：N位数可能超出任何机器的最大数字范围；所以需要使用string，array或者创建一个大数类型来表示数字，然后模拟每次加1的运算，注意最后数字溢出N位数字的判断；
解法2：同样使用string或者array表示数字，不同的是使用递归全排列N位数字，每位数字可能的取值是0-9，但是当N较大时系统栈也可能溢出；

解题：

 void printBigInt(int *array, int length, int index) {

         if(index == length) {

                 printf("\n");

                 for(int i=;i<length;i++) {

                         if(array[i] !=) {

                                 for(int j=i;j<length;j++)

                                         printf("%d",array[j]);

                                 break;

                         }

                 }

                 return;

         }

         for(int i=;i<=;i++) {

                 array[index]=i;

                 printBigInt(array,length,index+);

         }

 }

 void printBigInt(int length) {

         int array[length];

         for(int i=;i<length;i++)

                 array[i]=;

         printBigInt(array, length, );

 }

巴特西

笔试算法题（20）：寻找丑数 & 打印1到N位的所有的数

最新文章

热门文章