文章目录
上台阶
问题
将问题分解为子问题使用递归解决。
子问题相较于原来的问题形式相同，规模更小。
上台阶可以一次上1级或2级，现在要求上n级台阶有几种走法。
这个问题可以分解为先走一级后，剩下n-1级的走法+先走2级后，剩下n-2级台阶的走法。
也就是f(n) = f(n-1)+f(n-2)。
同时，递归的边界条件是n小于0时返回0，n为1时只有一种走法返回1，n为2时两种走法返回2。
题解
import java.util.*;
public class Main {
public static String expression;
public static int stairs(int n){
if(n<=0) return 0;
if(n==1) return 1;
else if(n==2) return 2;
return stairs(n-1)+stairs(n-2);
}
public static void main(String[] args){
System.out.println(stairs(5));
}
}
放苹果POJ1664
题目地址
http://poj.org/problem?id=1664
问题
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？注：5，1，1和1，5，1是同一种放法。
设把i个苹果放在k个盘子里的放法数量是f(i,k)，则：
k>i时，f(i,k) = f(i,i)
k<=i时，放法 = 有盘子为空的放法+没盘子为空的放法
f(i,k) = f(i,k-1)+f(i-k,k)
有盘子为空的放法，就是至少一个盘子不放苹果，因此是f(i,k-1)
没盘子为空，那向每个盘子先放一个，所以剩下i-k个就是f(i-k,k)
边界条件：
当i==0时，没有苹果放，只有1种放法
当k==0时，没有盘子了，只有0种放法
题解
import java.util.*;
public class Main {
public static int putApplpe(int i,int k) {
if(k>i) return putApplpe(i,i);
if(i==0) return 1;//没有苹果时有1种放法
if(k==0) return 0;//没有盘子没有放法
return putApplpe(i,k-1) + putApplpe(i-k,k);
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while(n--!=0){
int i = scanner.nextInt();
int k = scanner.nextInt();
System.out.println(putApplpe(i,k));
}
}
}
算24
问题
给出4个小于10的正整数，可以使用加减乘除以及括号，是否存在一种方式使得结果为24。
给定一个4个数的输入，如果存在某种组合结果为24，则输出true，不存在就输出false。
那么n个数算24，必然有两个数先算。这两个数计算的结果，作为一个数，再与剩下的数字进行运算。
那我们就需要枚举先算的两个数，以及两个数的运算方式。
边界条件：
只剩一个数的时候，看它是不是24就好了。
题解
import java.util.*;
public class Main {
public static boolean isZero(double x){
return Math.abs(x)<=1e-6;
}
public static boolean is24(double a[],int n) {
if(n==1)
if(isZero(a[0]-24)) return true;
else return false;
double[] b = new double[5];
for(int i=0;i<n-1;++i)
for(int j=i+1;j<n;++j) {//枚举两个数
int m = 0;//还剩m个数
for(int k=0;k<n;++k)//剩下的n-2个数放入b
if(k!=i&&k!=j) b[m++] = a[k];
b[m] = a[i]+a[j];
if(is24(b,m+1)) return true;
b[m] = a[i]-a[j];
if(is24(b,m+1)) return true;
b[m] = a[j]-a[i];
if(is24(b,m+1)) return true;
b[m] = a[i]*a[j];
if(is24(b,m+1)) return true;
if(!isZero(a[j])){
b[m] = a[i]/a[j];
if(is24(b,m+1)) return true;;
}
if(!isZero(a[i])){
b[m] = a[j]/a[i];
if(is24(b,m+1)) return true;;
}
}
return false;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int a1 = scanner.nextInt();
int a2 = scanner.nextInt();
int a3 = scanner.nextInt();
int a4 = scanner.nextInt();
double a[] = new double[5];
a[0] = a1;
a[1] = a2;
a[2] = a3;
a[3] = a4;
System.out.println(is24(a,4));
}
}