ITeye博客

lianggl2008的博客

lianggl2008 · 共 15 篇文章

回溯法求解 “n 皇后 问题”——Java 实现

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。 回溯算法描述: void Queue(int n) { for (i=1; i<=n; i++) //初始化 x[i]=0; k=1; while (k>=1) { x[k]=x[k]+1; //在下一列放置第k个皇后 while (x[k]<=n && !Place(k)) x[k]=x[k]+1; //搜索下一列 if (x[k]<=n && k= =n) { //得到一个解,…

2010-03-14 22:27 · 算法 · 评论(0)

贪心法和回溯法 求解“背包、0/1背包问题”——Java 实现

给定n种物品和一个容量为C的背包,物品i的重量是wi,其价值为vi,背包问题是如何选择装入背包的物品,使得装入背包中物品的总价值最大? 贪心算法描述: 1.改变数组w和v的排列顺序,使其按单位重量价值v[i]/w[i]降序排列; 2.将数组x[n]初始化为0; //初始化向量 3. i=1; 4.循环直到(w[i]>C); 4.1 x[i]=1; 4.2 C=C-w[i]; 4.3 i++; 5. x[i]=C/w[i]; KnapSack1.java //贪心算法 import java.util.*; public class KnapSack1 { public static void…

2010-03-14 22:25 · 算法 · 评论(3)

三种算法求最大子段和问题——Java实现

给定由n个整数组成的序列(a1, a2, …, an),求该序列的子段和的最大值,当所有整数均为负整数时,其最大子段和为0。 LargestSubsegmentSum1.java //蛮力算法 import java.util.*; public class LargestSubsegmentSum1 { public static void main(String[] args) { /** *从键盘输入所要求的序列的长度n */ Scanner in=new Scanner(System.in); System.out.println("Please enter the length o…

2010-03-14 22:21 · 算法 · 评论(0)

Comparable排序

import java.util.Arrays; public class User implements Comparable { private String id; private int age; public User(String id, int age) { this.id = id; this.age = age; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String getId() { return id; } public vo…

2010-03-14 22:05 · 评论(0)

适配器模式

public class Banner { private String string; public Banner(String string){ this.string=string; } public void showWithParen(){ System.out.println("("+string+")"); } public void showWithAster(){ System.out.println("*"+string+"*"); } } public interface Print { public abstract void printWeak(); public …

2010-03-14 22:01 · Java设计模式 · 评论(0)

简单递归算法

public class DiGuiAgri { public void binary_to_ascii(int value) { int quotient; quotient = value / 10; if( quotient != 0) { binary_to_ascii( quotient); } System.out.println(value % 10); } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub DiGuiAgri dg =…

2010-03-14 21:58 · 算法 · 评论(0)

自定义类加载器,实现动态更新DEMO

import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.util.HashSet; class CustomCL extends ClassLoader { private String basedir; // 需要该类加载器直接加载的类文件的基目录 private HashSet dynaclazns; // 需要由该类加载器直接加…

2010-03-14 21:54 · 评论(0)

深拷贝问题

public class CopyObject { /** * @param */ public static void main(String[] args) { // TODO Auto-generated method stub Professor p = new Professor("wangwu", 50); Student s1 = new Student("zhangsan", 18, p); Student s2 = (Student) s1.clone(); s2.p.name = "lisi"; s2.p.age = 30; System.out.println("nam…

2010-03-14 21:50 · 评论(0)

排列算法

import java.util.ArrayList; /** * 全排列算法 * */ public class Arrange { private int total = 0; private ArrayList<String> arrangeList = new ArrayList<String>(); public Arrange() { } private void swap(String list[], int k, int i) { String c3 = list[k]; list[k] = list[i]; list[i] = c3; } public void perm(…

2010-03-14 21:44 · 算法 · 评论(0)

观察者模式

public abstract class NumberGenerator { public Vector<Observer> observers = new Vector<Observer>();// 所有观察者信息将录入observers中 public void addObserver(Observer observer) { observers.add(observer); } public void deleteObserver(Observer observer) { observers.remove(observer); } public void notifyObserver…

2010-03-14 21:40 · Java设计模式 · 评论(0)

工厂方法模式

public abstract class Shape { public abstract void draw(); public abstract void erase(); public String name; public Shape(String aName) { name = aName; } } public class Circle extends Shape { @Override public void draw() { // TODO Auto-generated method stub System.out.println("It will draw a circle…

2010-03-14 21:35 · Java设计模式 · 评论(0)

排序查找问题

package com.strongit; public class PaiXu { private int[] data = {11,3,17,1,13,21,10,15,6,4}; public PaiXu() { print(); //quickSort(data,0,data.length-1); selectSort(data); int pos = binSearch(data,0,data.length-1,13); System.out.println("pos="+pos); } //快速排序 public void quickSort(int[] r,int s,int …

2010-03-14 21:27 · 算法 · 评论(0)

微软面试题:1、2、2、3、4、5,要求4不在第三位,3、5不能相连问题。

package com.strongit; import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.List; import java.util.regex.Pattern; public class Test { private String[] data = { "1", "2", "2", "3", "4", "5" }; private Collection<String> list = new HashSet<String>(); publ…

2010-03-14 21:23 · 算法 · 评论(0)

二叉树问题

package com.strongit; import java.util.LinkedList; import java.util.Queue; /** * H * / * D * / \ * B G * / \ / * A C F * / * E * * @author Administrator * */ public class ErChaShu { private char[] data = {'H','D','G','B','C','F','A','E'}; private TreeNode root; public TreeNode getRoot() { return ro…

2010-03-14 21:18 · 评论(0)

约瑟夫环问题

package com.strongit; /** * 用数组实现约瑟夫出圈问题,n个人排成一圈,从第一个开始报数,报到m的人出圈, 剩下的人继续开始从1报数,直到所有的人都出圈为止。对于给定的n,m, 求出所有的人出圈顺序 * @author Administrator * */ public class TestLink { private static final int m = 3; // private static final int n = 6; // 人数 public TestLink() { Node root = new Node(); root.data = -1; …

2010-03-14 21:09 · 评论(0)