参考代码:
import java.util.Scanner; public class zz摆动序列 { /** * @param args */ static int n; static boolean []is;//用于记录是否用过(保证每个数都是不相同的) static int []cz;//用于保存摆动序列 static int num=0;//用于记录摆动序列 public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); n=scanner.nextInt(); is=new boolean[n+1]; cz=new int[n+1]; dfs(1); System.out.println(num-n); } public static void dfs(int k) { if (k>n) { return; } //当只有1个和2个数的时候就不用考虑那么多,只要两个数不相等就行了 if (k==1||k==2) { for (int i = 1; i <= n; i++) { if (!is[i]) { is[i]=true; cz[k]=i; num++; dfs(k+1); //回溯 is[i]=false; cz[k]=0; } } } else { //当前一个数比前前一个数大的时候现在的这个数就要比前一个数小 if (cz[k-1]>cz[k-2]) { //这里范围就是1到前一个数(不能等于前一个数) for (int i = 1; i < cz[k-2]; i++) { if (!is[i]) { is[i]=true; cz[k]=i; num++; dfs(k+1); //回溯 is[i]=false; cz[k]=0; } } } //当前一个数比前前一个数小的时候现在的这个数就要比前一个数大 else if (cz[k-1]<cz[k-2]) { //所以范围是从前一个数(不能等于前一个数)到n for (int i = cz[k-2]+1; i <= n; i++) { if (!is[i]) { is[i]=true; cz[k]=i; num++; dfs(k+1); //回溯 is[i]=false; cz[k]=0; } } } } } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:662 |
大神老白 (C语言代码)浏览:611 |
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:636 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:675 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:512 |
成绩转换 (C语言代码)浏览:1008 |
A+B for Input-Output Practice (II) (C语言代码)浏览:1000 |
WU-复数求和 (C++代码)浏览:2015 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:327 |
1013题解浏览:561 |