资源描述
N皇后问题/*N皇后题目描述说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，* 1970年与1971年， E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。该题要求N皇后的放置结果共有多少种输入描述输入一个正整数N（N16）输出描述输出结果输入样例8输出样例92* * 1 * 2*/packagejava201211;import java.util.Scanner;/* author Administrator*/public class N皇后 static int n = 8; static int lie = new intn; static int count=0; static boolean canPlace(int k) boolean canPlace=true; for (int i = 0; i n-1) count+; else for (int i = 0; i n; i+) liem=i; if(canPlace(m) backtrack(m+1); /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here Scanner sc = new Scanner(System.in); n = sc.nextInt(); lie = new intn; backtrack(0); System.out.println(count); 24点/*二十四点题目描述问题描述：输入4个数，通过 加、减、乘、除运算看能否得到 结果 24，每个数只用一次，如果能输出 一种公式，输入描述输入四个正整数输出描述能通过某种方式得到24则输出1，不能则输出0输入样例6 6 6 6输出样例16+6+6+6* * * 0 1 2 3 4 5 6 * 0 1 2 3* * 1 2 3 4* 3 4 3 * 3 7 3 -1 * 10 10* * -4 -1* */package java201211;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/* author Administrator*/public class _24点2 static int data = 6, 6, 6, 6; static float s = 0; static String str = ; static List strList=new ArrayList(); static int count = 0; static String strii = ; static List list = new ArrayList(); static void search(List list) if (list.size() = 1) if(s=24) count+; /System.out.println(str); else for (int n = 0; n list.size()-1; n+) for (int i = n + 1; i list.size(); i+) List tlist = new ArrayList(); tlist.addAll(list); s = list.get(n) + list.get(i); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); tlist.clear(); tlist.addAll(list); s = list.get(n) - list.get(i); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); tlist.clear(); tlist.addAll(list); s = -list.get(n) + list.get(i); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); tlist.clear(); tlist.addAll(list); s = list.get(n) * list.get(i); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); tlist.clear(); tlist.addAll(list); s = list.get(n) / list.get(i); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); tlist.clear(); tlist.addAll(list); s = list.get(i)/list.get(n); tlist.remove(n); tlist.remove(i-1); tlist.add(s); search(tlist); /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here Scanner sc = new Scanner(System.in); for (int i = 0; i 0) /System.out.println(count); System.out.println(1); else System.out.println(0); 砝码组合/*用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。本题目要求编程实现：对用户输入的重量(1121)，给出砝码组合方案（用加减式表示，减代表砝码放在物品盘）。例如：输入：5输出：9-3-1输入：19输出：27-9+1* 类似0 1背包问题 回溯法*/package java201211;import java.util.Arrays;import java.util.Scanner;/* copyright 朱小波* author 朱小波 * date 2012-11-22 09:36:37*/public class famazuhe static int w = 0, 1, 3, 9, 27, 81; static int x = 0, 0, 0, 0, 0, 0; static int current = 0; public static void printResult() for (int j = x.length-1; j 0; j-) if(1=xj|2=xj) System.out.print(wj); for (int jj = j-1; jj 0; jj-) if(1=xjj) System.out.print(+wjj); if(2=xjj) System.out.print(-+wjj); break; public static void backtrack(int i, int n) if (i 5) if (current = n) printResult(); else if (current = n) printResult(); else /+砝码 xi = 1; current += wi; backtrack(i + 1, n); current -= wi; /-减砝码 xi = 2; current -= wi; backtrack(i + 1, n); current += wi; /不选 xi=0; backtrack(i+1,n); /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here Scanner sc= new Scanner(System.in); int n=sc.nextInt(); backtrack(1, n); 取石子/* 动态规划思想题目描述有一堆石子，A，B两人轮流从中取出石子，每次取出的石子数目只能为1，3，7或8，最后一枚石子谁取到就是输方。A,B两人都足够聪明，不会做出错误的判断。现给出一定数目的石子，A先取石子，计算A最终是输是赢，赢用1表示，输用0表示.输入描述第一行为一个整数n(0 n 100),表示玩n局，接下来n行每行有一个整数，表示对应的局提供的石子数（不大于10000），输出描述编程输出A对应的n局是赢是输，赢输出1，输输出0.输入样例31310输出样例001*测试数据512101118* 01110*/package java201211;import java.util.Scanner;/* copyright 朱小波* author 朱小波 * date 2012-11-23 07:37:17*/public class qushizhi3 /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int amount=new intn; int status=new int10000; int max=0; for (int j = 0; j amountj?max:amountj; status1=0; status2=1; status3=0; status4=1; status5=0; status6=1; status7=0; status8=1; for(int i=9;i=max;i+) statusi=0; if(0=statusi-1|0=statusi-3|0=statusi-7|0=statusi-8)/状态转移式 statusi=1; for (int i = 0; i 0; i-) t *= getLastThree(m); t = getLastThree(t); return t; static int getLastThree(int n) int t = n / 1000; return n - t * 1000; /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here List result = new ArrayList(); int x, y; Scanner sc = new Scanner(System.in); int n=sc.nextInt(); while (n0) x = sc.nextInt(); y = sc.nextInt(); result.add(powerr(x,y); n-; for (int object : result) System.out.println(object); 最大乘积/* 最大k乘积问题题目描述设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定的I和k ,求出I的最大k乘积.Input输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个n位十进制整数.（n=10）Output输出计算结果，第1行中的数是计算出的最大k乘积.输入描述输入的第1行中有2个正整数n和k.正整数n是序列的长度;正整数k是分割的段数.接下来的一行中是一个n位十进制整数.（nres?max:res; /System.out.println(res); else for(int j=i-1;j=1;j-)/左段i-1为数 res=res*(int)(Math.floor(x/Math.pow(10,j);/取整 duan+; divide(int)(x%Math.pow(10,j),j);/继续对右段进行划分 /回溯 duan-; res=1; /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here /divide(1569,4); Scanner sc = new Scanner(System.in); int len = sc.nextInt(); d=sc.nextInt(); int l=sc.nextInt(); /System.out.println(len+ +d+ +l); divide(l,len); System.out.println(max); /System.out.println(Math.floor(123/Math.pow(10, 2); 乒乓球赛/*乒乓球比赛题目描述两个乒乓球队进行比赛，各出三人。甲队为a，b，c三人，乙队为x，y，z三人。已抽签决定比赛名单。共三场比赛，所有队员必须参加比赛。有人向队员打听比赛的名单，a说他不和x比，c说他不和x，z比，请编程找出三场比赛赛手的名单。输入描述此题不需要输入输出描述假设a和y比，则输出a vs y严格按照上面的格式输出，不要有多余的文字叙述或符号，每场比赛输出占一行输入样例不需要输入输出样例a vs y*/package java201211;import java.util.Arrays;/* author Administrator*/public class 乒乓球赛 static int a = 1, 2, 3; static char abc = a, b, c; static int x = 1, 2, 3; static char xyz = x, y, z; static void swap(int aa, int bb) int temp = xaa; xaa = xbb; xbb = temp; static void perm(int n) /System.out.println(Arrays.toString(x); if (n 2) if (a0 != x0 & a2 != x0 & a2 != x2) for (int i = 0; i 3; i+) for (int j = 0; j 3; j+) if (ai = xj) System.out.println(abci + vs + xyzj); else for (int i = n ; i 3; i+) swap(i, n); perm(n + 1); swap(i, n); /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here perm(0); 全排列/*排列组合题目描述对字符串（数字，字母，符号）进行全排列，并统计全排列的种树输入描述输入一个字符串输出描述输出字符串的全排列，每种情况占一行，最后一行输出全排列的个数输入样例123输出样例1231322132313123216*/package java201211;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/* author Administrator*/public class 全排列 static String s = 12; static char ch = s.toCharArray(); static int count = 0; static List sl=new ArrayList(); static void backtrack(int n) if (n = ch.length) String temp=String.valueOf(ch); if(!is_has(temp) count+; sl.add(temp); System.out.println(temp); else for (int i = n; i ch.length; i+) exchange(n, i); backtrack(n + 1); exchange(n, i); static boolean is_has(String str) for (String s : sl) if(s.equals(str) return true; return false; static void exchange(int a, int b) char tem = cha; cha = chb; chb = tem; /* * param args the command line arguments */ public static void main(String args) / TODO code application logic here Scanner sc=new Scanner(System.in); s=sc.next(); ch = s.toCharArray(); backtrack(0); System.out.println(count); 8数码问题/*广度搜索Eight题目描述在3*3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字.棋盘中留有一个空格,空格用0来表示.空格周围的棋子可以移到空格中.要求解的问题是：给出一种初始布局和目标布局,为了使题目简单,设目标状态为:1 2 38 0 47 6 5找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变.输入描述输入初试状态,3*3的九个数字,空格用0表示.输出描述只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次(若无法到达目标状态则输出-1).输入样例2 8 31 0 47 6 5输出样例4* 利用奇偶性判断所给出的初始状态有无解.判别方法是：以数组为一维的举例子.将八数码的一个结点表示成一个数组a9，空格用0表示，设临时函数p(x)定义为：x数所在位置前面的数比x小的数的个数，其中0空格不算在之内，那设目标状态为b9，那r=sigma(p(x) sigma()表示取所有的x:1-8并求和，那对于初始状态a9，t=sigma(p(x)，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。*/package java201211;import java.util.Scanner;import java.util.Vector;/* copyright 朱小波* author 朱小波 * date 2012-11-26 06:19:58*/public class 八数码问题2 /static int endGrid = new int33; /static int startGrid = new int33; static Vector nodeList = new Vector(); static int startGrid = 2, 8, 3, 1, 0, 4, 7, 6, 5;/开始状态 static int endGrid = 1, 2, 3, 8, 0, 4, 7, 6, 5;/结束状态 static int qipan = new int9;/转换成一行 static int qipan2 = new int9; /* * param args the command line arguments */ public static void main(String args) int sum = 0; int start = 0; int end = 0; int m = 1, n = 1;/0的初始位置 while (sum 9) Scanner input = new Scanner(System.in); /System.out.println(请输入数据的初始状态！); for (int k = 1; k 4; k+) /System.out.print(请输入初始状态的第 + k + 行:); for (int j = 0; j 3; j+) if (input.hasNextInt() startGridk - 1j = input.nextInt(); if (startGridk - 1j = 0) m = k - 1; n = j; sum+; int i=0; for (int k = 0; k 3; k+) for (int j = 0; j 3; j+) qipani=startGridkj; qipan2i=endGridkj; start += small(i, qipan); end += small(i, qipan2); i+; /System.out.println(-); /System.out.println(请输入数据的终止状态！);/ for (int k = 1; k 4; k+) / /System.out.print(请输入终止状态的第 + k + 行:);/ for (int j = 0; j 3; j+) / if (input.hasNextInt()/ endGridk - 1j = input.nextInt();/ sum+;/ / if (sum 9) System.out.println(数据输入有误，重新运行并输入，注意：数字之间以空格间隔！); else break; / 初始化结束 /System.out.println(start+ +end); if (start % 2 = 0 & end % 2 = 0 | start % 2 != 0 & end % 2 != 0) /同奇数或者偶数有解 Node root = new Node(null, m, n, m, n, startGrid); Vector v = new Vector(); v.add(root); Node leaf = breathFirstSearch(v); System.out.println(leaf.depth - 1); else System.out.println(-1); / 显示结果：从终止节点向上直到根节点即初始节点/ int i = 0;/ while (leaf.father_node != null) / System.out.println(i + times:);/ leaf.display();/ leaf = leaf.father_node;/ i+;/ public static int small(int i, int qipan) int count = 0; for (int j = 0; j i; j+) if (qipanj qipani) count+; return count; public static Node depthFirstSearch(Node curNode) if (curNode.equalGrid(endGrid) return curNode; nodeList.add(curNode); curNode.setSons(nodeList, endGrid); Node sons = curNode.getSons(); if (sons = null) return null; for (int i = 0; i sons.length; i+) Node n = depthFirstSearch(sonsi); if (n != null) return n; return null; public static Node breathFirstSearch(Vector curNodes) Vector v = new Vector(); for (int i = 0; i curNodes.size(); i+) Node n = (Node) curNodes.elementAt(i); if (n.equalGrid(endGrid) return (Node) curNodes.elementAt(i); else nodeList.add(n); n.setSons(nodeList, endGrid); Node sons = n.getSons(); if (sons != null) for (int j = 0; j sons.length; j+) v.add(sonsj); return breathFirstSearch(v); class Node int depth; Node father_node; Node sons; int oldX, oldY, newX, newY; int grid = new int33; public Node(Node father, int oldX, int oldY, int newX, int newY, int grid) this.father_node = father; if (this.father_node != null) this.depth = this.father_node.depth + 1; else this.depth
展开阅读全文