递归相关知识2
多路递归--斐波那契额数列
import java.util.Arrays;
//递归求斐波那契第n项
public class feibonaqie {
public static int fibonacci(int n){
int []cache=new int[n+1];
Arrays.fill(cache,-1);
cache[0]=0;
cache[1]=1;//[0,1,-1,-1,-1,-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[n]!=-1){
return cache[n];
}
int x=f(n-1,cache);
int y=f(n-2,cache);
cache[n]=x+y;
return cache[n];
}
/*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[i][j]>0){
return triangle[i][j];
}
if(j==0||i==j){
triangle[i][j]=1;
return 1;
}
triangle[i][j]=element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
return triangle[i][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){
int[][]triangle=new int[n][];
for (int i = 0; i < n; i++) {//行
triangle[i]=new int[i+1];
/* 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);
}
}
时间复杂度,空间复杂度同时提升
public class yanghuisanjiao2 {
/*
优化2·使用二组数组记忆法
Params:triangle-二维数组
i-行坐标
j-列坐标
Returns:该坐标元素值
*/
//动态规划--注意:还可以透过每一行的前一项计算半下一项,不必借助上一行,这与杨辉三角的另一个特性有关,
/* private static int element1(int[][]triangle,int i,int j){
if(triangle[i][j]>0){
return triangle[i][j];
}
if(j==0||i==j){
triangle[i][j]=1;
return 1;
}
triangle[i][j]=element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
return triangle[i][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 print2(int n){
int[]row=new int[n];
for (int i = 0; i < n; i++) {//行
/* triangle[i]=new int[i+1];*/
/* printSpace(n,i);*/
createRow(row,i);
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d",row[j]);
}
System.out.println();
}
}
private static void createRow(int[]row,int i){
if(i==0){
row[0]=1;
return;
}
for (int j = i; j >0 ; j--) {
row[j]=row[j]+row[j-1];
}
}
public static void main(String[] args) {
/* System.out.println(element(4,2));*/
print2(5);
}
}
数据结构素数实现
class FuShu{
int real; //实部real、虚部image;
int image;
FuShu(int real, int image) { //构造方法:赋初值;
this.real = real;
this.image = image;
}
FuShu add(FuShu s1) { // 加法运算 FuShu add(FuShu s1);
FuShu tmp = new FuShu(real + s1.real, image + s1.image);
return tmp;
}
}
public class xubu {
public static void main(String[] args) { //两个复数相加,输出结果
FuShu s1 = new FuShu(1, 2);
FuShu s2 = new FuShu(2, 3);
FuShu s3 = s2.add(s1);
System.out.println(s3.real + " + " + s3.image + "i");
}
}
标签:triangle,递归,int,void,知识,return,static,相关,public
From: https://www.cnblogs.com/cgy-chen/p/17554984.html