AI 助理
备案控制台
开发者社区 云计算 文章 正文

第七章递归知识讲解。（二）

2023-02-18 96
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 第七章递归知识讲解。（二）

第四题“逐步生成结果”之非数值型问题。

package 第七章递归知识讲解;
import java.util.HashSet;
import java.util.Set;
/**
 * 7.5 “逐步生成结果”之非数值型问题
 * @author MZFAITHDREAM
 *
 */
public class 递归4 {
  //递归
    public static Set<String> kuohao1(int m){
        Set<String> s_M=new HashSet<>();  //因为set可以去重复
        if(m==1) {
            s_M.add("()");
            return s_M;
        }
        Set<String> set_m_1=kuohao1(m-1); //调m-1层，添加元素
        for (String s : set_m_1) {
            s_M.add("()"+s);
            s_M.add(s+"()");
            s_M.add("("+s+")");
        }
        return s_M;
    }
    //迭代
    public static Set<String> kuohao2(int m){
        Set<String> res=new HashSet<>();
        res.add("()");
        if(m==1) return res;  
        for (int i = 2; i <=m; i++) {
            Set<String> res_new=new HashSet<>();  //创建一个新的集合用于存储上一个集合更新后的结果
            for (String s : res) {  //添加
                res_new.add("()"+s);
                res_new.add(s+"()");
                res_new.add("("+s+")");
            }
            res=res_new; //更新集合
        }
        return res;
    }
    public static void main(String[] args) {
        Set<String> kuohao1 = kuohao1(8);
        for (String s : kuohao1) {
            System.out.print(s+"    ");
        }
        System.out.println();
        Set<String> kuohao2 = kuohao2(3);
        for (String s : kuohao2) {
            System.out.print(s+"    ");
        }
    }
}


第五题 子集生成

package 第七章递归知识讲解;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
/**
 * 7.6 子集生成
 * @author MZFAITHDREAM
 * 给定一个数组A和数组的大小int n，请返回A的所有非空子集。
 *
 */
/**
 * 2的n次方-1
 * arr目标数组
 * cur:数组下标1
 * @author MZFAITHDREAM
 *
 */
public class 递归6 {
  public static void main(String[] args) {
  递归6 obj=new 递归6();
        int[] a= {1,2,3};
        Set<Set<Integer>> subSets=obj.getSubset(a,a.length);
        System.out.println(subSets);
    }
    public Set<Set<Integer>> getSubset(int[] a,int n){
        return solve(a,n,n-1);
    }
    private static Set<Set<Integer>> solve(int[] a, int n, int cur) {
        /**
         * 下面是大集合
         * 对每一个元素 建立集合
         */
      Set<Set<Integer>> newset=new HashSet<>();
        /**
         * 判断
         */
        if(cur==0) {
            Set<Integer> nil=new HashSet<>();//空集
            Set<Integer> first=new HashSet<>();//第一个元素
            first.add(a[0]);
            newset.add(nil);
            newset.add(first);
            return newset;
        }
//        大集合里面
        Set<Set<Integer>> oldset=solve(a,n,cur-1);
        for(Set<Integer> set:oldset){
            //对于每个子集cur下标对应的元素可以加进去也可以不加进去
            newset.add(set);//保留原样
            Set<Integer> clone=(Set<Integer>)((HashSet)set).clone();//拷贝set
            clone.add(a[cur]);//添加当前元素
            newset.add(clone);
        }
        return newset;
    }
  }


第六题子集生成之二进制法。

package 第七章递归知识讲解;
import java.util.HashSet;
import java.util.Set;
/**
 * 7.6 子集生成之二进制法
 * @author MZFAITHDREAM
 *
 *
 */
public class 递归7 {
  private static Set<Set<Integer>> newSet;
  public static void main(String[] args) {
//  调用自己定义的方法
  int [] A= {123,456,789};
  Set<Set<Integer>> set=new 递归7().getSubset(A, A.length);
  System.out.println(set);
  }
 public static Set<Set<Integer>> getSubset(int[] A,int n){
     return solve(A,n,n-1);
 }
 /**
  * 递归增量构造法
  * @param A
  * @param n
  * @param cur
 * @return 
  */
 private static Set<Set<Integer>> solve(int[] A, int n, int cur) {
  if(cur==0) {//处理第一个元素
//  null
  Set<Integer> nil=new HashSet();
//  fist
  Set<Integer> fist=new HashSet();
  fist.add(A[0]);
  newSet.add(nil);
  newSet.add(fist);
  try {
  Set<Set<Integer>> oldSet =getSubset(A, n);
  } catch (Exception e) {
  // TODO Auto-generated catch block
  e.printStackTrace();
  }
  Set<Set<Integer>> newSet =new HashSet();
  for (Set<Integer> set : newSet) {
//  对于每个子集，cur这个元素可以加进去，也可以不加进去
  newSet.add(set);//保留原样
//  set转为HashSet
  Set<Integer>clone= (Set<Integer>) ((HashSet)set).clone();
//  上面是技术克隆 
  clone.add(A[cur]); //增加元素
  newSet.add(clone);
  } 
  return  newSet;
  }
  return newSet;
 }
}


7.7 子集生成之二进制法。

package 第七章递归知识讲解;
import java.util.HashSet;
import java.util.Set;
/**
 * 7.7 子集生成之二进制法
 * @author MZFAITHDREAM
 *
 *2的n次方-1
 */
public class 递归71 {
  public static void main(String[] args) {
  Object[] arr = {1,2,3};
  Set<Set<Object>> subSets = getSubSets( arr,arr.length-1);  
  subSets.remove(new HashSet<Object>());//移除空集
  System.out.println(subSets);
  }
  /*
  * arr:目标数组
  * cur:正在操作的数组元素下标 
  */
  public static Set<Set<Object>> getSubSets(Object[] arr,int cur) {
  //当前元素对应的结果,
  Set<Set<Object>> newSet = new HashSet<Set<Object>>();
  if(cur == 0) {
    Set<Object> nil = new HashSet<Object>();//借助空集
    Set<Object> first = new HashSet<Object>();//只包含第一个元素的子集
    first.add(arr[cur]);
    newSet.add(nil);
    newSet.add(first);
    return newSet;
  }
  //上一个元素的结果
  Set<Set<Object>> oldSet = getSubSets(arr,cur-1);
  for (Set<Object> set : oldSet) {
    newSet.add(set);
    Set<Object> temp = new HashSet<Object>(set);
    temp.add(arr[cur]);
    newSet.add(temp);
  }
  return newSet;
  }
  /**
  * //递推实现:
  * @param args
  */
  public static void main1(String[] args) {
  Object[] arr = {"c","d","a"};
  Set<Set<Object>> subSets = getSubSets( arr,arr.length-1);
  subSets.remove(new HashSet<Object>());
  System.out.println(subSets);
  }
  /* arr:目标数组
  * cur:正在操作的数组元素下标 
  */
  public static Set<Set<Object>> getSubSets1(Object[] arr,int cur) {
  //当前元素对应的结果,
  Set<Set<Object>> res_set = new HashSet<Set<Object>>();
  res_set.add(new HashSet<Object>());
  for (Object i : arr) {
   Set<Set<Object>> tempSet = new HashSet<Set<Object>>();
    tempSet.addAll(res_set);
    for (Set<Object> set : res_set) {
    Set<Object> temp = new HashSet<Object>(set);
    temp.add(i);
    tempSet.add(temp);
    }
    res_set = tempSet;
  }
  return res_set;
}
}


第八题：全排列（上）

package 第七章递归知识讲解;
import java.util.ArrayList;
/**
 * 7.8 全排列（上）
 * @author MZFAITHDREAM
 *给定一个字符串String s = "abc";求s的全排列
递归实现:
对于字符串s的全排列可以再s.length()-1的字符串全排列基础上放左边,放右边和放中间几种方式实现
 */
import java.util.HashSet;
import java.util.Set;
public class 递归8 {
  public static void main(String[] args) {
  Set<String>res=new 递归8().getPermutations("ab");
  System.out.println(res);
  System.out.println("----------------------全排列方式------------------------------------");
  Set<String>re=new 递归8().getPermutations1("abc");
  System.out.println(re);
  }
  /**
  * 
  *全排列
  * @param str
  * @return
  */
  public static Set<String> getPermutations1(String str) {
  //当前元素对应的结果,
  Set<String> res_set = new HashSet<String>();
//  判断长度==1
  if(str.length()==1) {
    res_set.add(str);
    return res_set;
  }
//字符串长度-1的全排列
  Set<String> pre_set =
      getPermutations1(str.substring(0,str.length()-1));
  String addStr = str.charAt(str.length()-1)+"";//需要添加的字符串
  for (String s : pre_set) {
    //放左边
    String tempStr = addStr+s;
    res_set.add(tempStr);
    //放右边
    tempStr = s+addStr;
    res_set.add(tempStr);
    //放中间
    for (int j = 1; j < s.length(); j++) {
    tempStr = s.substring(0,j)+addStr+s.substring(j);
    res_set.add(tempStr);
    }
  }
  return res_set;
  }
  /**
  * 递推实现:
  * @param str
  * @return
  */
  public static Set<String> getPermutations(String str) {
  //当前元素对应的结果,
  Set<String> res_set = new HashSet<String>();
  res_set.add(str.substring(0,1));
  if(str.length()==1) {
    return res_set;
  }
  for (int i = 1; i < str.length(); i++) {
    Set<String> tempSet = new HashSet<String>();
    String addStr = str.substring(i,i+1);
    for (String s : res_set) {
    //放左边
    String tempStr = addStr+s;
    tempSet.add(tempStr);
    //放右边
    tempStr = s+addStr;
    tempSet.add(tempStr);
    //放中间
    for (int j = 1; j < s.length(); j++) {
     tempStr = s.substring(0,j)+addStr+s.substring(j);
      tempSet.add(tempStr);
    }
    }
    res_set = tempSet;
  }
  return res_set;
  }
}


全排列（中）

package 第七章递归知识讲解;
import java.util.HashSet;
import java.util.Set;
/**
 * 7.8 全排列（中）
 * @author MZFAITHDREAM
 *
 */
public class 递归9 {
  public static void main(String[] args) {
  Set<String>res= new 递归9().getPermutations("abcdef".toCharArray(),3);
  System.out.println(res);
  }
  private static Set<String> res = new HashSet();;
  public static Set<String> getPermutations(char[] charArr,int k) {
  if(k==charArr.length) {
    res.add(new String(charArr));
  }
  for (int i = k; i < charArr.length; i++) {
    swap(charArr,k,i);
    getPermutations(charArr,k+1);//将剩余元素一次放在k+1位置
    swap(charArr,k,i);//还原(回溯)
  }
  return res;
  }
  static void swap(char[] charArr,int i,int j) {
  char temp = charArr[i];
  charArr[i] = charArr[j];
  charArr[j] = temp;
  }
}


全排列（下)

package 第七章递归知识讲解;
/**
 * 7.8 全排列（下)
 * @author MZFAITHDREAM
 *
 */
public class 递归10 {
  /**
  * 前缀法
  * @param args
  */
  public static void main(String[] args) {
  permutations("","abc");
  }
  final static int k = 5;
  static int count = 0;
  public static void permutations(String prefix,String target) {
  if(prefix.length() == target.length()) {
    count++;
    if(count==k) {
    System.out.println(prefix);
    System.exit(0);
    }
  }
  for (int i = 0; i < target.length(); i++) {
    char ch = target.charAt(i);
    if(!prefix.contains(ch+"")) {
    permutations(prefix+ch,target);
    }
  }
  }
}
t75yjb52rsccc
目录
相关文章
布客飞龙
|
7月前
|
算法 JavaScript 前端开发
递归的递归之书：第五章到第九章
递归的递归之书：第五章到第九章
布客飞龙
156 0
布客飞龙
|
7月前
|
存储 JavaScript 前端开发
递归的递归之书：第十章到第十四章
递归的递归之书：第十章到第十四章
布客飞龙
54 0
一只大鸽子
|
6月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
一只大鸽子
62 1
龙大吉
|
6月前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用，包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现，通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数，分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例，展示了递归的优雅与效率。然而，递归可能导致栈溢出，需注意优化。学习递归深化了对“分而治之”策略的理解。**
龙大吉
124 7
布客飞龙
|
7月前
|
存储 算法 JavaScript
递归的递归之书：引言到第四章
递归的递归之书：引言到第四章
布客飞龙
191 0
sky_qiyi
|
6月前
数据结构学习记录——判断是否为同一颗二叉搜索树（题意理解、求解思路、程序搭建框架、具体函数的实现）
数据结构学习记录——判断是否为同一颗二叉搜索树（题意理解、求解思路、程序搭建框架、具体函数的实现）
sky_qiyi
62 2
GR鲸鱼
|
7月前
|
算法
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码（上）
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
GR鲸鱼
39 1
空白诗
|
6月前
|
机器学习/深度学习 存储 算法
算法学习：递归
算法学习：递归
空白诗
66 0
sky_qiyi
|
6月前
|
C语言
C语言学习记录——用递归思想求第n个斐波那契数，函数递归
C语言学习记录——用递归思想求第n个斐波那契数，函数递归
sky_qiyi
28 0
aliyun0193839942-27807
|
7月前
|
机器学习/深度学习 算法
加深理解函数递归
加深理解函数递归
aliyun0193839942-27807
37 0

热门文章

最新文章

  • 1
    Hadoop迁移MaxCompute神器之DataX-On-Hadoop使用指南
  • 2
    Nginx的启动、停止与重启
  • 3
    Hive之数据倾斜的原因和解决方法
  • 4
    开发人员各级岗位胜任力模型
  • 5
    Node.js 中流操作实践
  • 6
    传奇龙版地图查看器
  • 7
    调整DC的网络对网络是否会有影响?
  • 8
    How to maintain Oracle10g Recyclebin?
  • 9
    你知道自己感染了恶意软件吗？
  • 10
    Groovy 快速入门
  • 1
    Python学习的自我理解和想法（9）
    90
  • 2
    Kimi 上线视觉思考模型，K1 系列强化学习模型正式开放，无需借助外部 OCR 处理图像与文本进行思考并回答
    102
  • 3
    CosyVoice 2.0：阿里开源升级版语音生成大模型，支持多语言和跨语言语音合成，提升发音和音色等的准确性
    80
  • 4
    Megrez-3B-Omni：无问芯穹开源最强端侧全模态模型，支持理解图像、音频和文本三种模态数据
    51
  • 5
    FreeScale：无需微调即可提升模型的图像生成能力，生成 8K 分辨率的高质量图像
    38
  • 6
    Freestyler：微软联合西工大和香港大学推出说唱音乐生成模型，支持控制生成的音色、风格和节奏等
    37
  • 7
    《C 语言与统计假设检验：洞察人工智能模型性能差异》
    83
  • 8
    《C 语言赋能：物联网环境下人工智能应用的能耗优化之道》
    23
  • 9
    《C 语言助力神经网络剪枝：优化模型的卓越之道》
    25
  • 10
    《C 语言复数运算：赋能人工智能信号处理新境界》
    20

    • 相关课程

    更多
  • 机器学习入门-概念原理及常用算法

    • 相关电子书

    更多
  • 图解算法小抄
  • Python第五讲——关于爬虫如何做js逆向的思路
  • 低代码开发师（初级）实战教程

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    fs.oss.accessKeyId和fs.oss.accessKeySecret。