第一题,求仅由2,3,5组成的数从小到大的第
个数是啥(
)。
为了简化,我们称呼这种数为“漂亮数”。
即是在2、3、5、22、23、25、32、33、35、222、……里面找第
个“漂亮数”。
一句话:转成3进制计算!
思路:
-
先得到第
个数是几位数的。我们可以很容易想到,位数为
的“漂亮数”个数为
,那么我们就构建一个数组:
,分别表示位数为1、2、3……的“漂亮数”个数。我们对
求累加和,得到
,表示到某一位数位置前面共有多少个“漂亮数”。因为
,所以
长度为6就足够了。然后为了得到位数
,我们从头开始一次判断
,如果大于,则表示1位数的“漂亮数”个数凑不到
,说明
。之后继续比较
,
……,直到某个位置有
,此时我们就得到了
。
-
再在
位数里面找我们要找的数是第几个。就先简短省略了。。。
上代码:
public class Main { public static final int N = 7; public static final int[] cusums = new int[N]; public static final int[] mapping = new int[10]; static { int pow = 3; cusums[0] = 0; cusums[1] = 3; for (int i = 2; i < N; i++) { pow *= 3; cusums[i] = cusums[i - 1] + pow; } mapping[0] = 2; mapping[1] = 3; mapping[2] = 5; } public static int numberN(int n) { int k = 0; // 求第n个数的位数,记为k,并得到在k位数里面它排在第几个,最多循环7次 while (n >= cusums[k]) { k++; } n -= cusums[k - 1]; // 建立k位数的三进制数组 int[] nums = new int[k]; // 求在k位里面的第n个排列(表示为三进制数),最多循环7次 int p = 0; while (n > 0) { nums[p] = n % 3; n = n / 3; p++; } // 将三进制表示的数组转为2,3,5组成的数 int res = 0; for (int i = k - 1; i >= 0; i--) { res = res * 10 + mapping[nums[i]]; } return res; } public static void main(String[] args) { for (int i = 0; i < 1000; i++) { System.out.println(numberN(i)); } } }
全部评论
(1) 回帖