第一题,求仅由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) 回帖