编程算法基础_常用思路_1_枚举与剪枝

 

剪枝的由来：

 

暴力破解中，依靠计算机的强大计算能力时，必须考虑计算性能和计算限度

eg: 100W的双层for循环，计算机就会比较吃力，耗时较长.

 

如果某个问题考虑情况较多，我们可以尝试在逻辑中排除不可能的情况，或者从循环中找出一些规律来排除循环次数(eg 案例2)，减少计算次数，这就是剪枝的由来。

 

 案例如下:

 

public class pruning {

	
	public static void main(String[] args) {
		
		example2();
	}
	
	
	/**
	 * 剪枝-找钱问题---使用暴力破解(未含有枝剪)
	 * 1 找8元钱
	 * 2有零钞: 5元，2元，1元，5角
	 * 问： 所有找钱方案
	 * 
	 * 将角换算成元，避免浮点数运算造成的误差
	 * 结果: 多个结果 ，此处没有列举
	 */
	public static void example1(){
		// x表示5元个数  y表示2元个数 z表示1元个数 m表示0.5元个数
		int count = 0;
		for(int x=0; x<=80/50; x++){
			for(int y=0; y<=80/20; y++){
				for(int z=0; z<=80/10; z++){
					for(int m=0; m<=80/5; m++){
						++count;
						if(x*50 + y*20 + z*10 + m*5 == 80){
							System.out.println("第" +count + "次结果---> 5元为: " + x + "次" + " 2元为: " + y  + "次" + " 1元为: " + z  + "次"
						+ " 5角为: " + m  + "次");
						}
					}
				}
			}
			
		}
	}
	
	
	/**
	 * 剪枝: 尽早排除不合逻辑的情况， 在暴力破解情况下优化查询次数
	 * 
	 * 以上计算次数过多，增加过多无意义的计算 eg: 如果有一次5元，那么第二次2元循环中，只能最多出现1次，而没优化情况下，是从1次到4次都执行
	 */
	public static void example2(){
		// x表示5元个数  y表示2元个数 z表示1元个数 m表示0.5元个数
		int count = 0;
		for(int x=0; x<=80/50; x++){
			for(int y=0; y<=80/20; y++){
				if((80 - 50*x - 20*y) < 0 ){break;} // 尽早排除不合逻辑的情况
				for(int z=0; z<=80/10; z++){
					if((80 - 50*x - 20*y - 10*z) < 0 ){break;} // 尽早排除不合逻辑的情况
					++count;
					int m = (80 - (x*50 + y*20 + z*10))/5;
						if(x*50 + y*20 + z*10 + m*5 == 80){
							System.out.println("第" +count + "次结果---> 5元为: " + x + "次" + " 2元为: " + y  + "次" + " 1元为: " + z  + "次"
						+ " 5角为: " + m  + "次");
					}
				}
			}
			
		}
	}

}

 

案例2:

 

/**
 * 求n的平方尾数仍为n数本身的数字
 */
public class square {

	public static void main(String[] args) {
		
		/*for(int i=0; i<10; i++){
			int n = i*i;
			if(n%10 == i){
				System.out.println("平方为: " + n + " 数字为: " + i);
			}
		}*/
		
		for(int i=10; i<100; i++){
			int n = i*i;
			int m = i%10;
			if(m != 0 && m!= 1 && m!= 5 && m!= 6){ // 如果个位数不是左侧这几种的话，那么平方后的结果个位数肯定和原数各位不一致，这情况下直接剪枝
				continue;
			};
			if(n%100 == i){
				System.out.println("平方为: " + n + " 数字为: " + i);
			}
		}
	}
}