風生
- 八皇后
- 原始碼
- 圖示分析秒懂原始碼
- 再進階：把每一種情況的棋圖都列印出來
- 整體代碼實作
- 漢諾塔
- 原始碼
- 圖示分析秒殺原始碼
- 迷宮問題之在原始碼解釋
- 先用鏈表模擬一個堆疊：
- 操作堆疊解決問題
八皇后
在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法？
原始碼
public class Demo {
static int TRUE = 1, FALSE = 0, EIGHT = 8;
static int[] queen = new int[EIGHT];
static int number = 0;
static int count=0;
//建構式
public Demo() {
number = 0;
}
public static void print1(){
count++;
for(int i=0;i<EIGHT;i++){
System.out.print(queen[i]+" ");
}
System.out.println();
}
//判斷在（row，col）上的皇后是否遭受攻擊
public static boolean attack(int row) {
for(int i=0;i<row;i++){
if(queen[i]==queen[row]||Math.abs(i-row)==Math.abs(queen[i]-queen[row])){
return false;
}
}
return true;
}
//確定皇后放的位置
public static void thePlace(int row){
if(row==EIGHT){
print1();
print2();
return;
}
for(int i=0;i<EIGHT;i++){
queen[row]=i;
if(attack(row))
thePlace(row+1);
}
}
public static void main(String[] args){
thePlace(0);
System.out.println(count);
}
}
圖示分析秒懂原始碼
static int[] queen = new int[EIGHT];
注釋：原始碼中row代表行數，請讀者想象出一個棋盤，這里定義一個一維陣列queen[EIGHT];用一維陣列的每一個源數的下標作為行號，下標對應的陣列中的數值作為列號，所以每列印出來的一個一維數中的每一個元素及其對應的下標即為每一種情況下對應的所有落子的坐標
public static boolean attack(int row) {
for(int i=0;i<row;i++){
if(queen[i]==queen[row]||Math.abs(i-row)==Math.abs(queen[i]-queen[row])){
return false;
}
}
return true;
}
attack()方法是用來判斷，其落子處所對應的列號和對角線上是否有其他皇后，如果有則不進入遞回，反之則進入遞回，
決議：
注意看原始碼中，main函式在最底下，僅呼叫了 thePlace（）方法，傳入引數為0，即在此方法中row（行數）先為0，先判斷row(行數)是否等于EIGHT(EIGHT=8)；不等于，往下進入for回圈，for回圈中有涉及遞回，注意看下面的圖示：
第一次棋盤為空直接落子，進入遞回，
每一次進入遞回都是因為找到了確定的行中的某一列可以落子的地方，找不到則在當前遞回層數中進入for回圈，直到找到可以落子的地方，如果回圈到頭，則回傳上一層遞回中的for回圈，如此一直回圈下去則可以統計出所有情況，
再進階：把每一種情況的棋圖都列印出來
public static void print2(){
String[][] arr={{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "}};
for(int i=0;i<EIGHT;i++){
arr[i][queen[i]]="*";
}
for(int i=0;i<EIGHT;i++){
for(int j=0;j<EIGHT;j++) {
if(j<EIGHT-1) {
System.out.print(" " + arr[i][j] + " ");
System.out.print("|");
}else{
System.out.print(" " + arr[i][j] + " ");
}
}
System.out.println();
if(i<EIGHT-1){
for (int k = 0; k < EIGHT; k++) {
if(k==7)
System.out.print("---");
else
System.out.print("---|");
}
}
System.out.println();
}
}
整體代碼實作
package 八皇后問題;
public class Demo {
static int TRUE = 1, FALSE = 0, EIGHT = 8;
static int[] queen = new int[EIGHT];
static int number = 0;
static int count=0;
//建構式
public Demo() {
number = 0;
}
//列印一維陣列結果
public static void print1(){
count++;
for(int i=0;i<EIGHT;i++){
System.out.print(queen[i]+" ");
}
System.out.println();
}
//列印棋盤式結果
public static void print2(){
String[][] arr={{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "},
{" "," "," "," "," "," "," "," "}};
for(int i=0;i<EIGHT;i++){
arr[i][queen[i]]="*";
}
for(int i=0;i<EIGHT;i++){
for(int j=0;j<EIGHT;j++) {
if(j<EIGHT-1) {
System.out.print(" " + arr[i][j] + " ");
System.out.print("|");
}else{
System.out.print(" " + arr[i][j] + " ");
}
}
System.out.println();
if(i<EIGHT-1){
for (int k = 0; k < EIGHT; k++) {
if(k==7)
System.out.print("---");
else
System.out.print("---|");
}
}
System.out.println();
}
}
//判斷在（row，col）上的皇后是否遭受攻擊
public static boolean attack(int row) {
for(int i=0;i<row;i++){
if(queen[i]==queen[row]||Math.abs(i-row)==Math.abs(queen[i]-queen[row])){
return false;
}
}
return true;
}
//確定皇后放的位置
public static void thePlace(int row){
if(row==EIGHT){
print1();
print2();
return;
}
for(int i=0;i<EIGHT;i++){
queen[row]=i;
if(attack(row))
thePlace(row+1);
}
}
public static void main(String[] args){
thePlace(0);
System.out.println(count);
}
}
漢諾塔
漢諾塔：漢諾塔(Tower of Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，
當圓盤為n時，一共要挪動多少次？
原始碼
import java.util.Scanner;
public class Demo2 {
static int times;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
System.out.println("請輸入盤子數量");
int j=sc.nextInt();
hanoi(j,'A','B','C');
}
public static void move(int disk,char p1,char p3){
System.out.println("第"+(++Demo2.times)+"次將"+disk+"從"+p1+"移動到"+p3);
}
public static void hanoi(int n,char p1,char p2,char p3){
if(n==1) {
move(n,p1, p3);
}else{
//將n-1個圓盤移到B柱上
hanoi(n-1,p1,p3,p2);
//將最后一個圓盤移到C柱上
move(n,p1,p3);
//將n-1個圓盤移到C柱上
hanoi(n-1,p2,p1,p3);
}
}
}
圖示分析秒殺原始碼
以n=3進行分析，
迷宮問題之在原始碼解釋
有一個迷宮地圖，有一些可達的位置，也有一些不可達的位置（障礙、墻壁、邊界），從一個位置到下一個位置只能通過向上（或者向右、或者向下、或者向左）走一步來實作，從起點出發，如何找到一條到達終點的通路，并在走過的路徑下留下標記，
先用鏈表模擬一個堆疊：
public class Node {
int x;
int y;
Node next;
public Node(){}
public Node(int x,int y){
this.x =x;
this.y =y;
next=null;
}
}
public class NodeList {
Node first;
Node last;
//壓堆疊
public void push(int x,int y){
Node newNode=new Node(x,y);
if(first==null){
first=newNode;
last=newNode;
}else{
last.next=newNode;
last=newNode;
}
}
//出堆疊
public void pop(){
if(first==null){
System.out.println("堆疊已滿，誤洗掉選項");
return;
}else{
Node delNode=first;
while(delNode.next!=last)
delNode=delNode.next;
delNode.next=last.next;
last=delNode;
}
}
}
操作堆疊解決問題
public class Demo {
public static int exitx=8;
public static int exity=10;
public static int[][] arr = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};
public static void main(String[] args) {
int x = 1;
int y = 1;
NodeList L = new NodeList();
System.out.println("老鼠走前");
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 12; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
while (x <=exitx&&y<=exity){
arr[x][y]=2;
if(arr[x-1][y]==0){
x--;
L.push(x,y);
}else if(arr[x+1][y]==0){
x++;
L.push(x,y);
}else if(arr[x][y-1]==0){
y--;
L.push(x,y);
}else if(arr[x][y+1]==0){
y++;
L.push(x,y);
}else{
if(chkExit(x,y,exitx,exity)){
break;
}
else{
arr[x][y]=2;
L.pop();
x=L.last.x;
y=L.last.y;
}
}
}
System.out.println("老鼠走后");
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 12; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
public static boolean chkExit(int x,int y,int exitx,int exity) {
if (x == exitx && y == exity) {
if(arr[x-1][y]==1||arr[x+1][y]==1||arr[x][y-1]==1||arr[x][y+1]==2){
return true;
}else if(arr[x-1][y]==1||arr[x+1][y]==1||arr[x][y-1]==2||arr[x][y+1]==1){
return true;
}else if(arr[x-1][y]==1||arr[x+1][y]==2||arr[x][y-1]==1||arr[x][y+1]==1){
return true;
}else if(arr[x-1][y]==2||arr[x+1][y]==1||arr[x][y-1]==1||arr[x][y+1]==1)
return true;
else
return false;
}else{
return false;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/294204.html
標籤：java