目录
前言
第一章 概述
一、算法复杂度
二、汉诺塔问题
1、描述
2、实现代码
3、结果
4、时间复杂度
三、判断素数
1、描述
2、实现代码
3、结果
4、时间复杂度
四、判断回文
1、描述
2、实现代码
3、结果
4、时间复杂度
第二章 递归算法设计技术
一、递归
1、描述
2、总结
二、二叉树
1、描述
2、实现二叉树
3、结果
三、复制二叉树
1、描述
2、代码实现
3、结果
四、二叉树节点之和
1、描述
2、代码实现
3、结果
五、N皇后问题
1、描述
2、代码实现
3、结果
六、递归求字符个数
1、描述
2、实现代码
3、结果
七、非递归二叉树
1、描述
2、代码实现
3、结果
前言
本文是用来记录在大三下学期学习《算法设计与分析》这门课时，根据老师布置的作业，用java实现的算法代码。本文仅供学习交流使用，侵删。
第一章 概述
一、算法复杂度
计算复杂度主要是找到程序的运行关系
计算复杂度主要是找到程序的运行关系
详细的内容可见该博客一文讲透算法中的时间复杂度和空间复杂度https://www.cnblogs.com/lonely-wolf/p/15674526.html
二、汉诺塔问题
1、描述
2、实现代码
public class HanioTest {
public static void main(String[] args) throws IOException {
System.out.println("请输入盘子数：");
Scanner scanner = new Scanner(System.in);
int i = scanner.nextInt();
hanio(i,'a','b','c');
}
public static void hanio(int n ,char a,char b,char c) throws IOException {
if (n == 1){
move(n,a,c);
}else {
hanio(n-1,a,c,b);
move(n,a,c);
hanio(n-1,b,a,c);
}
}
public static void move(int n,char a,char b) throws IOException {
File file = new File("src/com/fayoung/ach/date2_28/hanio/output.txt");
if (file.exists()){
file.createNewFile();
}
FileWriter fw = new FileWriter("src/com/fayoung/ach/date2_28/hanio/output.txt", true);
PrintWriter pw = new PrintWriter(fw);
pw.println("把第"+n+"个盘子从"+a+"移到"+b);
pw.flush();
}
}
3、结果
4、时间复杂度
设盘子个数为n时，需要T（n)步，把A柱子n-1个盘子移到B柱子，需要T（n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T（n-1)步。
得递推公式T（n）=2T（n-1)+1
所以汉诺塔问题的时间复杂度为O(2^n);
三、判断素数 1、描述
判断一个大于2的正整数n是否为素数的方法有很多中，给出两种算法，说明其中哪种算法更好的理由。
2、实现代码
public class isPrimeNumber {
public static void main(String[] args) {
System.out.println("请输入一个大于2的正整数：");
Scanner scanner1 = new Scanner(System.in);
int x = scanner1.nextInt();
if (isPrimeNumber.way1(x))
System.out.println("使用方法1判断结果为：" + x + "是一个素数");
else
System.out.println("使用方法1判断结果为" + x + "不是一个素数");
if (isPrimeNumber.way2(x))
System.out.println("使用方法2判断结果为：" + x + "是一个素数");
else
System.out.println("使用方法2判断结果为" + x + "不是一个素数");
if (isPrimeNumber.way3(x,2))
System.out.println("使用方法3判断结果为：" + x + "是一个素数");
else
System.out.println("使用方法3判断结果为" + x + "不是一个素数");
}
//将n与[1,n-1]相取余，判断是否为0。如果为0则表示可以整除，该数就部署素数。反之就是素数
public static boolean way1(int n) {
Boolean flag = true;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
flag = false;
break;
} else
flag = true;
}
return flag;
}
//将n与[1,根号n]相取余，判断是否为0。如果为0则表示可以整除，该数就部署素数。反之就是素数
public static boolean way2(int n) {
Boolean flag = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
flag = false;
break;
} else
flag = true;
}
return flag;
}
//用递归的方式处理，终止条件为取余为0
public static boolean way3(int n ,int i){
if(i==n) return true;
if (n%i==0) return false;
return way3(n,++i);
}
}
3、结果
4、时间复杂度
方法一为O(n)；方法二为O（根号n)；方法三为O(n)
四、判断回文 1、描述
一个字符串采用string对象存储，设计一个算法判断该字符串是否为回文。
2、实现代码public class isPalinDrome {
public static void main(String[] args) {
System.out.println("请输入一个字符串：");
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
if (fun1(s))
System.out.println("使用方法1判断结果为：" + s + "是回文");
else
System.out.println("使用方法1判断结果为：" + s + "不是回文");
if (fun2(s,0,s.length()))
System.out.println("使用方法2判断结果为：" + s + "是回文");
else
System.out.println("使用方法2判断结果为：" + s + "不是回文");
}
//将该字符串先转成字符数组s1，然后复制该该字符数组s2。将s2和s1反向对比，判断回文
public static boolean fun1(String s) {
Boolean flag = true;
char[] s1 = s.toCharArray();
char[] s2 = new char[s1.length];
int n=s1.length;
for (int i = 0; i
3、结果
4、时间复杂度
方法一：O(n)；方法二：O(n)；
第二章 递归算法设计技术
一、递归
1、描述
递归（英语：recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。
2、总结
递归是将站在全局，将大问题转化成小问题，主要是要找到递归关系式。
二、二叉树
1、描述
基础知识可见此博客数据结构与算法——二叉树基础https://xiaozhuanlan.com/topic/7189032546
2、实现二叉树
treeNode
//用类去实现数据结构
public class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char x){
val =x;
}
}
TreeNodeUtil
public class TreeNodeUtil {
public static TreeNode arrayToTreeNode(char[] array){
if(array.length == 0){
return null;
}
TreeNode root = new TreeNode(array[0]);
Queue queue = new linkedList();
queue.add(root);
boolean isLeft = true;
for(int i = 1; i < array.length; i++){
TreeNode node = queue.peek();
if(isLeft){
if(array[i] != '0'){
node.left = new TreeNode(array[i]);
queue.offer(node.left);
}
isLeft = false;
}else {
if(array[i] != '0'){
node.right = new TreeNode(array[i]);
queue.offer(node.right);
}
queue.poll();
isLeft = true;
}
}
return root;
}
}
TreeNodeShow
public class TreeNodeShow {
private static int getTreeDepth(TreeNode root){
return root == null ? 0 : (1+ Math.max(getTreeDepth((root.left)), getTreeDepth(root.right)));
}
private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.val);
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的""与右儿子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(TreeNode root) {
if (root == null){
System.out.println("EMPTY!");
return;
}
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i++) {
for (int j = 0; j < arrayWidth; j++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth / 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
test
public class Test {
public static void main(String[] args) {
System.out.println("请输入二叉树：");
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
char[] s1 = s.toCharArray();
TreeNode q = TreeNodeUtil.arrayToTreeNode(s1);
TreeNodeShow.show(q);
}
}
3、结果
三、复制二叉树
1、描述
给定一个二叉树，复制该二叉树
2、代码实现
class TreeNode{
int val=0;
TreeNode left;
TreeNode right;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
public class CopyBT {
public TreeNode copyTree(TreeNode root){
TreeNode copyRoot = new TreeNode();
if (root!=null){
copyRoot.setVal(root.getVal());
copyRoot.setLeft(root.getLeft());
copyRoot.setRight(root.getRight());
}
return copyRoot;
}
public static void main(String[] args) {
TreeNode root = new TreeNode();
TreeNode left = new TreeNode();
TreeNode right = new TreeNode();
TreeNode node = new TreeNode();
root.setVal(1);
right.setVal(2);
left.setVal(3);
node.setVal(4);
root.setRight(right);
root.setLeft(left);
root.getLeft().setLeft(node);
TreeNode copy1 = new CopyBT().copyTree(root);
System.out.println("原来的树："+ root.getVal()+" "+left.getVal()+" "+right.getVal()+" "+left.left.getVal());
System.out.println("复制后的树："+copy1.getVal()+" "+copy1.getLeft().getVal()+" "+copy1.getRight().getVal()+
" "+copy1.getLeft().getLeft().getVal());
}
}
3、结果
四、二叉树节点之和
1、描述
给定一个字节类型为Int的二叉树，计算该二叉树各节点之和。
2、代码实现
public class SumBTNode {
public static void main(String[] args) {
BTNode root = new BTNode();
BTNode right = new BTNode();
BTNode left = new BTNode();
root.setVal(1);
right.setVal(5);
left.setVal(3);
root.setRight(right);
root.setLeft(left);
int sumBTNode = new SumBTNode().Sum(root);
System.out.println("二叉树："+root.getVal()+" "+left.getVal()+" "+right.getVal());
System.out.println("节点之和为："+sumBTNode);
}
public int Sum(BTNode root) {
if (root != null)
return root.getVal() + Sum(root.getLeft()) + Sum(root.getRight());
return 0;
}
}
class BTNode{
int val;
BTNode left;
BTNode Right;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public BTNode getLeft() {
return left;
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getRight() {
return Right;
}
public void setRight(BTNode right) {
Right = right;
}
}
3、结果
五、N皇后问题
1、描述
N皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。给定一个整数n，返回所有不同的N皇后问题的解决方案。
2、代码实现
public class NQueen {
static int max=4;//有几个皇后
int[] array=new int[max];//用一维数组表示皇后所在的位置，值表示所在列，下标表示所在行
static int count=0;//解法的个数
public static void main(String[] args) {
NQueen q = new NQueen();
q.check(0);
System.out.println( max+"皇后问题的解法有" + count + "种");
}
private boolean judge( int n){ //判断放入第n个皇后是否冲突
for (int i = 0; i < n; i++) {
if (array[n] == array[i] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { //在同一列或者同一斜线
return false; //冲突
}
}
return true;
}
public void check ( int n){ //递归调用check
if (n == max) {
print();
count++;
return;
}
for (int i = 0; i < max; i++) {
array[n] = i;
if (judge(n)) {
check(n + 1);
}
}
}
private void print() { //打印n皇后的一种解法
for (int i = 0; i < max; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
3、结果
六、递归求字符个数
1、描述
对于一个采用字符数组存放的字符串str，设计一个递归算法求其字符个数（长度）
2、实现代码
public class CharLength {
public int length(String str,int i){
if (str ==null){
return 0;
}
if(i>= str.length())
return 0;
else {
return 1+length(str,++i);
}
}
public static void main(String[] args) {
String s = "hello world";
int length = new CharLength().length(s,0);
System.out.println(s+"的字符长度为："+length);
}
}
3、结果
七、非递归二叉树
1、描述
假设二叉树采用二叉链存储结构存放，节点值为Int类型，设计一个非递归算法求二叉树bt中所有叶子节点值大于等于k的节点个数。
2、代码实现
public class BinaryChainTree {
public static void main(String[] args) {
BinaryChainTree tree = new BinaryChainTree();
Node node = new Node();
node=tree.creat(1);
tree.add(node,2,true );
tree.add(node,3,false);
int k =2;
System.out.println("二叉树："+" "+tree.root.data+" "+tree.root.left.data+" "+tree.root.right.data);
System.out.println("该二叉树中大于等于"+k+"的节点个数为："+num(tree, k));
}
//二叉链树的节点，也就是域，每个节点都有三个域，分别为左、根、右
public static class Node{
Integer data;//用Inter类型是因为int无法判空
Node left;
Node right;
//无参构造，以可以new出来
public Node(){
}
//有参构造
public Node(int data){
this.data=data;
this.left=null;
this.right=null;
}
}
private Node root;
//根据提供的元素构造二叉树
public Node creat(Integer data){
return root = new Node(data);
}
//为指定节点添加子节点
public Node add(Node parent,int data,boolean isLeft){
//如果提供的节点为空，则不能添加子节点
if(parent==null||parent.data==null){
throw new RuntimeException("节点为空的不能添加子节点");
}
Node node=null;
if(isLeft){//如果要添加的是左子节点
if(parent.left!=null){
throw new RuntimeException("该节点的左子节点已经存在");
}else{
node=new Node(data);
parent.left=node;
}
}else{//否则添加的是右子节点
if(parent.right!=null){
throw new RuntimeException("该节点的右子节点已经存在");
}else{
node=new Node(data);
parent.right=node;
}
}
return node;
}
//采用非递归的方法进行遍历，统计大于k的节点的个数
public static int num(BinaryChainTree tree,int k) {
int num=0;//大于k的节点的个数
Stack stack = new Stack();
if (tree == null){//树为空，返回0
return 0;
}
stack.push(tree.root);//将树的根节点入栈
while (!stack.isEmpty()){//当栈不为空时
Node pop = stack.pop();//用一个变量Node表示出栈的根节点
if (pop!=null){//如果根节点不为空
if (pop.data>=k){//如果根节点的值大于k，则num++
num++;
}
stack.push(pop.right);//将根的右节点入栈
stack.push(pop.left);//将根的左节点入栈
}
}
return num;//返回个数
}
}
3、结果
