您的位置: 首页  >  文章  >  递归问题

递归问题

分类: 文章 • 2024-07-31 22:32:16
  1. 递归将数据从左侧移右侧实现全排列
package com.qcx;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class List {
	// 输出
		public static void print(List target){
			for(Object o: target){
				System.out.print(o);
			}
			System.out.println();
		}
		// 递归排列
		public static void sort(List datas,List target,int n){
		//若新的集合和原集合的长度相同，则调用输出。
			if(target.size()==n){
				print(target);
				return;
			}
			for(int i=0;i<datas.size();i++){
				//把数组真正转换成集合
				List newDatas = new ArrayList(datas);
				List newTarget = new ArrayList(target);
				newTarget.add(newDatas.get(i));
				newDatas.remove(i);
				//递归
				sort(newDatas,newTarget,n);
			}
		}
		public static void main(String[] args){
			String[] s = {"a","b","c"};
			//asList的返回对象是一个Arrays内部类,并没有实现集合的修改方法。Arrays.asList体现的是适配器模式，只是转换接口，后台的数据仍是数组。故sort方法中需要将数组转化为集合
			sort(Arrays.asList(s),new ArrayList(),s.length);
		}
}

分析： 先将数组用asList转化一下，再创建一个新的数组，并且传入一个字符串的长度。在递归函数中如果新的集合长度等于原来字符串的长度则说明排列完成输出即可。for循环的内部关键是 ，循环一次就递归，相当于把字符串拆分后继续执行递归方法，直到newDatas的长度为0，newTarget的长度变为n，就输出。（不知表述的是否清楚，请见谅，请自行模拟一下代码过程即可）

参考文章：https://blog.****.net/Robert_Ln/article/details/79773040

另一种解法：

package com.qcx;
//全排列，例如三个字母abc   可排列成abc,acb,bca,bac,cab,cba并显示出来
public class List {
	//k是当前的交换位置，与其后的元素交换
	public static void f(char date[],int k) {
		if(k==date.length) {
			for(int i=0;i<date.length;i++) {
				System.out.print(date[i]+" ");
			}
			System.out.println();
		}
		for(int i=k;i<date.length;i++) {
			//试探
			{
				char t=date[k];
				date[k]=date[i];
				date[i]=t;
			}
			//回溯
			f(date,k+1);
			{
				char t=date[k];
				date[k]=date[i];
				date[i]=t;
			}
		}
	}
	public static void main(String[] args) {
		char [] date="abcd".toCharArray();
		f(date,0);
	}
}

分析：后面的数与前面的数依次交换位置从而获得新的字符串，但是交换位置之后要再把位置调整回来才可以

2.反串问题，输入ige字符串将其倒着输出。例如输入abc，则输出cba。

package com.qcx;
public class Fanchuan {
	public static String f(String s) {
		if(s.length()<2||s.length()==0) {
			return s;
		}else 
		return f(s.substring(1))+s.charAt(0); //从每个字符串的第二个字符截取，使其进入下一次循环
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(f("abcd"));
	}
}

分析：将每个字符串不断截取，使其长度为1时返回最后剩余的元素（与递归求阶乘问题相似），再一个一个返回即可拼接成逆串。
f(s.substring(1))+s.charAt(0);

3.m个A和n个B可以组成多少种不同的排列方式。

package com.qcx;
/**
 1. @author 仇晨旭
 *m个A和n个B可以组成多少种排列
 */
public class AB {
	//m个A，n个B
	public static int f(int m,int n) {
		if(m==0||n==0) return 1;
		return f(m-1,n)+f(m,n-1);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(f(3,1));  //6
	}
}

分析：每一个位置可以放A也可以放B，当A的个数和B的个数都为0时就是一种排列，所以判断递归结束的语句就是用if来判断AB的个数是否是0，是则返回1。f(m-1,n)当第一个字符是A时，m-1，f(m,n-1)第二个字符为B时n-1，最后加起来就是总个数。

  1. 解析下来的这道题可就厉害了，我也不知道题目是啥（当时笔记没做好，之写出了代码，没有将题目记录下来，见谅），应该是从两个串中判断相同子串的长度
package com.qcx;
public class Substring {
	public static int f(String s1,String s2) {
		if(s1.length()==0||s2.length()==0)  return 0;
		if(s1.charAt(0)==s2.charAt(0)) 
			return f(s1.substring(1),s2.substring(1))+1;
		else 
			return Math.max(f(s1.substring(1),s2), f(s1, s2.substring(1)));
	}
	public static void main(String[] args) {
		// 输出为3
		int	k=f("fabckd","xbacd");
		System.out.println(k);
	}
}

先记录代码吧！！等找到原题在进行修改。

  1. 李白打酒问题
    李白去打酒，壶中两斗酒，遇店加一倍，遇花喝一斗。途中遇到5次店，10次花，刚好把酒喝完。输出李白遇店（a）遇花（b）的顺序和总次数。
package com.qcx;
public class test1 {
	static int count=0;
	public static void main(String[] args) {
		String str="";
		fun(0,0,2,str);
		System.out.println(count);
	}
	//d为遇到店且遇到店5次，h为遇到花且遇到花10次,sum为斗中酒
	public static void fun(int d,int h,int sum,String str) {
		if(d==5&&h==10&&sum==0){
			System.out.println(str);
			count++;
			return;
		}else if(d>5||h>10||sum<=0) {
			return;
		} 
		//遇见店
		fun(d+1,h,sum*2,str+"a");
		//遇到花
		fun(d,h+1,sum-1,str+"b");//为什么不能是sum--？应该使用--sum，先减后操作。
	}
}

首先判断出结束递归的条件：当遇到5次店和10次花或者酒为0时输出，且遇花和遇店的次数不能超过指定次数。遇到花时d+1，酒的总数乘以二，遇到花时h+1总数减一。
递归问题就先写这么多吧！！！有什么问题请指教！每天考蓝桥杯，加油！！！

相关推荐