基于分治和DP的算法设计
发现下面的策略都是比较糟糕的，这里提及一下分治和动态规划的区别，动态规划避免了分治方法的重复计算，下面的基本上是用了最朴素的动态规划方案，接下来会用自底向上的方案来解决
题目一：
半数集问题
1，n属于set(n),
2，在n的左边加上一个自然数，但该自然数不超过最近添加的数的一半
按照此规则进行处理，知道不能再添加自然数为止
如set(6) = {6,16,26,126,36,136}
set(8) = {8,18,28,38,48,128,138,148,248,1248}
public class Banshuji {
//多重集的半数集问题
private static int n;
private static ArrayList<Integer>list = new ArrayList<Integer>();
public static int getN() {
return n;
}
public void setN(int n) {
this.n = n;
}
public static void readIn(){
Scanner in = new Scanner(System.in);
n = in.nextInt();
list.add(n);
}
//应该用分治的思想来实现
public static void compute(int n,int s1,int s2){
for(int i=1;i<=n/s1/2;i++){
int n1 = i*s2+n;
list.add(n1);
compute(n1,s1*10,s2*10);
}
}
public static void print(){
for(Integer ints:list){
System.out.print(ints);
System.out.print(",");
}
System.out.println();
System.out.print("数量为："+list.size());
}
public static void main(String[] args) {
Banshuji.readIn();
Banshuji.compute(Banshuji.getN(),1,10);
Banshuji.print();
}
}题目2 求反转，输入12,34
输出46
public int returnS(){
Scanner in = new Scanner(System.in);
String s = in.next();
String[] strTemp = s.split(",");
int x = Integer.parseInt(strTemp[0]);
/*xN = strTemp[0].length();*/
int y = Integer.parseInt(strTemp[1]);
/*yN = strTemp[1].length();*/
return Rev(Rev(x)+Rev(y));
}
public int Rev(int a){
int count =1;
int s2=1;
int sum=0;
int temp =a/10;
while(temp!=0){
count++;
temp/=10;
}
int len = count;
while(count>1){
s2*=10;
count--;
}
count = len;
while(count>=1){
sum+=a%10*s2;
a =a/10;
s2/=10;
count--;
}
return sum;
}
public static void main(String[] args) {
Test10 test = new Test10();
System.out.print(test.returnS());
}题目 3：输入：整型n
输出：m,最小整数使得m的各位相乘等于n
public class Test18 {
//题目为输入一个正整数n,返回这个整数因子相乘得到n，并且这个数最小，比如，36=4*9
//49最小，而找不到这样的数则返回-1
private static int input;
private static int len=0;;
public static void readIn(){
Scanner in = new Scanner(System.in);
input = in.nextInt();
}
public static int getLength(int n){
int num = n;
while(num!=0){
len++;
/*System.out.print(len);*/
num/=10;
}
return len;
}
public static int returnS(){
readIn();
int[] sum=new int[3];
sum[0] = -1;
return compute2(input,getLength(input),sum);
}
/*public int compute(int n,int j){
//j表示应该返回数值的位数
int length = getLength(n);
int syn =1;
for(int i=2;i<=9;i++){
if(n%i==0){
//说明i是n的一个因子
}
}
}*/
/*public boolean judge(int j,int n){
boolean flag=false;
//判别n是否可以分解为由j个因子组成,每个因子都在2-9之间进行取值
for(int i=2;i<=9;i++){
int count=0;
if(n%i==0){
count++;
judge(j,n/i);
if(count==j){
flag = true;
}
}
}*/
/* return flag;
}*/
public static int compute2(int n,int len,int[] sum){
/*boolean flag = false;*/
for(int i=2;i<=9;i++){
if(n==i){
sum[0] = i;
sum[1] = 1;
sum[2] = 10;
break;
}
if(n%i==0&&len>1){
compute2(n/i,len-1,sum);
if(sum[1]==1)
{
sum[0]=sum[0]+i*sum[2];
sum[2]=10*sum[2];
break;
}
}
}
return sum[0];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print(Test18.returnS());
}
}题目4
求不相邻的最小红包数和最大红包数，收尾在本题中也是相邻的，比如2,4,5,3,6,1,7中2和7也是相邻的。
输入量：1，为所求红包链的个数，也就是要求的红包链的数量，代表循环的次数
2，红包链，如果1中输入的量为1，则一条红包链，输入为：2,4,5,3,6,1,7
输出：不相邻最大红包数量18，不相邻最小红包数量6
public class Test5 {
private int[]temp;
private int N;
public void readIn(){
Scanner in1 = new Scanner(System.in);
System.out.print("please input the number of:");
N = in1.nextInt();
while(N>0){
System.out.print("input the number:");
Scanner in = new Scanner(System.in);
String str = in.next();
String[] strTemp;
strTemp = str.split(",");
//将其转换为整型
temp = new int[strTemp.length];
for(int i=0;i<strTemp.length;i++){
temp[i] = Integer.parseInt(strTemp[i]);
}
System.out.print(MessageFormat.format("不相邻位置的最大值：{0},不相邻位置的最小值：{1}", getMax(),getMin()));
System.out.println();
N--;
}
}
//判别是否为首尾相邻的情况
public int getN(){
return temp.length/2;
}
//用来求不相邻红包的最小值
public int getMin(){
int minValue = Integer.MAX_VALUE;
for(int i=0;i<temp.length;i++){
int sum =0;
int count = 1;
for(int j=i;count<=getN();){
sum+=temp[j];
j=j+2;
count++;
if(j>=temp.length){
j=j-temp.length;
}
}
if(sum<minValue)
minValue = sum;
}
/*System.out.print(maxValue);*/
return minValue;
}
public int getMax(){
//用来求出不相邻红包的最大值
int maxValue= Integer.MIN_VALUE;
for(int i=0;i<temp.length;i++){
int sum =0;
int count = 1;
for(int j=i;count<=getN();){
sum+=temp[j];
j=j+2;
count++;
if(j>=temp.length){
j=j-temp.length;
}
}
if(sum>maxValue)
maxValue = sum;
}
/*System.out.print(maxValue);*/
return maxValue;
}
public static void main(String[] args) {
Test5 test = new Test5();
test.readIn();
}
}题目5
目前有一个不太会的题目，希望会的大神能帮忙解答
一系列数字23,54,33,12,66,7,41找出累加其中的数字，每个数字不能被重复使用，找出累加和最接近100的和是多少，并且是由哪些数字组成的。刚刚想到一种方法，实现了一下是可行的~~
package TEXT;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Text10 {
/*private int[] arrayNum;*/
private ArrayList<Integer> listTemp = new ArrayList<Integer>();
private int[] array;
private int num;
public Text10(int num,int[] array){
this.num = num;
this.array = new int[array.length];
for(int i=0;i<array.length;i++){
this.array[i] = array[i];
}
listTemp.add(num);
}
public void cal_Sum(int j,int sum){
int max = num;
for(int i=j;i<array.length;i++){
int temp = sum;
temp+=array[i];
if(temp>num){
//说明此次累加是无意义的，因而需要从下次循环开始进行
continue;
}
listTemp.add(temp);
cal_Sum(i+1,temp);
}
}
public int returnS(){
cal_Sum(0,0);
for(int i=0;i<listTemp.size();i++){
System.out.println("----"+listTemp.get(i)+"----");
}
return secondMax(listTemp);
}
public int secondMax(ArrayList<Integer>list){
Collections.sort(list);
return list.get(list.size()-2);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array ={22,3,5,6};
Text10 text = new Text10(30,array);
System.out.print(text.returnS());
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年10月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读