A recursive algorithm is an algorithm that calls itself directly or indirectly. In computer programming, recursive algorithms are very effective in solving a large class of problems. It often makes the description of the algorithm concise and easy to understand.
Question 1: The rules for a column of numbers are as follows: 1, 1, 2, 3, 5, 8, 13, 21, 34. What is the 30th digit? Using recursion to implement
public class FibonacciSequence { public static void main(String[] args){ System.out.println(Fribonacci(9)); } public static int Fribonacci(int n){ if(n<=2) return 1; else return Fribonacci(n-1)+Fribonacci(n-2); } }
Question 2: Tower of Hanoi problem
The Tower of Hanoi (also known as the Tower of Hanoi) problem is actually an ancient legend in India.
Brahma, the god who created the world (a god similar to Pangu in China) left three diamond rods in a temple. The first one was covered with 64 round gold pieces, the largest one was at the bottom, and the rest one to one They are small and stacked one after another. The monks in the temple move them one by one from one stick to another. It is stipulated that the middle stick can be used as a help, but only one can be moved at a time. , and the big one cannot be placed on top of the small one. noodle. The calculation result is very scary (the number of times the disk is moved): 18446744073709551615. Even if the monks spend their entire lives, it is impossible to complete the movement of the gold disk.
Requirement: Enter a positive integer n, indicating that there are n disks on the first pillar. Output a sequence of operations in the format "move t from x to y". Each operation has one line, which means moving the disk numbered t on column x to column y. The columns are numbered A, B, and C. You need to transfer all the plates from column A to column C with the least amount of operations.
public class Hanio { public static void main(String[] args){ int i=3; char a ='A',b='B',c='C'; hanio(i,a,b,c); } public static void hanio(int n,char a,char b,char c){ if(n==1) System.out.println("移动"+n+"号盘子从"+a+"到"+c); else{ hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到c System.out.println("移动"+n+"号盘子从"+a+"到"+c);//紧接着直接把n搬动c hanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c } } }
The above is the analysis of the use of Java recursive algorithm. For more related content, please pay attention to the PHP Chinese website (m.sbmmt.com)!