猪的安家问题解法

import java.io.*;

public class PigHome {
	public static void calcute_pig(){
		int num;
		//读取数据，将数据读取到数组pig[][]中，文件放在D：\arithmetic\src\pighome.txt中
		File file = new File("D:\\arithmetic\\src\\pighome.txt");
		if(!file.exists()){
			System.out.println("file is not exist!");
			return;
		}
	    FileReader fileReader = null;
		BufferedReader reader = null;
		try {
			fileReader = new FileReader(file);
		    reader = new BufferedReader(fileReader);
		    String line = "";
		    line = reader.readLine();
		    num = Integer.valueOf(line);
		    System.out.println(num);
		    int pig[][] = new int[num][2];
		    for(int i=0;i<num;i++){
		    	line = reader.readLine();
		    	String[] temp = line.split(" ");
		    	pig[i][0] = Integer.valueOf(temp[0].trim());
		    	pig[i][1] = Integer.valueOf(temp[1].trim());
		    	System.out.println(pig[i][0]+" "+pig[i][1]);
		    }
		    
		    //pighome保存猪的数量
		    int pighome = pig[0][0]+pig[0][1];
		    
		    //保存已经计算过的猪圈数的最小公倍数
	    	int multi = pig[0][0];
		    for(int i=0;i<num-1;i++){
		    	//System.out.println("multi="+multi);
		    	while(pighome % pig[i+1][0] != pig[i+1][1]){
		    		pighome += multi;
		    	}
		    	if(i == num-2){
		    		System.out.println("Andy家至少有"+pighome+"只猪!");
		    	}
		    	multi = least_common_multiple(multi,pig[i+1][0]);
		    }
		} catch (Exception e) {
			e.printStackTrace();
		}	    
	}
	
	//最小公倍数
	public static int least_common_multiple(int num1,int num2){
		return num1*num2/greatest_common_divisor(num1,num2);
	}
	
	//最大公约数
	public static int greatest_common_divisor(int num1,int num2){
		if(num1 > num2){
			int temp = num1;
			num1 = num2;
			num2 = temp;
		}
		if(num1 == num2 || num2 % num1 == 0)
			return num1;
		int temp = num2 % num1;
		while(num2 % temp != 0 && temp > 1){
			num2  =num1;
                        num1 = temp;
                        temp = num2 % num1;
		}
		return temp;
	}
	
	public static void main(String[] args){
		calcute_pig();
	}
}

 好久没有写些算法的内容了，题目不是很难，自己随手写了一个算法。

思路分析：

      首先，这是一个和余数有关的问题，按照题目的叙述，不难想到和最小公倍数有关系。但是对于求最小公倍数最好的解法就是先求出最大公约数，然后将该2个数相乘再除以他们的最大公约数即可得到最小公倍数。而求最大公约数的方法我所知道的最好的方法就是辗转相除法。

      辗转相除法还是我在小学上奥赛班的时候学到的，可能好多地方已经不叫这个名字了。其思路就是对于要计算的2个数字，先看大数能否被小数整除，如果不能就取其余数，然后在去较小数和余数，继续求他们的最小公倍数。

 

解法分析：

      先求出满足第一行，也就是文件第二行的一个猪圈数，即第二行的2个数相加之和，如例子中的4（=3+1），然后判断其是否满足下一行的数据，即是否满足除5余1.显然题目不满足，那么就将所得的数字4不停的加3（这样得到的结果对3的余数不变），知道满足第二行，可以得到16.然后处理下一行的思路一样，不过所加的数变成了15（即3和5的最小公倍数），只有这样才能是得到的结果对3和5除所得的余数不变。

 

      现在回头看看这个题目，根本就没有什么难度，只有一个简单的求2个数的最小公倍数可能稍微有点麻烦。其他的思路都非常容易想到。