文章目錄
- 一、仿真名稱
- 二、仿真目的
- 1．基于蠻力法思想實作
- 1.1、 僞代碼描述
- 1.2、代碼實作
- 1.3、背包問題的時間效率分析
- 2．基于減治法思想實作二叉查找樹的插入與查找
- 2.1 、二叉查找樹的插入與查找的僞代碼描述
- 2.2、二叉查找樹的插入與查找的源代碼實作
- 2.3、叉查找樹的插入與查找的時間效率分析
- 3、測試結果
- 3.1、基于減治法思想實作二叉查找樹的插入與查找的測試用例結果截圖
一、仿真名稱
蠻力法與減治算法應用
二、仿真目的
1.掌握蠻力法和減治法的基本思想；
2.學會運用蠻力法和減治算法解決實際系統設計應用中碰到的問題。
1．基于蠻力法思想實作
1.1、 僞代碼描述
算法 solveKs(w,v,index,capacity)
//實作放入背包的物品價值最大化
//輸入背包的容量capacity,價值v和品質w.存儲了商品品質W[0…n-1]和價值的數組V[0…n-1]
//輸出背包的最大價值
v←0,m←0
If index<0 and capacity<0
Return 0
Else
res←solveKs(w,v,index-1,capacity) //不存放第i個物品所得價值
if
w[index]<=capacity
res←Math.max(res,v[index]+solveKs(w,v,index-1,capacity-w[index]//放入或者不放入第i個物品時，背包最大的價值。
Return res 1.2、代碼實作
package com.back.cc;
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
int capacity;// 容量
int m;// 數量
int w = 0;// 初始化背包重量
int v = 0;// 初始化背包價值
// 輸入背包的容量和商品的數量
System.out.println("請輸入商品的數量：");
Scanner sc = new Scanner(System.in);
m = sc.nextInt();// 獲得商品數量
System.out.println("請輸入背包的容量：");
capacity = sc.nextInt();
// 用數組存儲商品的大小和價值
int[] weight = new int[m];
int[] values = new int[m];
// 通過循環指派
for (int i = 0; i < m; i++) {
System.out.println("請輸入第" + (i + 1) + "個商品的品質：");
weight[i] = sc.nextInt();
System.out.println("請輸入第" + (i + 1) + "個商品的價值：");
values[i] = sc.nextInt();
}
//直接調用靜态方法
System.out.println("存放的最大價值："+knapSack(weight, values, capacity));
// long time1 = System.currentTimeMillis();
// long time2 = System.currentTimeMillis();
// int time = (int) ((time2 - time1) / 1000);
// System.out.println("執行了：" + time + "秒！");
}
public static int knapSack(int[] w, int[] v, int C) {
int size = w.length;
return solveKS(w, v, size - 1, C);
}
private static int solveKS(int[] w, int[] v, int index, int capacity) {
// 基準條件：如果索引無效或者容量不足，直接傳回目前價值0
if (index < 0 || capacity <= 0)
return 0;
// 不放第index個物品所得價值
int res = solveKS(w, v, index - 1, capacity);
// 放第index個物品所得價值（前提是：第index個物品可以放得下）
if (w[index] <= capacity) {
res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
}
return res;
}
} 1.3、背包問題的時間效率分析
将前i件物品放入容量為v的背包中”這個子問題，若隻考慮第i件物品的政策（放或不放），那麼就可以轉化為一個隻牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。優化空間複雜度以上方法的時間和空間複雜度均為(V N).
2．基于減治法思想實作二叉查找樹的插入與查找
2.1 、二叉查找樹的插入與查找的僞代碼描述
算法：find(v)
//查找二叉樹中的資料
//輸入資料
//輸出：找到資料列印出資料，否則顯示無資料
While a!=b do
If a<b c←c.leftchild //如果資料比根節點資料小，則将目前的根節點指派左孩子
Else c←c.rightchild
Return c
算法：insert(treenode)
//向二叉樹插入資料
//輸入要插入的值
//輸出插入結束後的二叉樹
Current ←null ,parent←null a←1
If root==null
Root=newnode
Else
Current=root
While a do
If b<c
current←current.leftchild //目前節點的左孩子指派給目前節點。目前節點指向左子樹
if current==null
parament.leftchild←b //将新節點插入到左子樹的空位置
else
current←current.rightchild
if current==null
parament.rightchild←b //将新節點插入到右子樹的空位置 2.2、二叉查找樹的插入與查找的源代碼實作
package com.find.insert;
class TreeNode{
int value;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode() {
}
public TreeNode(int value) {
this.value = value;
leftChild = null;
rightChild = null;
}
public String toString() {
return "Node [value=" + value +"]";
}
}
package com.find.insert;
import java.util.LinkedList;
import java.util.Queue;
class Tree {
TreeNode root = null;
// 查找資料，找到資料列印出該節點
/**
* 查找原理：
* 1、查找的資料和根節點的數值比較。相等傳回根節點。
* 2、小于根節點進入左子樹查找
* 3、大于根節點進入右子樹查找
* 4、左右子樹都查找不到傳回空值
*
*/
public TreeNode find(int value) {
TreeNode current = root; //把根節點的值指派給目前指向
while (current.value != value) {
if (value < current.value)
current = current.leftChild;
else
current = current.rightChild;
if (current == null)
System.out.println("目前的二叉樹沒有此數值！！！");
}
return current;
}
public void insert(TreeNode treenode) {
if (root == null) {
root = treenode;
} else {
TreeNode current = root;
TreeNode parent;
while (true) {
while (true) {
parent = current;//父節點
if (treenode.value < parent.value) {
current = current.leftChild;
if (current == null) {
parent.leftChild = treenode;
return;
}
} else {
current = current.rightChild;
if (current == null) {
parent.rightChild = treenode;
return;
}
}
}
}
}
}
public void levelOrderByStack() {
System.out.println("采用層次周遊二叉樹：");
if (root == null)
return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (queue.size() != 0) {
int len = queue.size();
for (int i = 0; i < len; i++) {
TreeNode temp = queue.poll();// 出隊列
System.out.print(temp.value + " ");// 輸出出隊列的值
if (temp.leftChild != null)
queue.add(temp.leftChild);
if (temp.rightChild != null)
queue.add(temp.rightChild);
}
}
}
}
package com.find.insert;
public class TreeDemo {
public static void main(String[] args) {
Tree tree = new Tree();
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(1);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
tree.insert(node1);
tree.insert(node2);
tree.insert(node3);
tree.insert(node4);
tree.insert(node5);
tree.insert(node6);
//查找
System.out.println(tree.find(3));
//層次周遊
tree.levelOrderByStack();
System.out.println();
//插入資料
TreeNode node7 = new TreeNode(7);
tree.insert(node7);
//層次周遊
tree.levelOrderByStack();
} 2.3、叉查找樹的插入與查找的時間效率分析
在建構二叉搜尋樹時，如果插入元素有序或接近有序，如 1 2 3 4 5 6，二叉搜尋樹退化成為一顆單支樹，此時查找的時間複雜度為O(N)，此時插入的效率也是O(N)；如果左右子樹都存在，存在葉子結點，查找的效率和插入的效率是二叉樹的高度。
3、測試結果
3.1、基于減治法思想實作二叉查找樹的插入與查找的測試用例結果截圖
