最近在某IT社区看到一个问题，说算法是他目前见过最难的一门课程....
然而我个人见解，当然我也回复了他，算法的原理不难，想把它描述清楚就很难
所以，我还是以竞赛题目来助你们来理解它
比如:
<!--第一题_全排列-->
方式一:
public class Main {
public static void main(String[] args) {
int[] A={1,2,3};
dfs(A,0);
}
public static void swap(int[] A,int i,int j){
int t=A[i];
A[i]=A[j];
A[j]=t;
}
public static void dfs(int[] A,int step){
if(step==A.length){
for(int i=0;i<A.length;i++){
System.out.print(A[i]+" ");
}
System.out.println();
return;
}
for(int i=step;i<A.length;i++){
swap(A,i,step);
dfs(A,step+1);
swap(A,i,step);
}
}
}
方式二:
import java.util.Scanner;
public class Main {
static int[] book=new int[1000];
static int[] a=new int[1000];
static int n;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
dfs(1);
}
public static void dfs(int step){
if(n+1==step){
for(int i=1;i<=n;i++){
System.out.print(a[i]+" ");
}
System.out.println();
return;
}
for(int i=1;i<=n;i++){
if(book[i]==0){
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
}
}
再来一题，加深印象
<!--第二题:
B DEF
A + --- + ------- = 10
C GHI
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？-->
方式一:
public class Main {
static int[] book=new int[10];
static int[] a=new int[10];
static int count=0;
public static void main(String[] args) {
int[] A={1,2,3,4,5,6,7,8,9};
dfs(A,0);
System.out.println(count);
}
public static void swap(int[] A,int i,int j){
int t=A[i];
A[i]=A[j];
A[j]=t;
}
public static boolean check(int[] A){
int a=A[0]*A[2]*(A[6]*100+A[7]*10+A[8]);
int b=A[1]*(A[6]*100+A[7]*10+A[8]);
int c=A[2]*(A[3]*100+A[4]*10+A[5]);
if(a+b+c==10*A[2]*(A[6]*100+A[7]*10+A[8])){
return true;
}
return false;
}
public static int dfs(int[] A,int step){
if(step==A.length){
if(check(A)){
count++;
}
}else{
for(int i=step;i<A.length;i++){
swap(A,i,step);
dfs(A,step+1);
swap(A,i,step);
}
}
return count;
}
}
方式二:
public class Main {
static int[] book=new int[50];
static int[] a=new int[50];
static int count=0;
public static void main(String[] args) {
dfs(0);
System.out.println(count);
}
public static boolean check(int[] A){
int a=A[0]*A[2]*(A[6]*100+A[7]*10+A[8]);
int b=A[1]*(A[6]*100+A[7]*10+A[8]);
int c=A[2]*(A[3]*100+A[4]*10+A[5]);
if(a+b+c==10*A[2]*(A[6]*100+A[7]*10+A[8])){
return true;
}
return false;
}
public static void dfs(int step){
if(step==9){
if(check(a)){
count++;
}
}else{
for(int i=1;i<=9;i++){
if(book[i]==0){
book[i]=1;
a[step]=i;
dfs(step+1);
book[i]=0;
}
}
}
}
}