| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1589 人关注过本帖
标题:穷举法优化的问题求解,求个大神。
取消只看楼主 加入收藏
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
结帖率:25%
收藏
已结贴  问题点数:20 回复次数:9 
穷举法优化的问题求解,求个大神。
问题  :该如何修改代码达到以下所有计算式的情况
例如 1+1+1+1等同于1+(1+(1+1))我想消除这些重复的计算式


不含括号:ABCD,共1种
1个括号:(AB)CD、A(BC)D、AB(CD)、(ABC)D、A(BCD),共5种
以上两种情况未考虑

2个括号:(AB)(CD)、((AB)C)D、(A(BC))D、A(B(CD))、A((BC)D),共5种
一共有38400种情况


楼下代码只考虑如下计算式情况
第1种情况  ((a 。b)。c)。d
第2种情况(a 。b)。(c。 d)
第3种情况 (a。(b。c))。d
第4种情况  a。((b。c)。d )
第5种情况 a。(b。(c。d))


[ 本帖最后由 流光溢彩丿 于 2015-6-26 12:59 编辑 ]
搜索更多相关主题的帖子: 如何 
2015-06-25 18:26
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
程序代码:
void   D24(int v[], int result)          // 穷举法求结果,增加变量result 

{
       char op[4]={'+','-','*','/'};             //  +:0  -:1 *:2  /:3
       int count=0;// 计数成功次数
       int i1,i2,i3,i4;
       int f1,f2,f3;
       

//-----------四重循环开始穷举四个数字的位置: 4!=24 种  A44--------------------------
       
       for (i1=0;i1<4;i1++)                  //i表示v[i]下标的位置 i1 i2 i3 i4不能相等(分别为0 1 2 3)  表示4个数排列在数组4个不同的位置上

        for (i2=0;i2<4;i2++)                 // 四重循环对四个数穷举

          if (i2!=i1)

          for (i3=0;i3<4;i3++)

            if (i3!=i2 && i3!=i1)

            for (i4=0;i4<4;i4++)

               if (i4!=i3 && i4!=i2 && i4!=i1)

                 {

//-----------三重循环开始穷举三个运算符: 4X4X4=64 种 +-*/可以重复使用---------------------------

                   for (f1=0;f1<4;f1++)      // 三重循环对运算符穷举,f表示op[f]中的元素

                     for (f2=0;f2<4;f2++)

                       for (f3=0;f3<4;f3++)  // 运算符 f1,f2,f3

                         {                       // 对运算优先级直接列举(5种)

//-----------未用循环,直接穷举三个运算符的优先级: 3!-1=5种( 3*2-1=5)-------------------

                           double t1,t2,t3;      // 存放计算的中间值  两个两个按优先级进行计算

                           // 第1种情况  ((a 。b)。c)。d  :

                           t1=cal(v[i1],v[i2],f1);

                           t2=cal(t1,v[i3],f2);

                           t3=cal(t2,v[i4],f3);

                           if (isEqual(t3,result))    // 将24改成result

                            {

                              char *fs="((%d%c%d)%c%d)%c%d=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result); //增加resul参数 ,对应增加的%d 

                              count++;

                            }

                           // 第2种情况(a 。b)。(c。 d) 开始计算 :

                           t1=cal(v[i1],v[i2],f1);

                           t2=cal(v[i3],v[i4],f3);

                           t3=cal(t1,t2,f2);

                           if (isEqual(t3,result))      // 将24改成result

                            {

                              char *fs="(%d%c%d)%c(%d%c%d)=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                              count++;

                             }

                           // 第3种情况 (a。(b。c))。d  开始计算 :

                           t1=cal(v[i2],v[i3],f2);

                           t2=cal(v[i1],t1,f1);

                           t3=cal(t2,v[i4],f3);

                           if (isEqual(t3,result))    // 将24改成result

                            {

                              char *fs="(%d%c(%d%c%d))%c%d=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                              count++;

                            }

                           // 第4种情况  a。((b。c)。d ) 开始计算:

                           t1=cal(v[i2],v[i3],f2);

                           t2=cal(t1,v[i4],f3);

                           t3=cal(v[i1],t2,f1);

                           if (isEqual(t3,result))    // 将24改成result

                           {

                             char *fs="%d%c((%d%c%d)%c%d)=%d\n";  //将24改成%d 

                             printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                             count++;

                           }

                           // 第5种情况 a。(b。(c。d)) 开始计算:

                           t1=cal(v[i3],v[i4],f3);

                           t2=cal(v[i2],t1,f2);

                           t3=cal(v[i1],t2,f1);

                           if (isEqual(t3,result))    // 运算后是否为result

                           {

                             char *fs="%d%c(%d%c(%d%c%d))=%d\n";  //将24改成%d 

                             printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                             count++;

                           }
  

                         }

                   }
2015-06-25 18:27
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
求大神 请教一下
2015-06-25 21:13
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
回复 4楼 hjx1120
差不多就是这个意思,要求能穷举出所有的排序。四则运算也包含小括号
2015-06-25 22:28
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
回复 6楼 边小白
这个可能是我的理解错误,如何优化这个程序的算法,达到排除部分重复的结果式,例如某些带括号的式子与不带括号的式子重复了,要排除这些部分重复的式子。
2015-06-25 23:22
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
回复 8楼 边小白
就是例如1+1+1+1 等同于 1+((1+1)+1) 这种  ,两个式子表达的概念都是一样,结果也是一样,我要的就是排除这重复的式子的解决办法。源代码发楼下
2015-06-25 23:40
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
程序代码:
#include<stdio.h>   
#include<string.h>
#include<stdlib.h>

const char serial[][4] = {"", "", "", ""};//通过数组显示序号 


int input(int x) 
{
    int m;
    int flag,i;
    char t[100];  //先采用字符串输入 限定输入的每一位都在1~1000之间,保证输入的是数字、避免输入的是字母或者其他字符
    do{
        flag=0;   
        fflush(stdin);            //功能:清空输入缓冲区,通常是为了确保不影响后面的数据读取
        gets(t);
        for(i=0;(size_t)i<strlen(t);i++)    //strlen函数,其功能是求字符串长度
        {
            if(t[i]<'0' ||t[i]>'9')
            {
                flag=1;                        //定义的标示
                printf("输入有误,请重新输入\n>> %s:", serial[x]);
                break;
            }      
        }
        if(!flag)
        {
            m=atoi(t);//C语言库函数名atoi功能: 把字符串转换成整型数得到全局n的值
               if(m<=0||m>=1000)  
             {
                printf("输入有误,请重新输入\n>> %s:", serial[x]);
                flag=1;  
            }
        }
    }while(flag);
    
    return m;
}


//**************************输入输出定义********************************//
double  cal(double a,double b,int op)      // op: 0:+,1:-,2:*,3:/运算的优先级
{
        switch (op)                        // +-x 运算
         {
           case 0:  return(a+b);
           case 1:  return(a-b);
           case 2:  return(a*b);
         }
        if (b==0.0)                       //  考虑分母为0
            return(999.0);
        else                               //否则进行除法运算
            return(a/b);
}


//在运算过程中除法的特殊性——除数不能为零。因为可能会用到除法,所以要考虑精度问题
//这里通过结果减去输入数取绝对值与一个接近0的小数(如0.001)比较,如小于它,即可判定结果是输入数。

int    isEqual(double d1,double d2)           // 两个双精度浮点数是否近似相等   //isEqual函数功能是判断若干个给定的数组容量是否是相等的
{
        double d=d1-d2;                        //两个数做差取绝对值然后跟指定的精度进行比较 
        if (d<0) d=-d;                        // 求绝对值
        return(d<=0.001);                     //返回为1或者0 取决于d<=0.001是否成立。若成立则返回1,即判定预算结果等于输入值

}





/**************************计算result*************************/
void   D24(int v[], int result)          // 穷举法求结果,增加变量result 

{
       char op[4]={'+','-','*','/'};             //  +:0  -:1 *:2  /:3
       int count=0;// 计数成功次数
       int i1,i2,i3,i4;
       int f1,f2,f3;
       

//-----------四重循环开始穷举四个数字的位置: 4!=24 种  A44--------------------------
       
       for (i1=0;i1<4;i1++)                  //i表示v[i]下标的位置 i1 i2 i3 i4不能相等(分别为0 1 2 3)  表示4个数排列在数组4个不同的位置上

        for (i2=0;i2<4;i2++)                 // 四重循环对四个数穷举

          if (i2!=i1)

          for (i3=0;i3<4;i3++)

            if (i3!=i2 && i3!=i1)

            for (i4=0;i4<4;i4++)

               if (i4!=i3 && i4!=i2 && i4!=i1)

                 {

//-----------三重循环开始穷举三个运算符: 4X4X4=64 种 +-*/可以重复使用---------------------------

                   for (f1=0;f1<4;f1++)      // 三重循环对运算符穷举,f表示op[f]中的元素

                     for (f2=0;f2<4;f2++)

                       for (f3=0;f3<4;f3++)  // 运算符 f1,f2,f3

                         {                       // 对运算优先级直接列举(5种)

//-----------未用循环,直接穷举三个运算符的优先级: 3!-1=5种( 3*2-1=5)-------------------

                           double t1,t2,t3;      // 存放计算的中间值  两个两个按优先级进行计算

                           // 第1种情况  ((a 。b)。c)。d  :

                           t1=cal(v[i1],v[i2],f1);

                           t2=cal(t1,v[i3],f2);

                           t3=cal(t2,v[i4],f3);

                           if (isEqual(t3,result))    // 将24改成result

                            {

                              char *fs="((%d%c%d)%c%d)%c%d=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result); //增加resul参数 ,对应增加的%d 

                              count++;

                            }

                           // 第2种情况(a 。b)。(c。 d) 开始计算 :

                           t1=cal(v[i1],v[i2],f1);

                           t2=cal(v[i3],v[i4],f3);

                           t3=cal(t1,t2,f2);

                           if (isEqual(t3,result))      // 将24改成result

                            {

                              char *fs="(%d%c%d)%c(%d%c%d)=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                              count++;

                             }

                           // 第3种情况 (a。(b。c))。d  开始计算 :

                           t1=cal(v[i2],v[i3],f2);

                           t2=cal(v[i1],t1,f1);

                           t3=cal(t2,v[i4],f3);

                           if (isEqual(t3,result))    // 将24改成result

                            {

                              char *fs="(%d%c(%d%c%d))%c%d=%d\n";  //将24改成%d 

                              printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                              count++;

                            }

                           // 第4种情况  a。((b。c)。d ) 开始计算:

                           t1=cal(v[i2],v[i3],f2);

                           t2=cal(t1,v[i4],f3);

                           t3=cal(v[i1],t2,f1);

                           if (isEqual(t3,result))    // 将24改成result

                           {

                             char *fs="%d%c((%d%c%d)%c%d)=%d\n";  //将24改成%d 

                             printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                             count++;

                           }

                           // 第5种情况 a。(b。(c。d)) 开始计算:

                           t1=cal(v[i3],v[i4],f3);

                           t2=cal(v[i2],t1,f2);

                           t3=cal(v[i1],t2,f1);

                           if (isEqual(t3,result))    // 运算后是否为result

                           {

                             char *fs="%d%c(%d%c(%d%c%d))=%d\n";  //将24改成%d 

                             printf(fs,v[i1],op[f1],v[i2],op[f2],v[i3],op[f3],v[i4],result);//增加resul参数 ,对应增加的%d 

                             count++;

                           }
  

                         }

                   }

//-------------- 穷举结束---------------------------
                if (count==0)
                    printf("\n抱歉,无法算出结果%d\n\n\n", result);
                else
                    printf("\n共找到 %d 条算式\n\n\n",count);

}


int main()
{
        int i, result, v[4];
        char c;
        do{
            printf("\t\t\t*************************************\n ");
            printf("\t\t\t*       计算指定数值的问题程序      *\n");
            printf("\t\t\t*************************************\n ");
             
             printf("输入四个整数(1,1000)之间:\n");
               for(i = 0; i < 4; i++)
               {
                    printf(">> %s:", serial[i]);
                v[i] = input(i);
            }
            printf("您所输入的四个整数分别为:%d  %d  %d  %d\n",v[0],v[1],v[2],v[3]);
            printf("输入想求得的结果:");
             scanf("%d", &result);    //增加的结果输入语句
             D24(v, result);           //增加的参数result
            printf("是否继续?y/n\n>>");
            fflush(stdin);
             scanf("%c",&c);
            while(c!='y'&&c!='n')
            {
              printf("输入有误请选择y或者n\n>>");
              fflush(stdin);          //功能:清空输入缓冲区,通常是为了确保不影响后面的数据读取
              scanf("%c",&c);
            }
        }while(c=='y');
        printf("--------------------------------再见--------------------------\n");
        return 0;
}
2015-06-25 23:41
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
回复 11楼 边小白
那这个代码要如何改动呢?
2015-06-25 23:45
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
回复 13楼 边小白
这是我借鉴的代码,正在理解中,所以不太会修改。
2015-06-26 00:01
流光溢彩丿
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2015-6-3
收藏
得分:0 
求大神帮我啊
2015-06-26 12:58
快速回复:穷举法优化的问题求解,求个大神。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.036409 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved