3的子集非遞歸java的簡單介紹

本文目錄一覽：

• 1、JAVA編程問題：求漢諾塔非遞歸JAVA代碼
• 2、列舉集合{1，2，3}的所有子集．
• 3、用java編寫hanoi塔的非遞歸演算法。
• 4、java 用遞歸創建二叉樹，非遞歸遍歷二叉樹輸出節點
• 5、java樹級對象遞歸查找子集問題

JAVA編程問題：求漢諾塔非遞歸JAVA代碼

public class Hannuota {

private int n;//儲存檔子個數

public Hannuota(int n){

this.n = n;

}

public void function(){

//初始化三個柱子，A是開始堆滿盤子的柱子，C是目標柱子

Pillar a = new Pillar(n,n,”A”);

Pillar b = new Pillar(n,”B”);

Pillar c = new Pillar(n,”C”);

//把三個柱子按順序排好，詳見後面的演算法那裡的解釋

Pillar[] pillars = new Pillar[3];

pillars[0] = a;

if(n%2==0){

pillars[1] = b;

pillars[2] = c;

}else{

pillars[1] = c;

pillars[2] = b;

}

//開始移動，k用來計數，移動次數為2^n-1,至於為什麼，我不太清楚，

//反正有人證明過。i是用來保存最小那個盤子正在哪跟柱子上的。

int i=0;

for(int k=0;k(int)Math.pow(2, n)-1;){

int min;

//將最小的盤子順時針移動一個柱子

min = pillars[i%3].Pop();

pillars[(i+1)%3].Push(min);

System.out.println(pillars[i%3]+”-“+pillars[(i+1)%3]);

k++;

i++;

//這個IF好像可以不要，當時寫的，後面忘了刪除。

if(k(int)Math.pow(2, n)-1){

//如果，剩下兩根柱子中，某一根為空，則一定是非空那根中最上面個盤子

//移動到空的那個柱子上。若兩根都不為空，則把編號小的一個盤子

//移動到另外跟柱子上

if(!pillars[(i-1)%3].isEmpty()(pillars[(i+1)%3].isEmpty()||pillars[(i+1)%3].Top()pillars[(i-1)%3].Top())){

min=pillars[(i-1)%3].Pop();

pillars[(i+1)%3].Push(min);

System.out.println(pillars[(i-1)%3]+”-“+pillars[(i+1)%3]);

}else{

min=pillars[(i+1)%3].Pop();

pillars[(i-1)%3].Push(min);

System.out.println(pillars[(i+1)%3]+”-“+pillars[(i-1)%3]);

}

k++;

}

}

}

//主函數，用來測試的。3表示3個盤子。

public static void main(String args[]){

new Hannuota(3).function();

}

}

class Pillar{//構造一個新類，表示柱子，實際是當一個棧在用

private int[] s;

private int top;

private String name;

public String toString(){

return name;

}

//這個構造函數用來構造BC兩個柱子，下面那個用來構造柱子A。其實也可以寫成一個構造函數。

public Pillar(int max,String name){

s = new int[max];

top = -1;

this.name = name;

for(int i=0;imax;i++){

s[i] = max+1;

}

}

public Pillar(int n,int max,String name){

s = new int[max];

top = n-1;

this.name = name;

for(int i=0;imax;i++){

s[i] = max – i;

}

}

//這後面這些就是棧的基本方法了，不用介紹了吧

public boolean isEmpty(){

return top==-1?true:false;

}

public int Top (){

return s[top];

}

public int Pop(){

return s[top–];

}

public void Push(int x){

s[++top] = x;

}

}

演算法是這個

首先容易證明，當盤子的個數為n時，移動的次數應等於2^n – 1。

首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上。

根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；

若n為奇數，按順時針方向依次擺放 A C B。

（1）按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；

若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。

（2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。

即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤

這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。

（3）反覆進行（1）（2）操作，最後就能按規定完成漢諾塔的移動。

這玩意要非遞歸真麻煩。需不需要加點注釋？

其實我不明白乾嘛非要非遞歸。。。

列舉集合{1，2，3}的所有子集．

含有1個元素的子集有{1}，{2}，{3}； 含有2個元素的子集有{1，2}，{1，3}，{2，3}； 含有3個元素的子集有{1，2，3}．共有子集8個 子集中分別含1，2，3三個元素中的0個，1個，2個或者3個

用java編寫hanoi塔的非遞歸演算法。

這是個好問題，很少看到有人寫漢諾塔的非遞歸…其實只要先寫出遞歸，然後把遞歸的每一步要做的事情記錄在一個棧裡面就可以了

public class Test {

private static void emitStep(int source, int dest) {

System.out.println(source + ” – ” + dest);

}

static class Step {

Step(int n, int s, int d, int t) {

this.n = n;

source = s;

dest = d;

temp = t;

}

int n, source, dest, temp;

}

private static void hanoi(int n, int source, int dest, int temp) {

java.util.StackStep steps = new java.util.StackStep();

steps.add(new Step(n, source, dest, temp));

while (steps.empty() == false) {

Step step = steps.pop();

if (step.n == 1) {

emitStep(step.source, step.dest);

continue;

}

steps.push(new Step(step.n – 1, step.temp, step.dest, step.source));

steps.push(new Step(1, step.source, step.dest, 0));

steps.push(new Step(step.n – 1, step.source, step.temp, step.dest));

}

}

public static void main(String[] args) {

hanoi(3, 1, 3, 2);

}

}

java 用遞歸創建二叉樹，非遞歸遍歷二叉樹輸出節點

我自己用遞歸寫了下，不知道能不能給你幫助：

測試類：

package tree;

import java.util.*;

public class Test {

public static void main(String[] args){

ListTree trees=new ArrayListTree();

int id=1;

Tree tree1=new Tree(0,id++,”張三丰”);

Tree tree2=new Tree(tree1.getId(),id++,”武當宋大俠宋遠橋”);

Tree tree3=new Tree(tree1.getId(),id++,”武當俞二俠俞蓮舟”);

Tree tree4=new Tree(tree1.getId(),id++,”武當俞三俠俞岱岩”);

Tree tree5=new Tree(tree1.getId(),id++,”武當張四俠張松溪”);

Tree tree6=new Tree(tree1.getId(),id++,”武當張五俠張翠山”);

Tree tree7=new Tree(tree1.getId(),id++,”武當殷六俠殷梨亭”);

Tree tree8=new Tree(tree1.getId(),id++,”武當莫七俠莫聲谷”);

Tree tree9=new Tree(tree6.getId(),id++,”明教張無忌”);

Tree tree13=new Tree(tree2.getId(),id++,”叛徒宋青書”);

Tree tree10=new Tree(0,id++,”任我行”);

Tree tree11=new Tree(tree10.getId(),id++,”令狐沖”);

Tree tree12=new Tree(tree10.getId(),id++,”任盈盈”);

trees.add(tree1);

trees.add(tree2);

trees.add(tree3);

trees.add(tree4);

trees.add(tree5);

trees.add(tree6);

trees.add(tree7);

trees.add(tree8);

trees.add(tree9);

trees.add(tree10);

trees.add(tree11);

trees.add(tree12);

trees.add(tree13);

for(int i=0;itrees.size();i++){

Tree tree=trees.get(i);

if(tree.getParentId()==0){

tree.showChildTree(trees);

}

}

}

}

樹類：

package tree;

import java.util.List;

public class Tree {

private int parentId;

private int id;

private String showStr;

private String Spaces=””;

public Tree() {

// TODO Auto-generated constructor stub

}

public Tree(int parentId,int id,String showStr){

this.parentId=parentId;

this.id=id;

this.showStr=showStr;

}

public void showChildTree(ListTree trees){

if(parentId!=0){

trees.get(id-1).setSpaces(trees.get(parentId-1).getSpaces()+” “);

}

System.out.println(trees.get(id-1).getSpaces()+showStr);

for(int i=0;itrees.size();i++){

Tree tree=trees.get(i);

if(tree.getParentId()==id){

tree.showChildTree(trees);

}

}

}

public int getParentId() {

return parentId;

}

public void setParentId(int parentId) {

this.parentId = parentId;

}

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public String getShowStr() {

return showStr;

}

public void setShowStr(String showStr) {

this.showStr = showStr;

}

public String getSpaces() {

return Spaces;

}

public void setSpaces(String spaces) {

Spaces = spaces;

}

}

效果圖：

張三丰

武當宋大俠宋遠橋

叛徒宋青書

武當俞二俠俞蓮舟

武當俞三俠俞岱岩

武當張四俠張松溪

武當張五俠張翠山

明教張無忌

武當殷六俠殷梨亭

武當莫七俠莫聲谷

任我行

令狐沖

任盈盈

java樹級對象遞歸查找子集問題

package com.demo.dept;

/**

 * @author dongbin.yu

 * @from 2016-05-06

 * @since V1.0

 */

public class Dept {

    private int id;

    private String name;

    private int parentId;

    public int getId() {

        return id;

    }

    public void setId(int id) {

        this.id = id;

    }

    public String getName() {

        return name;

    }

    public void setName(String name) {

        this.name = name;

    }

    public int getParentId() {

        return parentId;

    }

    public void setParentId(int parentId) {

        this.parentId = parentId;

    }

    public Dept(int id, String name, int parentId) {

        this.id = id;

        this.name = name;

        this.parentId = parentId;

    }

}

package com.demo.dept;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

/**

 * @author dongbin.yu

 * @from 2016-05-06

 * @since V1.0

 */

public class DeptTest {

    private static ListDept depts = new ArrayList();

    static{

        depts.add(new Dept(1,”部門1″,0));

        depts.add(new Dept(2,”部門2″,1));

        depts.add(new Dept(3,”部門3″,1));

        depts.add(new Dept(4,”部門4″,1));

        depts.add(new Dept(5,”部門5″,2));

        depts.add(new Dept(6,”部門6″,3));

        depts.add(new Dept(7,”部門7″,2));

        depts.add(new Dept(8,”部門8″,2));

        depts.add(new Dept(9,”部門9″,1));

        depts.add(new Dept(10,”部門10″,5));

    }

    public static void main(String[] args) {

        MapInteger, ListInteger deptMap = new HashMap();

        for (Dept dept : depts) {

            deptMap.put(dept.getId(),getChildDept(dept.getId()));

        }

        System.out.println(deptMap);

    }

    private static ListInteger getChildDept(int id){

        ListInteger ids = new ArrayList();

        for (Dept dept : depts) {

            if(dept.getParentId() == id){

                //添加第一次父id符合的

                ids.add(dept.getId());

                //添加嵌套父id符合的

                ids.addAll(getChildDept(dept.getId()));

            }

        }

                Collections.sort(ids);

        return ids;

    }

}