回溯算法-N后问题和符号三角形java算法源程序.doc

实验报告10课程 数据结构与算法 实验名称 回溯法 第 页班级 11计本 学号 105032011130 姓名 风律澈 实验日期：2013年5月6日 报告退发 (订正 、 重做) 一、实验目的掌握回溯法的原理和应用。二、实验环境1、微型计算机一台 2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容 必做题：1、 编写程序，实现符号三角形问题算法。2、 编写程序，实现n后问题算法。四、实验步骤和结果(附上代码和程序运行结果截图)1. 符号三角形import java.util.Scanner;public class Triangles /* * param args */static int n,/第一行符号总数 half,/一半符号数量 count;/当前+号个数static int p;/符号三角数组static long sum;/已找到的符号三角数量public static void main(String args) / TODO Auto-generated method stubScanner in=new Scanner(System.in);int nn=in.nextInt();long result=compute(nn);System.out.println(result);private static long compute(int nn) / TODO Auto-generated method stub/类变量初始化n=nn;count=0;sum=0;half=n*(n+1)/2;if(half%2=1) return 0;/防止不合法输入half=half/2;p=new intn+1n+1;for(int i=0;i=n;i+)for(int j=0;jhalf)|(t*(t-1)/2-counthalf) return;if(tn) sum+;elsefor(int i=0;i2;i+)p1t=i;count+=i;for(int j=2;j=t;j+)/至上而下构造符号数组pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;backtrack(t+1);/对t以后的每一个执行上述操作/操作执行完成后恢复工作；for(int j=2;j=t;j+)count-=pjt-j+1;count-=i;2. N后问题import java.util.Scanner;public class nqueen /* * param args */static int n;/皇后个数static int x;/当前解，表示xi表示第i行皇后位置static long sum;/当前已找到的可行方案数public static void main(String args) / TODO Auto-generated method stubScanner in=new Scanner(System.in);int nn=in.nextInt();long result=nQueen(nn);System.out.println(result);private static long nQueen(int nn) / TODO Auto-generated method stub/初始化n=nn;sum=0;x=new intn+1;/尝试第一行的所有位置for(int i=0;in) sum+;elsefor(int i=1;i=n;i+)/从第一行开始往下放置，放置陈功继续xt=i;if(place(t)backtrack(t+1);private static boolean place(int t) / TODO Auto-generated method stubfor(int j=1;jt;j+)if(Math.abs(t-j)=Math.