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

zpsailor

浏览: 43350 次
性别:
来自: 重庆

最近访客更多访客>>

feng888918

cgf198171

18200254753

lollypop.

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Java原创

编程 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;
	}

}

分享到：

编程经典问题及其Java求解（二） | Java解最短路径问题

2010-05-31 11:14
浏览 2150
评论(38)
论坛回复 / 浏览 (35 / 20223)
分类:编程语言
查看更多

18 楼 zpsailor 2010-06-01

kevin_wanwei 写道

我晕倒，现在还在迷恋这些程序，悲哀啊！！！！！！！！！！！！

哥们儿，不是迷恋这些程序，只是一些基础的东西偶尔总会接触下吧。

17 楼 zpsailor 2010-06-01

zhao103804 写道

<div class="quote_title">skyremark 写道</div>
<div class="quote_div">
<div class="quote_title">写道你这个问题的解答方法可能并不是最简单的，而且有把问题复杂化的嫌疑。</div>
<div class="quote_div">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); } } 
</div>

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

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

就可以计算到你的结果。

正解，这样效率高多了

</div>

恩，你这个方法貌似比递归要简单些，其实我前面用数组的那个方法大概和你这个差不多，只需稍加改动

16 楼 yangfuchao418 2010-06-01

搞程序要么就搞算法，要么就搞业务。

15 楼 zpsailor 2010-06-01

bigkai_13 写道

想起来大学时候天天啃着谭浩强 C语言书的情景，现在基本这些算法忘的差不多了。感觉这些算法好处就是让你有递归的思想和熟练运用for循环.

对呀，是很基础的算法，不过面试题中还是有些会涉及的。我后面还会继续发布其他一些基础算法的！

14 楼 bigkai_13 2010-06-01

想起来大学时候天天啃着谭浩强 C语言书的情景，现在基本这些算法忘的差不多了。感觉这些算法好处就是让你有递归的思想和熟练运用for循环.

13 楼 zhuwei2008 2010-06-01

算法的思想应该有啊。可惜我在实际工作中处理的都是业务问题。算法涉及几乎为零

12 楼 kevin_wanwei 2010-06-01

我晕倒，现在还在迷恋这些程序，悲哀啊！！！！！！！！！！！！

11 楼 t42dw 2010-06-01

感觉是面试题样的，学习了

10 楼路在转角处 2010-05-31

业务逻辑代码是不是封装到一个方法里更好些。

9 楼 Wanghuidong 2010-05-31

恩不错学习一下

8 楼 shuiguozheng 2010-05-31

挺有意思的！之前读书的时候玩过

7 楼 zhao103804 2010-05-31

<div class="quote_title">skyremark 写道</div>
<div class="quote_div">
<div class="quote_title">写道你这个问题的解答方法可能并不是最简单的，而且有把问题复杂化的嫌疑。</div>
<div class="quote_div">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); } } 
</div>
 
 
因为到第10天只有一个桃子了，我们就可以这么理解了，假设今天还有x个桃子，那么他前一天的应该是(x+1)*2，那么直接使用
int x = 1; for(int i=9;i>0;i--){ x = (x+1) * 2; } System.out.println(x);
 
就可以计算到你的结果。
 
正解，这样效率高多了
</div>

6 楼 eric_kong 2010-05-31

<div class="quote_title">skyremark 写道</div>
<div class="quote_div">
<div class="quote_title">写道你这个问题的解答方法可能并不是最简单的，而且有把问题复杂化的嫌疑。</div>
<div class="quote_div">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); } } 
</div>
 
 
因为到第10天只有一个桃子了，我们就可以这么理解了，假设今天还有x个桃子，那么他前一天的应该是(x+1)*2，那么直接使用
int x = 1; for(int i=9;i>0;i--){ x = (x+1) * 2; } System.out.println(x);
 
就可以计算到你的结果。
</div>
 正解，这样效率最高。

5 楼 skyremark 2010-05-31

<div class="quote_title">写道你这个问题的解答方法可能并不是最简单的，而且有把问题复杂化的嫌疑。</div>
<div class="quote_div">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); } } 
</div>
 
 
因为到第10天只有一个桃子了，我们就可以这么理解了，假设今天还有x个桃子，那么他前一天的应该是(x+1)*2，那么直接使用
int x = 1; for(int i=9;i>0;i--){ x = (x+1) * 2; } System.out.println(x);
 
就可以计算到你的结果。

4 楼 orcl_zhang 2010-05-31

最大公约数，用欧几里得算法。O(logN)的复杂度。

3 楼 pixy 2010-05-31

最近也在准备比赛...天天做这些，痛苦ing~~~~~

2 楼 cdl2008sky 2010-05-31

大学里面天天编这些程序

1 楼 sarin 2010-05-31

递归思想要有，否则有些问题没法做了就。

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论