递推算法二

递推算法二（幂积数列）

幂积数列：M={2^x * 3^y|x>=0,y>=0},输入整数n,m求小于n的按从小到大的第m个元素
分析：

• 穷尽法：从2开始到n,如果n%2==0，n=n/2一直循环的直到不能除尽、n%3（同理），最后的商等于1则说明这个数在数列中。
• 算法分析：可以很清楚的得出时间复杂度 = O(n)

private static void power(int n, int m) {
		int f[] = new int[1000], index = 2;
		f[1] = 1;
		f[2] = 2;
		for (int i = 3; i <= n; i++) {
			int j = i;
			while (j % 2 == 0) {
				j = j / 2;
			}
			while (j % 3 == 0) {
				j = j / 3;
			}
			if (j == 1) {
				index++;
				f[index] = i;
			}
		}
		System.out.println("数列中小于" + n + "的共有" + index + "项");
		System.out.println("数列中的第" + m + "项为：" + f[m]);
	}

• 递推法：
• 寻求递推关系:寻求x+y =i;和x+y = i-1之间的关系，不难看出第i行有i+1个元素，第行的前i个元素等于第i-1行对应列的2倍，而第i+1个元素等于3倍前一行的最后一个元素。
      x+y=0;1
     x+y=1;2*1=2,3*1=3
     x+y=2;2*2=4,3*2=6,3*3=9
     x+y=3;4*2=8,6*2=12,9*2=18,9*3=27
• 排序后输出第m项。
• 算法分析：党n从分大时项数index<n^(1/4)的，冒泡排序的时间复杂度=O(n^2) = O(index^2)——>排序的时间复杂度=O(n^1/2),总的来说时间复杂度是<<O(n)的。

private static void power1(int n, int m) {
		int i = 1, flag = 0, k = 1, rowMax = 1, j = 0, temp = 0;
		int f[] = new int[1000];
		int row[] = new int[100];
		f[1] = 1;
		row[0] = 1;
		while (true) {
			//当元素不满足递推的条件时，结束递推，初始时falg=0
			flag = 0;
			for (j = 0; j <= i - 1; j++) {
				int h = row[i - 1] + j;
				//递归的条件：当前的数>0&&<=n
				if (2 * f[h] <= n && f[h] > 0) {
					k++;
					f[k] = 2 * f[h];
					//这一行有满足条件的递推关系成立
					flag = 1;
					if (j == 0) {
						//记录每行第一个元素的位置
						row[i] = k;
					}
				} else {
					break;
				}
			}
			rowMax = rowMax * 3;
			if (rowMax <= n && rowMax > 0) {
				k++;
				f[k] = rowMax;
			}
			//递推结束推出while循环
			if (flag == 0)
				break;
			i++;
		}
		//冒泡排序
		for (i = 1; i < k; i++) {
			for (j = i + 1; j <= k; j++) {
				if (f[i] > f[j]) {
					temp = f[i];
					f[i] = f[j];
					f[j] = temp;
				}
			}
		}
		System.out.println("数列中小于" + n + "的共有:" + k + "项");
		System.out.println("数列中的第" + m + "项为：" + f[m]);
	}