枚举算法_填运算符（5 5 5 5 5=5）(C语言)

￡神魔★判官ぃ 2021-11-29 15:00 596阅读 0赞

5 5 5 5 5=5  
求解其有多少种可能性？  
例如：5+5-5\*5/5=5  
由于算术表达式地特殊性，在编程求解这个算式时，需要注意以下几点：

1.  当填入除号时，要求右侧地数不能为0。
2.  乘除地运算级别比加减高。

总体思路  
对于这种问题需要用到枚举的思想，也就是遍历所有的符号分配方式，判断是否满足结果，若满足则视为一个合理的分配方案进行输出。

详细设计  
♦ 我们所研究的对象是符号分配，所以要将注意力放在符号上，为了方便在后边判断符号添加的合理性，我们最好要有将符号存储在一个字符数组中的意识。且还需要一个数组用来存放符号数组中所有排列组合的下标集（0代表‘+’；1代表‘-’；2代表‘\*’；3代表‘/’），然后对每一组进行循环排查。  
♦除数不能是0 通过一个判断语句进行筛选，当下标大于3时下一个数不能是0。  
♦优先级  
设置俩个变量，一个负责加减，另一个负责乘除，最后进行合并。

C语言相关代码：

#include<stdio.h>
    int main()
    {
    	int j,i[5]; //循环变量，数组i用来表示4个运算符 
    	int sign;   //累加运算时地符号 
    	int result;   //保存运算式的结果值 
    	int count=0;   //计数器，统计符合条件的方案 
    	int num[6];		//保存操作数 
    	float left,right;  //保存中间结果 
    	char oper[5]={' ','+','-','*','/'};  //运算符 
    	printf("请输入5个数："); 
    	for(j=1;j<=5;j++)
    	{
    		scanf("%d",&num[j]);
    	 } 
    	 printf("请输入结果："); 
    	 scanf("%d",&result);
    	 for(i[1]=1;i[1]<=4;i[1]++) //循环4种运算符，1表示+，2表示-，3表示*，4表示/ 
    	 {
    	 	if((i[1]<4)||(num[2]!=0)) //运算符若是/， 则第2个运算数 不能为0 
    	 	{
    	 		for(i[2]=1;i[2]<=4;i[2]++)
    	 			{
    	 				if((i[2]<4)||(num[3]!=0))
    	 					{
    	 						for(i[3]=1;i[3]<=4;i[3]++)
    	                           {
    	 								if((i[3]<4)||(num[4]!=0))
    	 									{
    	 										for(i[4]=1;i[4]<=4;i[4]++)
    	                                           {
    	 												if((i[4]<4)||(num[5]!=0))
    	 													{
    	 														left=0;
    															right=num[1];
    															sign=1;
    															for(j=1;j<=4;j++)
    															{
    																switch(oper[i[j]])
    																{
    																	case '+':
    																		left=left+sign*right;
    																		sign=1;
    																		right=num[j+1];
    																		break;
    																	case '-':
    																		left=left+sign*right;
    																		sign=-1;//符号位 
    																		right=num[j+1];
    																		break;
    																	case '*':
    																		right=right*num[j+1];
    																		break;
    																	case '/':
    																		right=right/num[j+1];
    																		break;
    																}
    															}
    															if(left+sign*right==result)
    															{
    																count++;
    																printf("%3d: ",count);
    																for(j=1;j<=4;j++)
    																	printf("%d%c",num[j],oper[i[j]]);
    																printf("%d=%d\n",num[5],result);	
    															 } 				
    														 }
    	                                           } 
    		 								}
    	                              } 
    		 				}
    	 			 } 
    		 }
    		 
    	  }
    	  if(count==0)
    	  		printf("没有符合要求地方法！\n");
    	  return 0; 
    }