枚举算法

枚举(穷举)法

 

枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:

(1):可预先确定候选答案的数量;

(2):候选答案的范围在求解之前必须有一个确定的集合.

 

实例1:填数游戏.

 

 Java代码描述:

public static void main(String[] args) {

		int multi = 1;
		int result = 0;
		int i1, i2, i3, i4, i5;
		for (i1 = 1; i1 <= 9; i1++) { 
			for (i2 = 0; i2 <= 9; i2++) {
				for (i3 = 0; i3 <= 9; i3++) {
					for (i4 = 0; i4 <= 9; i4++) {
						for (i5 = 0; i5 <= 9; i5++) {
							multi = i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5;
							result = i5 * 100000 + i5 * 10000 + i5 * 1000 + i5 * 100 + i5 * 10 + i5;
							if (multi * i1 == result) {
								System.out.println(i1 + " " + i2 + " " + i3 + " " + i4 + " " + i5);
								System.out.println("        " + i1);
								System.out.println("-----------------");
								System.out.println(i5 + " " + i5 + " " + i5 + " " + i5 + " " + i5);
								break;
							}
						}
					}
				}
			}
		}

	}

 

 运行结果:


 

实例2:填运算符:

 

Java代码描述:

	private static void tysf() {
		int[] i = new int[5];// 数组i用来表示4个运算符
		int j; // 循环变量
		int sign; // 累加运算时的符号
		int result = 0; // 保存运算式的结果值
		int count = 0; // 计数器,统计符合条件的方案
		int[] num = new int[6]; // 保存操作数
		float left, right; // 保存中间结果
		char[] oper = { ' ', '+', '-', '*', '/' }; // 运算符
		System.out.println("请输入五个数");
		Scanner sc = new Scanner(System.in);
		for (int ii = 1; ii < num.length; ii++) {
			num[ii] = sc.nextInt();
		}
		System.out.println("请输入结果");
		result = sc.nextInt();
		// for (i[0] = 1; i[0] < 4; i[0]++) { //循环4中填运算符,1表示+,2表示-,3表示*,4表示/
		// if ((i[0] < 4) || (num[1] != 0)) { //运算符如果是/,则第二个运算数不能为0
		for (i[1] = 1; i[1] <= 4; i[1]++) {
			if ((i[1] < 4) || (num[2] != 0)) {
				for (i[2] = 1; i[2] <= 4; i[2]++) {
					if ((i[2] < 4) || (num[3] != 0)) {
						for (i[3] = 1; i[3] <= 4; i[3]++) {
							if ((i[3] < 4) || (num[4] != 0)) {
								for (i[4] = 1; i[4] <= 4; i[4]++) {
									if ((i[4] < 4) || (num[5] != 0)) {
										left = 0;
										right = num[1];
										sign = 1;
										for (j = 1; j <= 4; j++) {
											switch (oper[i[j]]) {
											case '+':
												left = left + sign * right;
												sign = 1;
												right = num[j + 1];
												break;
											case '-':
												left = left + sign * right;
												sign = -1; // 通过sign=-1实现减法
												right = num[j + 1];
												break;
											case '*':
												right = right * num[j + 1]; // 实现乘法
												break;
											case '/':
												right = right / num[j + 1]; // 实现除法
												break;
											}
										}
										if (left + sign * right == result) {
											count++;
											System.out.print(count + "  ");
											for (j = 1; j <= 4; j++) {
												System.out.print(num[j] + "" + oper[i[j]]);
											}
											System.out.println("=" + result);
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if (count == 0) {
			System.out.println("没有符合条件的 ");
		}
	}

 运行结果: