上课内容

第9次课 主题《【回朔法】》

例1

设计一个算法在1，2，……9(顺序不变)数值之间插入+或者-或者什么都不插入，
使得计算结果总是100的程序。输出所有的情况。例如1+2+34-5+67-8+9=100。
方法1
处理：“什么都不插入”，使用空格来表示！

1 对于程序而言，插入的对象是+ - 空格。表示是’+’ ‘-’ ‘ ’
定义一个字符数组来存放这3个符号
char op[3]={ ’+’,‘-’,‘ ’};
op[0]=’+’;
op[1]=’-‘;
op[2]=’ ‘;
区分3个符号完全可以用op数组的下标来区分0 1 2 对应 + - 空格
2 上述提到整个一个完整表达式看作都是字符型
定义一个字符数组用来存放整个表达式
char str[20];//20足够长
3 因为只有9个数值之间的共8个符号需要讨论分别可能是+ - 空格中的其中一个
int a[9];//提醒我只用a[1]到a[8]，因为这样编号方便处理
a[1]也就是第一个数值之后的符号【+ - 空格中的其中一个】
a[1]的取值呢？也就是op数组的下标范围[0,2]
……
a[8]的取值呢？也就是op数组的下标范围[0,2]
4 上述第3点描述结束后，应该清楚我想要用什么写法了吧？枚举！
5 进一步处理最开始的分析

	1+2+34-5+67-8+9=100
	整个现有的一堆东西，最终全部看成字符型，因为+-空格符号
	很容联想到大一曾经学过的一个程序1+2+3+。。。+100
	变成s=0+1+2+3+……+100
　	　	1	+	2	+	3		4	-	5	+	6	 	7	-	8	+	9	
0	+	1	+	2	+	3		4	-	5	+	6	 	7	-	8	+	9	
	str[0]	str[1]	str[2]	……															
	所以str[0]=’+’;
	

所以str[0]=’+’;
6 所以在存储完str[0]之后，再之后数值字符和+ - 空格符号的处理。一次性处理2个。
比如str[2]中存放的是+，同时把str[1]=’1’也给存储了
但是如果是3后面是空格的话，是不存储空格的，直接存储字符‘3’就可以了嘛
【这个部分是根据a数组中的值，来决定2选1的处理】
例如考虑第一个数值1 及其后面的 可能字符的操作如下。

//a[1]的取值呢？也就是op数组的下标范围[0,2]
//如果是+或者-，是先放输入数值字符再放运算符

if(op[a[1]]=='+' || op[a[1]]=='-') 
		{
			j++;
			str[j]=1+48;
			j++;
			str[j]=op[a[1]];
		}
		//如果是空格，直接把对应的数值存入数组，且空格不存 
		if(op[a[1]]==' ')
		{
			j++;
			str[j]=1+48;
		}

注意：

上述过程是1配其后的字符，2配其后的字符……所以这样处理会把最后的数字9给弄成单身。所以9单独在存放，但是存放完了之后，记得字符串末尾需要加一个\0。

提醒：

之所以用数组a,其用的是a[1]到a[8]，其实因1-8刚好就是数字的前8个，可以用数组a标号来表示。

因为char qian=str[0];
所以接下来的计算应该从str[1]开始到str[19]

当求得1在zuhe变量中后，还不能运算，要看它之后的字符，如果是+或者-，则证明1可以和其前面的运算符进行运算。

最后完整代码

蛮力代码

#include<stdio.h>

int main()
{
	char op[3]={ '+','-',' '};
	char str[20];//20足够长,定义一个字符数组用来存放整个表达式
	int a[9],i,j;
	
	for(a[1]=0;a[1]<=2;a[1]++)
	for(a[2]=0;a[2]<=2;a[2]++)
	for(a[3]=0;a[3]<=2;a[3]++)
	for(a[4]=0;a[4]<=2;a[4]++)
	for(a[5]=0;a[5]<=2;a[5]++)
	for(a[6]=0;a[6]<=2;a[6]++)
	for(a[7]=0;a[7]<=2;a[7]++)
	for(a[8]=0;a[8]<=2;a[8]++)
	{
		//把数字变对应数字字符和运算符一起存入str数组中，但是空格不存！
		//不存储空格，好处是存储结束后的计算过程方便。
		int j=0;
		str[0]='+';
		
		for(i=1;i<=8;i++)
		{
			//接下来涉及到的处理是
			//a[i]的取值呢？也就是op数组的下标范围[0,2]
			//如果是+或者-，是先放输入数值字符再放运算符 
			if(op[a[i]]=='+' || op[a[i]]=='-') 
			{
				j++;
				str[j]=i+48;
				j++;
				str[j]=op[a[i]];
			}
			//如果是空格，直接把对应的数值存入数组，且空格不存 
			if(op[a[i]]==' ')
			{
				j++;
				str[j]=i+48;
			}
		}
		//上述过程是1配其后的字符，2配其后的字符……所以这样处理会把最后的数字9给弄成单身。所以9单独在存放，但是存放完了之后，记得字符串末尾需要加一个\0。
		j++;
		str[j]=9+48;
		j++;
		str[j]='\0';
		
		//开始计算
		//计算过程存在着数值需要组合的问题3和4要组合成34
		//记得存储的是字符3和字符4，先要变成数字3和4才能组合成34
		//因为34组成之后才能用数字前面的运算符 
		int zuhe;
		int sum;
		char qian=str[0];//存储前一个运算符,初始值是一开始的+号
		zuhe=0;
		sum=0;
		
		for(i=1;i<=19;i++)
		{
			if(str[i]>=48 && str[i]<=57)
			{
				zuhe=zuhe*10+(str[i]-48);	
			}
			else if(str[i]=='+' || str[i]=='-')//说明组合结束，组合的数值可以和前面的运算符进行计算 
			{
				if(qian=='+')
					sum=sum+zuhe;
				if(qian=='-')
					sum=sum-zuhe;
					
				//说明某个组合的值已经使用了，且这个zuhe清零
				zuhe=0;
				//qian的运算符已经使用了，这个时候前一个运算符应该是现在这个str[i]作为运算符 
				qian=str[i];	
			}	
		} 
		
		//最后那个组合变量中值其后已经没有运算符。所以在上述循环中，最后zuhe中的值还没有算进去
		if(qian=='+')
			sum=sum+zuhe;
		if(qian=='-')
			sum=sum-zuhe; 
		
		//最后讨论sum是否等于100，但是因为我一开始补了一个+，所以输出的时候是不能有它，拿空格填写 
		if(sum==100)
		{
			str[0]=' ';
			printf("%s=100\n",str);
		}		 
	}
	return 0;	
}

注明

太长了，不用

发现：

1 上述写法使用的蛮力法
2 融入了数字字符和数值之间的变化
3 1+2+3+……+100的这个程序的解题思想。
4 此题的解题过程太长了，而且繁琐。
是否有更好的别的方法来实现呢？

回顾一个经典例子。Fibonacci数列。
曾经写过数组版本，写过递归版本。

1 如果要求5的阶乘，必须分成f(5)=f(3)+f(4)
2 要算5的阶乘，得先算3的阶乘和4的阶乘
3 而3的阶乘 f(3)=f(1)+f(2)
而4的阶乘 f(4)=f(2)+f(3)
4 要算4的阶乘，得先算3的阶乘
5而3的阶乘 f(3)=f(1)+f(2)
6 注意：都知道fibonacci的前2个数值是已知的1和1.
7 【5而3的阶乘 f(3)=f(1)+f(2)】计算出来，
【而4的阶乘 f(4)=f(2)+f(3)】再计算出来
8 而另外一边【而3的阶乘 f(3)=f(1)+f(2)】是也再计算一次3的阶乘。
9 【1 如果要求5的阶乘，必须分成f(5)=f(3)+f(4)】它也算出来了。
黄色区域叫：递推
蓝色区域叫：递归
归：回去。【回朔法】

就好比小朋友玩儿东西
要玩儿：拿【自己拿，别人拿给他】
不玩儿了：从视频中看出，【丢，放在玩具应该放的地方】这里就是凸显出回朔法的：回。
今天是如此，明天呢，玩具多的时候呢。
【还有：丢，放在玩具应该放的地方】都可能存在一种情况。玩具可能损坏。【意味着可能需要修改某对象的值的问题。】

今天接下来用回朔法的思路来编写程序
【其实刚才举例中fibonacci和小朋友玩儿玩具拿和丢，其实都可以理解为循环，或者是 递归】
强调的是回的处理！【还是会用到递归】
问大家一个问题：1-9之间填写 + 或者 – 或者 空格 这个分析过程是否可以用树型结构描述？
完全可以用树型结构描述（三叉树）

最终还是要融入本周第一次课所讲述的内容：深度优先算法！
此题处理有区别于前一个题目。
我不会在1之前增加+号了。
问题直接从1开始。。。。。。。。。
这里
sum的初始值是a[0];

把1强制的看作是独立的数值【这里是有风险的，因为还要参考1后的运算符】

如果是+ 或者 - 这里强制处理就很ok

如果是空格，那这里处理就明显不对。

注意：

a[0] 1
a[1] 2
a[2] 3
a[3] 4
a[4] 5
a[5] 6
a[6] 7
a[7] 8
a[8] 9

调用fun函数是从1开始讨论

执行

sum=sum+a[1]; 【也就是1+2】

现在第一次讨论是 1和2之间是+的情况【一路走到黑】

但是如果走不下去，则层层返回

说明之前sum=sum+a[1]; 【+2 处理的不对】

只能变成原本的sum，不带2的sum

所以 最后写了 sum=sum-a[1];

相当于sum要还原

---

因为递归的写法，所以每层的i 在处理+的时候都要考虑走不下去，
返回上一层，得减去前面加过的数值。

在考虑第0位置的数值1 是直接给sum，这里是有风险
【如果1和2之间是空格】
之前sum里面给的1作为初始值不对的，所以，把sum之前存的值去掉。之前备front，就是为sum做减去处理准备的。

可能
sum=0

也可能是变成原本sum

像这里 sum=0

1和2重新组合成12，再作为sum的新的初始值

---

【就是因为sum初始值直接给了a[0],也就是1，而是有风险的】
既然一开始有风险，在整个递归过程中都有风险。

比如12作为sum的初始值，那是否有风险呢？也有啊，万一2后面也是空。相当于1 2 3要组合成123了！

递归代码

#include<stdio.h>

fun(char op[],int a[],int sum,int front,int i)//已知数组op，已知数组a，已知求和，从谁开始求和，标号 
{
	if(i==9)//而数组a的实际编号是0-8，所以到9说明遍历结束
	{
		if(sum==100)
		{
			int j;
			//数值是9个，最多8个其他全部都是运算符，
			//成组合【数值+运算符。最后一个数值单了】 
			//成组合【运算符+数值。第一个数值单了】 
			printf("%d",a[0]);//输出1
			for(j=1;j<9;j++)
			{
				if(op[j]=='+' || op[j]=='-')
				{
					printf("%c",op[j]);
					printf("%d",a[j]);
				}
				else 
					printf("%d",a[j]);
			}
			printf("\n");	
		}	
	}
	else
	{
		int temp; 
		//说明没有遍历完。所以这里对于每次都要讨论三种情况 + - 空格的时候
		//上述三种情况不好意思是都要讨论而不是三选一
		//理由刚才描述的三叉树就明白了
		//1 讨论是+
		op[i]='+';
		sum=sum+a[i];
		fun(op,a,sum,a[i],i+1);//如果递归结束后，是要回的
		sum=sum-a[i];//原本sum加的部分，还原sum，必须减去【这里体现的就是回朔法处理】 
		
		//2 讨论是- 
		op[i]='-';
		sum=sum-a[i];
		fun(op,a,sum,-a[i],i+1);//如果递归结束后，是要回的，记得要带运算符 
		sum=sum+a[i];//原本sum加的部分，还原sum，必须减去【这里体现的就是回朔法处理】
		
		//3 讨论是空格
		op[i]=' ';
		sum=sum-front;//前去前面的数值。
		if(front>0) //就要组合成新的数值 比如-2 3组合或者 +2 3 组合
			temp=front*10+a[i];//就要组合成新的数值 +2 3 组合 成为23 
		else
			temp=front*10-a[i]; //就要组合成新的数值 -2 3 组合 -2*10-3 成为-23
		//新的组成了且在temp中
		sum=sum+temp;//这一步出来也是有风险的，再之后的数值呢和对应的运算符呢 
		fun(op,a,sum,temp,i+1);//如果递归结束后，是要回的
		sum=sum-temp;//原本sum加的部分，还原sum，必须减去【这里体现的就是回朔法处理】
		sum=sum+front;//而上面sum=sum-front;还sum还减去了一个front，也必须还原 
	}		
}

int main()
{
	int a[9]={1,2,3,4,5,6,7,8,9};
	char op[9];
	fun(op,a,a[0],a[0],1);
	//这个处理是1之间不加+的，从1之后的那个数值开始计算 ,
	//实际讨论是从数值中第2个【数组中的第1开始讨论】 
	return 0;	
}

评价

做法没法改，只能暴力，我只是改成了 长度 数列 目标值 手动输入的版本

更新版

#include<iostream>


using namespace std;

const int N=1e4;
int a[N];
char ch[N];
int n,kNum;

void func(int sum,int begin,int u)
{
    if(u == n)
    {
        if(sum == kNum)
        {
            cout<<a[1];
            for(int i=2;i<=n;i++)
                if(ch[i]=='+'||ch[i]=='-')cout<<ch[i]<<a[i];
                else cout<<a[i];
            cout<<endl;
        }
    return ;
    }
    
    else 
    {
        ch[u]='+';
        sum+=a[u];
        func(sum,a[u],u+1);
        sum-=a[u];
        
        ch[u]='-';
        sum-=a[u];
        func(sum,-a[u],u+1);
        sum+=a[u];
        
        ch[u]=' ';
        sum-=begin;
        int tmpN=0;
        if(begin)tmpN=begin*10+a[u];
        else tmpN=begin*10-a[u];
        sum+=tmpN;
        func(sum,tmpN,u+1);
        sum-=tmpN;
        sum+=begin;
    }
}

int main()
{
    cin>>n>>kNum;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    
    func(0,1,1);
    
    return 0;
}

测试数据

9 100
1 2 3 4 5 6 7 8 9

答案

1+23-4+5+67+89
1-2+34-5-6+789
1-2-3+45+67-89
12+3-4+5+6+789
12+34-5+67-89
123+45-6-789
12-34+56+789
1+2+3-4+5+6+789
1+2+34-5+67-89
1+23-4+56+7+89
12+3-4-5-6-7+89
12+3-45+6+7+89
12+34-56+7-89
12-3+4-5-6+7-89
12-3-4+5+6-7-89