算法设计

Question

某批警察正在进行智力测验，解答       1   2   3   4   5    6    7    8   9   =110
为了使等式成立需在数字中间添上"+" 或者"-"
之间没有符号的组成数
例如12+34+56+7-8+9是一种填法
123+4+5+67-89也是一种填法
需要输出每个答案占一行

Answer 1

public class test1 {
public static void main(String args[]){
String str="123456789";
char[] chars = str.toCharArray();
int[] array = new int[8];
StringBuffer sb = new StringBuffer(); while(array[0]<3){
sb.append(chars[0]);
for(int k=0;k<chars.length-1;k++){
if(array[k]==1){
sb.append("+");
}
else if(array[k]==2){
sb.append("-");
}
sb.append(chars[k+1]);
}
if(parse(sb.toString())){
System.out.println(sb.toString());
}
sb.setLength(0);

array[7]++;
for(int i=7;i>0;i--){
if(array[i]==3){
array[i]=0;
array[i-1]++;
}
}

}
}
private static boolean parse(String str) {
String[] str1 = str.split("[\\+]|[-]");
String str2 = str.replaceAll("\\d*","");
int sum = 0;
sum = Integer.parseInt(str1[0]);
for(int i=0;i<str1.length-1;i++){
switch(str2.charAt(i)){
case '+':
sum+=Integer.parseInt(str1[i+1]);
break;
case '-':
sum -=Integer.parseInt(str1[i+1]);
break;
}
}
if(sum==110){
return true;
}
return false;
}
}

Answer 2

/*集合划分：
f(5,3)=1,1,3  1,2,2   2,1,2  2,2,1
*/
#include <iostream>
#include <string.h>
using namespace std;
int sumTiger(int i,int sums);
int n;
int m;
int c=0;
int sum[10];
int tiger[10]={1,2,3,4,5,6,7,8,9};
int op[10];
#define N  110  //合void show(int *p)
{
int i,len=0;
//把数字求出来  for(i=0;i< m ;i++)
  {
   sum[i]=0;
    for(int j=0;j< p[i]; j++)
    {
      sum[i] *=10;
      sum[i] +=tiger[len++];
    }
   
  }
  
 sumTiger(0,0);
}int sumTiger(int i,int sums)
{
if(i >= (m))
{
//输出值
  if(sums == N)
  {
   int j;
   for( j=0;j< m-1;j++)
   {
     cout<<sum[j];
     if(op[j]==0)cout<<'+';
     if(op[j]==1)cout<<'-';
   }
   cout<<sum[j];
   cout<<'='<<sums<<endl;
  }
 
  return 0;
}     op[i]=0;    sumTiger(i+1,sums+sum[i]);     op[i]= 1;   sumTiger(i+1,sums-sum[i]);   return 1;
}
//把全部的状态列出来
void pai(int *p,int i)
{
    if(i>=(m-1))
    {
      p[i]=n-c;
      show(p);
    }else
    {
       for(int j=1;j<(n-m+2);j++)
       { 
         c+=j;
         if(c<n)
         {
            p[i]=j;
            pai(p,i+1);
            p[i]=0;  
         }
          c-=j;
         if(c>=n)break;
      }
    }
}
int main()
{
   // cin>>n;//输入个数
   n=9;
   int *p=new int[n];
   memset(p,0,sizeof(int)*n);for(int i=1;i<=n;i++)
{
    c=0;
    m=i;
    pai(p,0);
}
return 0;
}

Answer 3

http://blog.csdn.net/snakewarhead/article/details/7459790