精华内容
下载资源
问答
  • H(n) = 2*H(n-1)+1 (n>1) 那么我们很快就能得到H(n)的一般式: H(n) = 2^n - 1 (n>0) 2 解决方案 2.1 递归法 1 importjava.util.Scanner;2 3 public classHanoi {4 5 //使用递归法求解含有n个不同大小盘子的汉诺...

    1 问题描述

    Simulate the movement of the Towers of Hanoi Puzzle; Bonus is possible for using animation.

    e.g. if n = 2 ; A→B ; A→C ; B→C;

    if n = 3; A→C ; A→B ; C→B ; A→C ; B→A ; B→C ; A→C;

    翻译:模拟汉诺塔问题的移动规则;获得奖励的移动方法还是有可能的。

    相关经典题目延伸:

    引用自百度百科:

    有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子C上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动,设移动次数为H(n)。

    首先我们肯定是把上面n-1个盘子移动到柱子B上,然后把最大的一块放在C上,最后把B上的所有盘子移动到C上,由此我们得出表达式:

    H⑴ = 1          A—>C

    H(2) = 3         A—>B;A—>C;B—>C

    H(3) = 7         ...

    H(4) = 15

    ... ...

    H(n) = 2*H(n-1)+1 (n>1)

    那么我们很快就能得到H(n)的一般式:

    H(n) = 2^n - 1 (n>0)

    2 解决方案

    2.1 递归法

    1 importjava.util.Scanner;2

    3 public classHanoi {4

    5 //使用递归法求解含有n个不同大小盘子的汉诺塔移动路径,参数n为盘子数,把A塔上盘子全部移动到C塔上,B为过渡塔

    6 public static void recursionHanoi(int n,char A,char B,charC){7 if(n == 1){8 System.out.print(A+"——>"+C+"\n");9 }10 else{11 recursionHanoi(n-1,A,C,B); //使用递归先把A塔最上面的n-1个盘子移动到B塔上,C为过渡塔

    12 System.out.print(A+"——>"+C+"\n"); //把A塔中底下最大的圆盘,移动到C塔上

    13 recursionHanoi(n-1,B,A,C); //使用递归把B塔上n-1个盘子移动到C塔上,A为过渡塔

    14 }15 }16

    17 public static voidmain(String[] args){18 System.out.println("请输入盘子总数n:");19 Scanner in = newScanner(System.in);20 int n =in.nextInt();21 recursionHanoi(n,'A','B','C');22 }23 }

    运行结果:

    请输入盘子总数n:2A——>B

    A——>C

    B——>C

    请输入盘子总数n:3A——>C

    A——>B

    C——>B

    A——>C

    B——>A

    B——>C

    A——>C

    2.2 非递归法

    要使用非递归方法,首先要解决的核心问题就是找到汉诺塔的移动规律。现在问题是把n个盘子从A塔全部移动到C塔,那么先看看n = 2,3,4时,其具体盘子的移动路径结果(PS:移动路径前标号是指A塔上原有的第几个盘子,如(1)代表A塔上原有最上面的那个盘子,依次类推...):

    n = 2:

    (1)A—>B

    (2)A—>C

    (1)B—>C

    n= 3:

    (1)A——>C

    (2)A——>B

    (1)C——>B

    (3)A——>C

    (1)B——>A

    (2)B——>C

    (1)A——>C

    n= 4:

    (1)A——>B

    (2)A——>C

    (1)B——>C

    (3)A——>B

    (1)C——>A

    (2)C——>B

    (1)A——>B

    (4)A——>C

    (1)B——>C

    (2)B——>A

    (1)C——>A

    (3)B——>C

    (1)A——>B

    (2)A——>C

    (1)B——>C

    从上我们可以发现,n为偶数2,4时路径前标号为(1)的盘子移动路径依次为A——>B——>C,A——>B——>C——>A——>B——>C。n为偶数2,4时路径前标号为(2)的盘子移动路径依次为A—>C,A—>C——>B——>A—>C。而且发现n = 4其标号为(1)和标号为(3)的移动路径一模一样。n为奇数3时路径前标号为(1)和(2)的盘子移动路径依次为A——>C——>B——>A——>C,A——>B——>C。

    看到这里,我们可以大胆猜测盘子的具体移动路径与盘子的总个数的奇偶性以及盘子标号的奇偶性有关,而且移动的路径是固定又循环的。

    那么现在设定一个二维数组用来存放盘子下次移动的塔:

    char next = new char[2][3];

    二维数组中行char[0]代表数组下标为偶数的盘子下次要移动的塔

    二维数组中行char[1]代表数组下标为奇数的盘子下次要移动的塔

    二维数组重列char[0][0]代表盘子现在在A塔准备进行下次移动

    二维数组重列char[0][1]代表盘子现在在B塔准备进行下次移动

    二维数组重列char[0][2]代表盘子现在在C塔准备进行下次移动

    那么下面我们就来根据盘子现在所在塔,设定其下次移动的目的塔(PS:设共有n的盘子):

    if(n为偶数)

    {//数组下标为偶数的盘子移动目的塔,注意上面示例的标号为(1),其数组下标为0

    next[0][0] = ‘B’; //看n = 4的移动路径中(1)A——>B

    next[0][1] = ‘C’; //看n = 4的移动路径中(1)B——>C

    next[0][2] = ‘A’; //看n = 4的移动路径中(1)C——>A//数组下标为奇数的盘子移动目的塔

    next[1][0] = ‘C’; //看n = 4的移动路径中(2)A——>C

    next[1][1] = ‘A’; //看n = 4的移动路径中(2)B——>A

    next[1][0] = ‘B’; //看n = 4的移动路径中(2)C——>B

    }

    If(n为奇数)

    {//数组下标为偶数的盘子移动目的塔,注意上面示例的标号为(1),其数组下标为0

    Next[0][0] = ‘C’; //看n = 3的移动路径中(1)A——>C

    Next[0][1] = ‘A’; //看n = 3的移动路径中(1)B——>A

    Next[0][2] = ‘B’; //看n = 3的移动路径中(1)C——>B//数组下标为奇数的盘子移动目的塔

    Next[1][0] = ‘B’; //看n = 3的移动路径中(2)A——>B

    Next[1][1] = ‘C’; //看n = 3的移动路径中(2)B——>C

    Next[1][2] = ‘A’; //此处根据观察规律假设的

    }

    到这里,距离使用非递归法解决汉诺塔问题已经有头绪了,此处还有注意一点就是H(n) = 2^n - 1 (n>0),即移动n个盘子需要总次数为2^n - 1 ,即使用非递归法是需要进行循环2^n - 1 次。

    1 packagecom.liuzhen.ex2;2

    3 importjava.util.Scanner;4

    5 public classHanoi {6

    7 //使用递归法求解含有n个不同大小盘子的汉诺塔移动路径,参数n为盘子数,把A塔上盘子全部移动到C塔上,B为过渡塔

    8 public static void recursionHanoi(int n,char A,char B,charC){9 if(n == 1){10 System.out.print(A+"——>"+C+"\n");11 }12 else{13 recursionHanoi(n-1,A,C,B); //使用递归先把A塔最上面的n-1个盘子移动到B塔上,C为过渡塔

    14 System.out.print(A+"——>"+C+"\n"); //把A塔中底下最大的圆盘,移动到C塔上

    15 recursionHanoi(n-1,B,A,C); //使用递归把B塔上n-1个盘子移动到C塔上,A为过渡塔

    16 }17 }18

    19 public static void noRecursionHanoi(intn){20 if(n<=0){21 throw new IllegalArgumentException("n must be >=1");22 }23 char[] hanoiPlate = new char[n]; //记录n个盘子所在的汉诺塔(hanoiPlate[1]='A'意味着第二个盘子现在在A上)

    24 char[][] next = new char [2][3]; //盘子下次会移动到的盘子的可能性分类

    25 int[] index = new int[n];26

    27 //根据奇偶性将盘子分为两类

    28 for(int i=0;i

    35 //一开始所有盘子都在A上

    36 for(int i=0;i

    40 //n的奇偶性对移动方式的影响

    41 if(n%2==0){42 //数组下标为偶数的盘子移动目的塔,注意上面示例的标号为(1),其数组下标为0

    43 next[0][0]='B';44 next[0][1]='C';45 next[0][2]='A';46 //数组下标为奇数的盘子移动目的塔

    47 next[1][0]='C';48 next[1][1]='A';49 next[1][2]='B';50 }51 else

    52 {53 //数组下标为偶数的盘子移动目的塔,注意上面示例的标号为(1),其数组下标为0

    54 next[0][0]='C';55 next[0][1]='A';56 next[0][2]='B';57 //数组下标为奇数的盘子移动目的塔

    58 next[1][0]='B';59 next[1][1]='C';60 next[1][2]='A';61 }62

    63 //开始移动

    64 for(int i=1;i

    65 int m=0; //m代表第m块盘子hanoiPlate[m]66

    67 //根据步骤数i来判断移动哪块盘子以及如何移动

    68 for(int j=i;j>0;j=j/2){69 if(j%2!=0){ //此步骤光看代码代码有点抽象,建议手动写一下n = 2时的具体移动路径的j、m值变化

    70 System.out.println("("+(m+1)+")"+hanoiPlate[m]+"->"+next[index[m]][hanoiPlate[m]-'A']);71 hanoiPlate[m]=next[index[m]][hanoiPlate[m]-'A'];72 break; //移动盘子后则退出这层循环

    73 }74 m++;75 }76 }77 }78

    79 public static voidmain(String[] args){80 System.out.println("请输入盘子总数n:");81 Scanner in = newScanner(System.in);82 int n =in.nextInt();83 recursionHanoi(n,'A','B','C');84 System.out.println("非递归法结果:");85 noRecursionHanoi(n);86 System.out.println();87 }88 }

    运行结果:

    请输入盘子总数n:2A——>B

    A——>C

    B——>C

    非递归法结果:

    (1)A->B

    (2)A->C

    (1)B->C

    请输入盘子总数n:3A——>C

    A——>B

    C——>B

    A——>C

    B——>A

    B——>C

    A——>C

    非递归法结果:

    (1)A->C

    (2)A->B

    (1)C->B

    (3)A->C

    (1)B->A

    (2)B->C

    (1)A->C

    参考资料:

    展开全文
  • java递归算法详解

    2021-02-28 18:20:09
    Java中的递归算法虽然简单,但想要精通也是有着一定的难度的,本篇文章我们就来详细了解下递归算法。什么是递归?一般的说, 递归算法是一种直接或间接地调用自身的算法。在程序中,递归算法能够使算法的描述简洁而且...

    Java中的递归算法虽然简单,但想要精通也是有着一定的难度的,本篇文章我们就来详细了解下递归算法。

    什么是递归?

    一般的说, 递归算法是一种直接或间接地调用自身的算法。在程序中,递归算法能够使算法的描述简洁而且易于理解。

    递归分几类?

    递归通常分为两类,直接递归和间接递归:

    1、直接递归称为方法自身调用自己。

    2、间接递归可以A方法调用B方法,B方法调用C方法,C方法调用A方法。

    递归怎么实现实现?

    例://递归实现九九乘法表

    public class diguidemo

    {

    public static void main(String[] args)

    {

    digui(9);

    }

    private static void digui(int i)

    {

    if (i == 1)

    {

    System.out.println("1*1=1");

    }

    else

    {

    digui(i - 1);

    for (int j = 1; j <= 1; j++)

    {

    System.out.print(j + "*" + i + "=" + j * i + " ");

    }

    }

    }

    }

    //递归求和

    public class diguiqiuhe

    {

    public static void main(String[] args)

    {

    int num = 5;

    int sum = getSum(num);

    System.out.println(sum);

    }

    private static int getSum(int num)

    {

    if (num == 1)

    {

    return 1;

    }

    return num + getSum(num - 1);

    }

    }

    以上就是本篇文章的所有内容,更多详细java入门敬请关注奇Q工具网了解详情。

    推荐阅读:

    展开全文
  • 整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式:n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,.....

    整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式:

    n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分。

    如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

    例如但n=4时,他有5个划分,{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

    注意4=1+3 和 4=3+1被认为是同一个划分。

    该问题是求出n的所有划分个数,即f(n, n)。下面我们考虑求f(n,m)的方法;

    1.递归法:

    根据n和m的关系,考虑以下几种情况:

    (1)当n=1时,不论m的值为多少(m>0),只有一种划分即{1};

    (2)当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,...,1};

    (3)当n=m时,根据划分中是否包含n,可以分为两种情况:

    (a)划分中包含n的情况,只有一个即{n};

    (b)划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。

    因此 f(n,n) =1 + f(n,n-1);

    (4)当n

    (5)但n>m时,根据划分中是否包含最大值m,可以分为两种情况:

    (a)划分中包含m的情况,即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m,因此这情况下

    为f(n-m,m)

    (b)划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);

    因此 f(n, m) = f(n-m, m)+f(n,m-1);

    综上所述:

    f(n, m)=   1;              (n=1 or m=1)

    f(n,m)   =    f(n, n);                   (n

    1+ f(n, m-1);              (n=m)

    f(n-m,m)+f(n,m-1);         (n>m)

    #include

    using namespace std;

    int equationCount(int n,int m)

    {

    if(n==1||m==1)

    return 1;

    else if(n

    return equationCount(n,n);

    else if(n==m)

    return 1+equationCount(n,n-1);

    else

    return equationCount(n,m-1)+equationCount(n-m,m);

    }

    int main(void)

    {

    int n;

    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))

    {

    printf("%d\n",equationCount(n,n));

    }

    return 0;

    }

    展开全文
  • 详解Java递归法实现反转链表(LeetCode 206. 反转链表) /* * 示例: * 输入: 1->2->3->4->5->NULL * 输出: 5->4->3->2->1->NULL * * 链接:...

    详解Java递归法实现反转链表(LeetCode 206. 反转链表)

    /*
     * 示例:
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     * 
     * 链接:https://leetcode-cn.com/problems/reverse-linked-list/
     */
    
    // ListNode的数据结构
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {this.val = val;}
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    
    public class Solution {
    
        // 单链表反转
        public ListNode reverseList(ListNode head) {
            // 递归:
            // node1 -> node2 -> node3 -> node4 -> node5  // 先递归到最内层,并return head, return 后 head 位于 node4
            // node1 -> node2 -> node3 -> node4 <- node5  // node4.next.next = node4, 即node5.next = node4; node4.next = null
            // node1 -> node2 -> node3 <- node4 <- node5  // node3.next.next = node3, 即node4.next = node3; node3.next = null
            // node1 -> node2 <- node3 <- node4 <- node5  // node2.next.next = node2, 即node3.next = node2; node2.next = null
            // node1 <- node2 <- node3 <- node4 <- node5  // node1.next.next = node1, 即node2.next = node1; node1.next = null
            // 此时,node1 成为尾结点, 递归结束
    
            if (head == null || head.next == null) { // 为什么需要这两个判断呢?
                return head;
            }
            ListNode headNode = reverseList(head.next); // 递归到最内层,由内往外,由后往前 计算
            head.next.next = head;  // 因为这里需要 head.next == null 的判断
            head.next = null;       // 因为这里需要 head == null 的判断
            return headNode;
        }
    }
    
    展开全文
  • java 递归详解

    2021-02-12 21:52:13
    递归算法是一种直接或间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解.递归的分类:递归分为两种,直接递归和间接递归。直接递归称为方法自身...
  • Java实现折半查找(二分查找)的递归和非递归算法转 : http://wintys.blog.51cto.com/425414/94051/***名称:BinarySearch*功能:实现了折半查找(二分查找)的递归和非递归算法.*说明:* 1、要求所查找的数组已有序,...
  • 展开全部一、递归算法基本思路:Java递归算法是基于Java语言实现的递归算法。递归算法是一e5a48de588b662616964757a686964616f31333363373166种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成...
  • */ //折半查找非递归算法 //查询成功返回该对象的下标序号,失败时返回-1。 int BiSearch(int r[],int n,int k) { int low=0; int high=n-1; while(low) { int mid=(low+high)/2; if(r[mid]==k) return mid; else ...
  • Java递归实现全排列

    2021-03-10 06:14:46
    最近整理之前自己学习...递归算法:将数据分为两部分,递归将数据从左侧移右侧实现全排列package interview;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class FullSort {...
  • Java递归法求n个元素的全排列

    千次阅读 2021-01-16 10:17:41
    public class h { //k表示当前的交换位置。 public static void f(char[] data,int k){ if(k==data.length){ for(int i=0;i<data.length;i++){ System.out.print((data[i]+" "));... } System.out.println();...
  • 递归与泛型

    2021-03-15 13:06:35
    递归的本质是将一个大问题分解为一个简单的小问题然后逐步推进,比如说将1234打印出4,3,2,1的顺序,那么本质上就是n%10,可以将1234分解不断除以十,得到四个 个位数。递归法则:1、基准,即有穷,最终至少有一个...
  • Java递归函数讲解

    2021-03-15 12:53:55
    Java中的递归什么是递归?函数直接或间接调用自身的过程称为递归,相应的函数称为递归函数。使用递归算法,某些问题可以很容易地解决。这类问题的例子有Hanoi的Towers(TOH)、序/前序/后序树遍历、图的DFS等。递归中...
  • 一、概述 生活中来说: 父辈种地-- 挣钱 -- 供养孩子 -- 孩子长大 -- 孩子种地 -- 孩子挣钱 -- 供养孩子 -- 孙子长大 -- 孙子...递归一定要有出口,否则会报 栈内存溢出 异常 2.递归出口完了,还是会报 代...
  • 递归 递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上,递归,顾名思义,其包含了两个意思:递 和 归,这正是递归思想的精华所在。递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决...
  • 题目:编写一个java程序,实现递归算法从一加到一百,下面一起看看是如何实现的。实例:publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubSystem.out.println("sum:"+dg(1,100));System.out....
  • Java递归寻路实现,你理解递归了吗

    千次阅读 多人点赞 2021-08-24 13:55:20
    小伙伴们,好久不见,是不是谈递归色变,递归递归:通俗讲,我们拆分一下,“递”出去,“归”回来,哈哈,正如狂铁所说:“越是困难越是要战胜它”,不如来看看这篇文章,对于小白可能会有新的收获,大牛的话就小...
  • JAVA递归

    2021-03-13 08:33:17
    1.递归作为一种算法在程序设计语言中广泛应用,是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。2.递归算法一般用于解决三种问题:1)数据的定义是按递归定义的。( Fibonacci(斐波那契)函数)。...
  • Java递归求和的两种简单方法(推荐)方法一:package com.smbea.demo;public class Student {private int sum = 0;/*** 递归求和* @param num*/public void sum(int num) {this.sum += num--;if(0 < num){sum(num...
  • Java递归计算n的阶乘

    2021-03-22 23:32:50
    2、找到出口(边界值),让递归有结束边界 注意: 如果递归太多层,或者没有正确结束递归,则会出现栈内存溢出ERROR。 问题:为什么会出现内存溢出,而不是堆内存溢出? 溢出的意思就是越界,操作系统会给...
  • Java 求1-100的和,用递归和循环

    千次阅读 2020-12-19 21:00:03
    分享一个基础的练习题:用Java 求1-100的和,用递归和循环两种方法 一:循环 int sum=0; for(int i=1;i<=100;i++) { sum=sum+i; } System.out.println("1-100的和为"+sum) 二:递归方法 public ...
  • java递归算法有一道经典题目,求n的阶乘,这是每个学习递归算法的小伙伴必经的,下面我们就来看看它该怎么实现。示例1:importjava.util.Scanner;publicclassJiecheng{publicstaticintjiecheng(intn){//intk=1;//...
  • java递归

    2021-03-02 12:07:28
    package digui; /** * @author moon * @create 2021-03-02 11:57 */ public class add { public int add(int n){ //1....1的,则表示当前问题还不是最小问题,可以继续向下拆分 //大问题当中包含着小问题的解决...
  • 1,java递归生成目录树 返回list<T> 递归方法返回List<T>类型 public List<ProductCategory> treeselect() { // 获取数据库表中的所有数据 List<ProductCategory> dataList = ...
  • 递归调用结束。 用图表示如下; package com.wjl; public class Perm { static int count = 0; public void perm(int[] list, int k, int m) { if(k == m) { for(int i= 0; i; i++) { System.out.println(list[i]); }...
  • 要求: 分别使用多层for循环 和 递归解决上述问题 Math.random()的使用及做题思路 java.lang.Character.isLetterOrDigit(int codePoint) 确定指定字符(Unicode代码点)是一个字母或数字。 字符被确定是字母或数字,...
  • /***递归查找文件*@parambaseDirName查找的文件夹路径*@paramtargetFileName需要查找的文件名*/publicstaticFilefindFiles(StringbaseDirName,StringtargetFileName){Filefile=null;FilebaseDir=newFile(baseDirNam....
  • 斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...import java.util.Scanner; //递归求斐波那契数列的第n个数值 //递归就是自己调用自己 class Evaluate//求值类 { private int a1
  • Java——递归调用

    2021-02-12 23:49:53
    递归是程序语言中的一个很基础的应用,学习递归对理清程序编码的思路非常有帮助所以在本章中把递归也作为学习的一部分内容。希望读者了解并掌握它的相关用法我们在中学时期都学过数学归纳,例如求n的阶乘比如要求5!,...
  • Java递归总结

    2021-02-27 17:29:15
    对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代码的简洁,但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵,分析了递归与循环...
  • 在一个 n X n 的棋盘上放置n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆。 解法 拿到问题先考虑存储方式,使用一维数组代表棋盘可以大大减少存储空间, 代码 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,808
精华内容 27,123
关键字:

java递归法

java 订阅