递归相关知识2
递归相关知识2多路递归--斐波那契额数列
import java.util.Arrays;
//递归求斐波那契第n项
public class feibonaqie {
public static int fibonacci(int n){
int []cache=new int;
Arrays.fill(cache,-1);
cache=0;
cache=1;//
return f(n,cache);
}
public static int f(int n,int[]cache){
/* if(n==0){
return 0;
}
if(n==1){
return 1;
}*/
if(cache!=-1){
return cache;
}
int x=f(n-1,cache);
int y=f(n-2,cache);
cache=x+y;
return cache;
}
/*public static void main(String[] args) {
int f=f(8);
System.out.println(f);
}*/
}汉诺塔问题
import java.util.LinkedList;
public class hannuota {
static LinkedList<Integer> a=new LinkedList<>();//三根柱子
static LinkedList<Integer> b=new LinkedList<>();
static LinkedList<Integer> c=new LinkedList<>();
//3 2 1
static void init(int n){
for(int i=n;i>=1;i--){
a.addLast(i);
}
}
/*
Params:n-圆席个数
a-源
b-信
c-目
*/
static void move(int n,LinkedList<Integer> a,LinkedList<Integer> b,
LinkedList<Integer> c){
if(n==0){
return;
}
move(n-1,a,c,b);
c.addLast(a.removeLast());//中间
print();
move(n-1,b,a,c);
}
public static void main(String[]args){
init(3);
/*System.out.println(a);
System.out.println(b);
System.out.println(c);
b.addLast(a.removeLast());*/
print();
move(3,a,b,c);
}
private static void print() {
System.out.println("----------------------");
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}爆栈问题
//递归求和n+n-1+...+1
public class baozhan {
//f(n)=f(n-2)+n;
public static long sum(long n){
if(n==1){
return 1;
}
return sum(n-1)+n;
}
public static void main(String[] args) {
/* System.out.println(sum(15000));*///爆栈
}
}杨辉三角
第一种,时间复杂度最高,空间复杂度最高
public class yanghuisanjiao {
private static int element(int i,int j){
if(j==0||i==j){
return 1;
}
return element(i-1,j-1)+element(i-1,j);
}
private static void printSpace(int n,int i){
int num=(n-1-i)*2;
for (int j = 0; j < num; j++) {
System.out.print(" ");
}
}
public static void print(int n){
for (int i = 0; i < n; i++) {
printSpace(n,i);
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d",element(i,j));
}
System.out.println();
}
}
public static void main(String[] args) {
/*System.out.println(element(4,2));*/
print(5);
}
}数据结构素数实现
public class yanghuisanjiao1 {
/*
优化1·使用二组数组记忆法
Params:triangle-二维数组
i-行坐标
j-列坐标
Returns:该坐标元素值
*/
private static int element1(int[][]triangle,int i,int j){
if(triangle>0){
return triangle;
}
if(j==0||i==j){
triangle=1;
return 1;
}
triangle=element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
return triangle;
}
private static void printSpace(int n,int i){
int num=(n-1-i)*2;
for (int j = 0; j < num; j++) {
System.out.print(" ");
}
}
public static void print(int n){
int[][]triangle=new int[];
for (int i = 0; i < n; i++) {//行
triangle=new int;
/* printSpace(n,i);*/
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d",element1(triangle,i,j));
}
System.out.println();
}
}
public static void main(String[] args) {
/*System.out.println(element(4,2));*/
print(5);
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]