编程经典问题及其Java求解（一）

这几天由于参加一个编程赛，做了些编程的练习，程序题就来自于javaeye中的朋友分享的一些经典程序题，现在我将自己用Java写出的部分题代码分享出来。

package com.sailor.game;

/**
 * 题目：猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个 第二天早上又将剩
 * 下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。
 * 程序分析：采取逆向思维的方法，从后往前推断。
 * 
 * @author Sailor
 * 
 */
public class Monkey_Peach {

	public static void main(String[] args) {
		int[] peach = new int[10];
		peach[9] = 1;
		// 下面利用的是数组和循环将每天的桃子数量都求出来了
		for (int i = peach.length - 1; i > 0; i--) {
			peach[i - 1] = 2 * (peach[i] + 1);
		}
		for (int i = 0; i < peach.length; i++) {
			System.out.println(peach[i]);
		}
		System.out.println("第一天的桃子数："+getPeach_Num(10, 1));
	}

	// 利用递归的方法来求第一天的桃子数,输入参数为天数和当天的桃子数，输出为第一天桃子数
	public static int getPeach_Num(int day, int peach_num) {
		if (day == 1)
			return peach_num;
		else if (day < 1 || peach_num < 0)
			return 0;
		else
			return getPeach_Num(day - 1, (peach_num + 1) * 2);
	}

}

package com.sailor.game;

/**
 * 输出9*9口诀
 * 
 * @author Sailor
 * 
 */
public class Times_Table {

	public static void main(String[] args) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= i; j++) {
				System.out.print(j + " * " + i + " = " + (i * j));
				System.out.print("\t");
			}
			System.out.println();
		}
	}

}

package com.sailor.game;

/**
 * 题目：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。
 * 例如：153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。
 * 
 * @author Sailor
 * 
 */
public class Armstrong_number {

	public static void main(String[] args) {
		for (int i = 100; i < 1000; i++) {
			int n1, n2, n3;
			int k = i;
			n1 = k / 100;
			k %= 100;
			n2 = k / 10;
			k %= 10;
			n3 = k;
			if (i == (getCube(n1) + getCube(n2) + getCube(n3))) {
				System.out.println(i);
			}
		}
	}

	public static int getCube(int n) {
		return n * n * n;
	}

}

package com.sailor.game;

import java.util.Scanner;

/**
 * 题目：输入两个正整数m和n，求其最大公约数和最小公倍数。 程序分析：利用辗除法。
 * 
 * 用辗转相除法求两个数的最大公约数的步骤如下： 先用小的一个数除大的一个数，得第一个余数； 再用第一个余数除小的一个数，得第二个余数；
 * 又用第二个余数除第一个余数，得第三个余数；
 * 这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
 * 最小公倍数为两个数相乘然后除以最大公约数
 * 
 * @author sailor
 * 
 */
public class Common_Divisor {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
        System.out.println("请输入第一个数");
	    int a=in.nextInt();
	    System.out.println("请输入第二个数");
	    int b=in.nextInt();
	    System.out.println(a+"和"+b+"的最大公约数是"+getMaxCommon_Divisor(a, b));
	    System.out.println(a+"和"+b+"的最小公倍数是"+getMincommon_multiple(a, b));
	}

	// 求最大公约数
	public static int getMaxCommon_Divisor(int a, int b) {
		int max = Math.max(a, b);
		int min = Math.min(a, b);
		int mod = max % min;
		if (mod == 0) {
			return min;
		} else {
			return getMaxCommon_Divisor(mod, min);
		}
	}

	// 求最大公约数
	public static int getMincommon_multiple(int a, int b) {
		return (a * b) / getMaxCommon_Divisor(a, b);
	}

}

package com.sailor.game;

import java.util.Scanner;

/**
 * 题目：输入某年某月某日，判断这一天是这一年的第几天？
 * 程序分析：以3月5日为例，应该先把前两个月的加起来，然后再加上5天即本年的第几天，
 * 特殊情况，闰年且输入月份大于3时需考虑多加一天。
 * 
 * @author Sailor
 * 
 */
public class Compute_Day {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		System.out.println("请依次输入年、月、日：");
		int year = in.nextInt();
		int month = in.nextInt();
		int day = in.nextInt();
		int days = 0;
		boolean isLeap = isLeap(year);
		for (int i = 1; i < month; i++) {
			days += getDays(i, isLeap);
		}
		System.out.println("这是今年的第 " + (days + day) + " 天 ");
	}

	public static int getDays(int month, boolean isLeap) {
		int days = 0;
		switch (month) {
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
			days = 31;
			break;
		case 4:
		case 6:
		case 9:
		case 11:
			days = 30;
			break;
		case 2:
			if (isLeap)
				days = 29;
			else
				days = 28;
			break;
		}

		return days;
	}

	/**
	 * 判断闰年的条件： 如果年份值能被4整除且不能被100整除，或者能被400整除，就是闰年，否则不是
	 * 
	 * @param year
	 * @return
	 */
	public static boolean isLeap(int year) {
		if (year % 4 == 0 && year % 100 != 0) {
			return true;
		}
		if (year % 400 == 0) {
			return true;
		}
		return false;
	}

}

package com.sailor.game;

/**
 * 题目：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。
 * 已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。
 * 
 * @author Sailor
 * 
 */
public class GameList {

	public static void main(String[] args) {
		int a, b, c;
		int x = 1,z = 3;// y = 2,  此处y不用，只是为了方便读懂。
		String[] temp = { "x", "y", "z" };
		for (int i = 1; i <= 3; i++)
			for (int j = 1; j <= 3; j++)
				for (int k = 1; k <= 3; k++) {
					if (i != j && j != k && i != k) {
						a = i;
						b = j;
						c = k;
						if (a != x && c != x && c != z) {
							System.out.println("a--" + temp[a - 1]);
							System.out.println("b--" + temp[b - 1]);
							System.out.println("c--" + temp[c - 1]);
						}
					}
				}
	}

}

package com.sailor.game;

/**
 * 题目：海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子凭据分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。
 * 第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三、第四、第五只猴子都是这样做的，
 * 问海滩上原来最少有多少个桃子？ 解：最少的情况下，第五只猴子分配时每只猴子得到一个桃子,这是第五只猴子看到的桃子是6个
 * 
 * @author Sailor
 * 
 */
public class MonkeyGetPeach {

	public static void main(String[] args) {
		System.out.println(getPeach_Num(1));
	}

	// 返回桃子总数
	public static int getPeach_Num(int index) {
		if (index == 5)
			return 6;
		if (index < 5) {
			return getPeach_Num(index + 1) * 5 + 1;
		} else
			return 0;
	}

}

package com.sailor.game;

import java.util.Scanner;

/**
 * 
 * 题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
 * (1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。 (2)如果n<>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。
 * (3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。
 * 
 * @author Sailor
 */
public class Prime_factor {

	public static void main(String[] args){
		
		Scanner in=new Scanner(System.in);
		System.out.println("请输入待分解因式的数字：");
		int num = in.nextInt();
		String result = num+"=";
		while (num > 1) {
			for (int i = 1; i < num;) {
				int prime = getPrime(i);
				if (num % prime == 0) {//从最小的质数开始找起
					num /= prime;
					result += prime + (num<=1 ? "" : "*");
				}else{
					i=prime;
				}
			}
		}
		System.out.println(result);
	}

	/**
	 * 返回比n大的最小质数
	 * 
	 * @param n
	 * @return
	 */
	public static int getPrime(int n) {
		int prime = 1;
		for (int i = 1 + n;; i++) {
			boolean mark = true;
			for (int j = 2; j <= Math.sqrt(i) + 1; j++) {
				if (i % j == 0 && j != i) {
					mark = false;
					break;
				}
			}
			if (mark) {
				prime = i;
				break;
			}
		}
		return prime;
	}

}

因为到第10天只有一个桃子了，我们就可以这么理解了，假设今天还有x个桃子，那么他前一天的应该是(x+1)*2，那么直接使用

int x = 1;
  for(int i=9;i>0;i--){
   x = (x+1) * 2;
  }
  System.out.println(x);

就可以计算到你的结果。

正解，这样效率最高。