java演算法題解法

❶ 用java解決tsp問題用什麼演算法最簡單

package noah;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class TxTsp {

private int cityNum; // 城市數量
private int[][] distance; // 距離矩陣

private int[] colable;//代表列，也表示是否走過，走過置0
private int[] row;//代錶行，選過置0

public TxTsp(int n) {
cityNum = n;
}

private void init(String filename) throws IOException {
// 讀取數據
int[] x;
int[] y;
String strbuff;
BufferedReader data = new BufferedReader(new InputStreamReader(
new FileInputStream(filename)));
distance = new int[cityNum][cityNum];
x = new int[cityNum];
y = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
// 讀取一行數據，數據格式1 6734 1453
strbuff = data.readLine();
// 字元分割
String[] strcol = strbuff.split(" ");
x[i] = Integer.valueOf(strcol[1]);// x坐標
y[i] = Integer.valueOf(strcol[2]);// y坐標
}
data.close();

// 計算距離矩陣
// ，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優值為10628
for (int i = 0; i < cityNum - 1; i++) {
distance[i][i] = 0; // 對角線為0
for (int j = i + 1; j < cityNum; j++) {
double rij = Math
.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
* (y[i] - y[j])) / 10.0);
// 四捨五入，取整
int tij = (int) Math.round(rij);
if (tij < rij) {
distance[i][j] = tij + 1;
distance[j][i] = distance[i][j];
} else {
distance[i][j] = tij;
distance[j][i] = distance[i][j];
}
}
}

distance[cityNum - 1][cityNum - 1] = 0;

colable = new int[cityNum];
colable[0] = 0;
for (int i = 1; i < cityNum; i++) {
colable[i] = 1;
}

row = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
row[i] = 1;
}

}

public void solve(){

int[] temp = new int[cityNum];
String path="0";

int s=0;//計算距離
int i=0;//當前節點
int j=0;//下一個節點
//默認從0開始
while(row[i]==1){
//復制一行
for (int k = 0; k < cityNum; k++) {
temp[k] = distance[i][k];
//System.out.print(temp[k]+" ");
}
//System.out.println();
//選擇下一個節點，要求不是已經走過，並且與i不同
j = selectmin(temp);
//找出下一節點
row[i] = 0;//行置0，表示已經選過
colable[j] = 0;//列0，表示已經走過

path+="-->" + j;
//System.out.println(i + "-->" + j);
//System.out.println(distance[i][j]);
s = s + distance[i][j];
i = j;//當前節點指向下一節點
}
System.out.println("路徑:" + path);
System.out.println("總距離為:" + s);

}

public int selectmin(int[] p){
int j = 0, m = p[0], k = 0;
//尋找第一個可用節點，注意最後一次尋找，沒有可用節點
while (colable[j] == 0) {
j++;
//System.out.print(j+" ");
if(j>=cityNum){
//沒有可用節點，說明已結束，最後一次為 *-->0
m = p[0];
break;
//或者直接return 0;
}
else{
m = p[j];
}
}
//從可用節點J開始往後掃描，找出距離最小節點
for (; j < cityNum; j++) {
if (colable[j] == 1) {
if (m >= p[j]) {
m = p[j];
k = j;
}
}
}
return k;
}

public void printinit() {
System.out.println("print begin....");
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
System.out.print(distance[i][j] + " ");
}
System.out.println();
}
System.out.println("print end....");
}

public static void main(String[] args) throws IOException {
System.out.println("Start....");
TxTsp ts = new TxTsp(48);
ts.init("c://data.txt");
//ts.printinit();
ts.solve();
}
}

❷ java經典演算法題——猴子吃桃

main()
{
int day,x1,x2;
day=9;
x2=1;
while(day>0)
{x1=(x2+1)*2;/*第一天的桃子數是第2天桃子數加1後的2倍*/
x2=x1;
day--;
}
print("the total is "+x1);
}

❸ java演算法面試題：排序都有哪幾種方法

一、冒泡排序
[java] view plain
package sort.bubble;
import java.util.Random;
/**
* 依次比較相鄰的兩個數，將小數放在前面，大數放在後面
* 冒泡排序，具有穩定性
* 時間復雜度為O（n^2）
* 不及堆排序，快速排序O（nlogn，底數為2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for(int i = 0 ; i < 10 ; i++){
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for(int i : sort){
System.out.print(i+" ");
}
buddleSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for(int i : sort){
System.out.print(i+" ");
}
}
/**
* 冒泡排序
* @param sort
*/
private static void buddleSort(int[] sort){
for(int i=1;i<sort.length;i++){
for(int j=0;j<sort.length-i;j++){
if(sort[j]>sort[j+1]){
int temp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = temp;
}
}
}
}
}
二、選擇排序
[java] view plain
package sort.select;
import java.util.Random;
/**
* 選擇排序
* 每一趟從待排序的數據元素中選出最小（或最大）的一個元素，
* 順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
* 選擇排序是不穩定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
selectSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 選擇排序
* @param sort
*/
private static void selectSort(int[] sort){
for(int i =0;i<sort.length-1;i++){
for(int j = i+1;j<sort.length;j++){
if(sort[j]<sort[i]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
三、快速排序
[java] view plain
package sort.quick;
/**
* 快速排序 通過一趟排序將要排序的數據分割成獨立的兩部分， 其中一部分的所有數據都比另外一部分的所有數據都要小，
* 然後再按此方法對這兩部分數據分別進行快速排序， 整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
System.out.print("排序前的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.print("排序後的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
}
/**
* 快速排序
* @param sort 要排序的數組
* @param start 排序的開始座標
* @param end 排序的結束座標
*/
public static void quickSort(int[] sort, int start, int end) {
// 設置關鍵數據key為要排序數組的第一個元素，
// 即第一趟排序後，key右邊的數全部比key大，key左邊的數全部比key小
int key = sort[start];
// 設置數組左邊的索引，往右移動判斷比key大的數
int i = start;
// 設置數組右邊的索引，往左移動判斷比key小的數
int j = end;
// 如果左邊索引比右邊索引小，則還有數據沒有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左邊索引比右邊索引要大，說明第一次排序完成，將sort[j]與key對換，
// 即保持了key左邊的數比key小，key右邊的數比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//遞歸調用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
[java] view plain
/**
* 快速排序
*
* @param a
* @param low
* @param high
* voidTest
*/
public static void kuaisuSort(int[] a, int low, int high)
{
if (low >= high)
{
return;
}
if ((high - low) == 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
return;
}
}
int key = a[low];
int left = low + 1;
int right = high;
while (left < right)
{
while (left < right && left <= high)// 左邊向右
{
if (a[left] >= key)
{
break;
}
left++;
}
while (right >= left && right > low)
{
if (a[right] <= key)
{
break;
}
right--;
}
if (left < right)
{
swap(a, left, right);
}
}
swap(a, low, right);
kuaisuSort(a, low, right);
kuaisuSort(a, right + 1, high);
}
四、插入排序
[java] view plain
package sort.insert;
/**
* 直接插入排序
* 將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據
* 演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
directInsertSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
順便添加一份，差不多的
[java] view plain
public static void charuSort(int[] a)
{
int len = a.length;
for (int i = 1; i < len; i++)
{
int j;
int temp = a[i];
for (j = i; j > 0; j--)//遍歷i之前的數字
{
//如果之前的數字大於後面的數字，則把大的值賦到後面
if (a[j - 1] > temp)
{
a[j] = a[j - 1];
} else
{
break;
}
}
a[j] = temp;
}
}
把上面整合起來的一份寫法：
[java] view plain
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}
private void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、順便貼個二分搜索法
[java] view plain
package search.binary;
public class Main {
public static void main(String[] args) {
int[] sort = {1,2,3,4,5,6,7,8,9,10};
int mask = binarySearch(sort,6);
System.out.println(mask);
}
/**
* 二分搜索法，返回座標，不存在返回-1
* @param sort
* @return
*/
private static int binarySearch(int[] sort,int data){
if(data<sort[0] || data>sort[sort.length-1]){
return -1;
}
int begin = 0;
int end = sort.length;
int mid = (begin+end)/2;
while(begin <= end){
mid = (begin+end)/2;
if(data > sort[mid]){
begin = mid + 1;
}else if(data < sort[mid]){
end = mid - 1;
}else{
return mid;
}
}
return -1;
}
}

❹ Java迷宮演算法問題（用棧實現）有演算法簡述

importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Scanner;

publicclassTest{

	publicstaticvoidmain(String[]args)throwsFileNotFoundException{
		Scannerinput=newScanner(newFile("Maze2tong.txt"));
		introw=0;
		char[][]Mazemap=newchar[12][58];
		while(input.hasNext()){
			Stringline=input.nextLine();
			for(intcolumn=0;column<=line.length()-1;column++){
				charc=line.charAt(column);
				Mazemap[row][column]=c;
			}
			row++;
		}
		for(inti=0;i<12;i++){
			for(intj=0;j<58;j++){
				System.out.print(Mazemap[i][j]);
			}
			System.out.print("
");
		}
		LinkedList<TwoTuple<Integer,Integer>>trace=newLinkedList<TwoTuple<Integer,Integer>>();
		System.out.println(maze(Mazemap,trace));
		System.out.println(trace);
	}

	publicstaticbooleanmaze(char[][]maze,
			List<TwoTuple<Integer,Integer>>trace){
		LinkedList<TwoTuple<Integer,Integer>>path=newLinkedList<TwoTuple<Integer,Integer>>();
		HashSet<TwoTuple<Integer,Integer>>traverse=newHashSet<TwoTuple<Integer,Integer>>();

		for(inti=0;i<maze.length;i++){
			for(intj=0;j<maze[i].length;j++){
				if(maze[i][j]=='S'){
					path.add(newTwoTuple<Integer,Integer>(i,j));
				}
			}
		}
		while(!path.isEmpty()){
			TwoTuple<Integer,Integer>temp=path.pop();

			if(traverse.contains(temp)){
				continue;
			}elseif(maze[temp.first][temp.second]=='F'){
				trace.add(temp);
				returntrue;
			}elseif(!traverse.contains(temp)){
				if(temp.second+1<maze[temp.first].length
						&&maze[temp.first][temp.second+1]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first,
							temp.second+1));
				if(temp.second-1>0
						&&maze[temp.first][temp.second-1]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first,
							temp.second-1));
				if(temp.first+1<maze.length
						&&maze[temp.first+1][temp.second]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first+1,
							temp.second));
				if(temp.first-1>0
						&&maze[temp.first-1][temp.second]!='W')
					path.add(newTwoTuple<Integer,Integer>(temp.first-1,
							temp.second));
				traverse.add(temp);
				trace.add(temp);
			}
		}
		trace.clear();
		returnfalse;
	}
}

classTwoTuple<A,B>{
	publicfinalAfirst;
	publicfinalBsecond;

	publicTwoTuple(Aa,Bb){
		first=a;
		second=b;
	}

	@Override
	publicinthashCode(){
		returnfirst.hashCode()+second.hashCode();
	}

	@Override
	publicbooleanequals(Objectobj){
		if(!(objinstanceofTwoTuple)){

		}
		returnobjinstanceofTwoTuple&&first.equals(((TwoTuple)obj).first)
				&&second.equals(((TwoTuple)obj).second);
	}

	publicStringtoString(){
		return"("+first+","+second+")";
	}
}///:-

importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.LinkedList;
importjava.util.Scanner;
classMyPoint
{
publicbooleanvisited=false;
publicintparentRow=-1;
publicintparentColumn=-1;
publicfinalcharcontent;
publicintx;
publicinty;
publicMyPoint(charc,intx,inty)
{
		this.content=c;
		this.x=x;
		this.y=y;
}
}
publicclassMaze
{

publicstaticMyPoint[][]getMazeArray(){
		Scannerinput=null;
		MyPoint[][]mazemap=newMyPoint[12][58];
		try{
			input=newScanner(newFile("Maze2tong.txt"));
			introw=0;
			while(input.hasNext()){
				Stringline=input.nextLine();
				for(intcolumn=0;column<=line.length()-1;column++){
					charc=line.charAt(column);
					MyPointpoint=newMyPoint(c,row,column);
					mazemap[row][column]=point;
				}
				row++;
			}
			input.close();
		}catch(FileNotFoundExceptione){
			e.printStackTrace();
		}
		returnmazemap;
}
publicstaticbooleantomRun(MyPoint[][]maze,MyPointend)
{
		intx=maze.length;
		inty=maze[0].length;
		LinkedList<MyPoint>stack=newLinkedList<MyPoint>();
		for(inti=0;i<maze.length;i++){
			for(intj=0;j<maze[i].length;j++){
				if(maze[i][j].content=='S'){
					stack.push(maze[i][j]);
					maze[i][j].visited=true;
				}
			}
		}
booleanresult=false;
while(!stack.isEmpty())
{
MyPointt=stack.pop();
//System.out.println("poppoint:"+t.x+""+t.y+"value:"+maze[t.x][t.y]);
if(t.content=='F')
{
result=true;
end.x=t.x;
end.y=t.y;
break;
}
if(t.x-1>0&&maze[t.x-1][t.y].visited==false&&maze[t.x-1][t.y].content!='W')
{
stack.push(maze[t.x-1][t.y]);
maze[t.x-1][t.y].parentRow=t.x;
maze[t.x-1][t.y].parentColumn=t.y;
maze[t.x-1][t.y].visited=true;
}
if(t.x+1<x&&maze[t.x+1][t.y].visited==false&&maze[t.x+1][t.y].content!='W')
{
stack.push(maze[t.x+1][t.y]);
maze[t.x+1][t.y].parentRow=t.x;
maze[t.x+1][t.y].parentColumn=t.y;
maze[t.x+1][t.y].visited=true;
}
if(t.y-1>0&&maze[t.x][t.y-1].visited==false&&maze[t.x][t.y-1].content!='W')
{
stack.push(maze[t.x][t.y-1]);
maze[t.x][t.y-1].parentRow=t.x;
maze[t.x][t.y-1].parentColumn=t.y;
maze[t.x][t.y-1].visited=true;
}
if(t.y+1<y&&maze[t.x][t.y+1].visited==false&&maze[t.x][t.y+1].content!='W')
{
stack.push(maze[t.x][t.y+1]);
maze[t.x][t.y+1].parentRow=t.x;
maze[t.x][t.y+1].parentColumn=t.y;
maze[t.x][t.y+1].visited=true;
}

}
returnresult;
}
publicstaticvoidshow(intx,inty,MyPoint[][]visited)
{
if(visited[x][y].parentRow==-1)
{
System.out.println("["+x+","+y+"]");
return;
}
show(visited[x][y].parentRow,visited[x][y].parentColumn,visited);
System.out.println("->"+"["+x+","+y+"]");
}
publicstaticvoidmain(String[]args)
{
		MyPoint[][]maze=getMazeArray();
		MyPointpoint=newMyPoint('c',1,1);
if(tomRun(maze,point))
{
System.out.println("逃生路徑如下：");
show(point.x,point.y,maze);
}
else
System.out.println("無法走出迷宮！");
}
}

❺ 3道java編程題，求解

packageTestPerson;
/**
*(1)編寫程序實現如下功能：已知Person類包含三個公共成員變數（姓名、性別、年齡）和一個構造方法，
*Student類是Person類的派生類，包含兩個新的公共成員變數(學號、班號)、兩個公共方法（修改年齡、顯示基本信息）及一個構造方法。
*在測試類Test1中，定義一組學生對象，並初始化他們的基本信息，然後依次輸出。
*/
publicclassTest1{
	publicstaticvoidmain(String[]args){
		Student[]student=newStudent[3];
		student[0]=newStudent("小李","男",12,20181101,01);
		student[1]=newStudent("小南","女",13,20001102,01);
		student[2]=newStudent("小李","男",12,20181103,01);
		
		for(Studentstu:student){
			stu.showInformation();
		}
	}
}

classPerson{
	publicStringname;
	publicStringsex;
	publicintage;
	publicPerson(Stringname,Stringsex,intage){
		super();
		this.name=name;
		this.sex=sex;
		this.age=age;
	}
}

classStudentextendsPerson{
	publiclongstudentId;
	publiclongclassId;
	publicvoidsetAge(intage){
		age=this.age;
	}
	publicvoidshowInformation(){
		System.out.println("我的姓名是"+name+","+"我的性別是"+sex+","+"我的年齡是"+age
				+"歲,"+"我的學號是"+studentId+","+"我的班號是"+classId+"班");
	}
	publicStudent(Stringname,Stringsex,intage,longstudentId,
			longclassId){
		super(name,sex,age);
		this.studentId=studentId;
		this.classId=classId;
	}
}

不可否認，我現在是有點閑，所以我就幫你寫第一個吧，至於後面兩個，我就不寫了，看看還有沒有其他人有點閑時間，看緣分吧

運行結果：

我的姓名是小李,我的性別是男,我的年齡是12歲,我的學號是20181101,我的班號是1班

我的姓名是小南,我的性別是女,我的年齡是13歲,我的學號是20001102,我的班號是1班

我的姓名是小李,我的性別是男,我的年齡是12歲,我的學號是20181103,我的班號是1班