小学奥数与信奥
题目
3.
把4分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
把5分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
把6分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
把8分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
思考
穷举法即可 2019-8-26 16:55
程序输出如下
把4分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
4
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
cnt=4
把5分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
5
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
cnt=6
把6分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
6
6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=1+5
6=2+2+2
6=2+4
6=3+3
cnt=10
把8分拆成几个数相加的形式(0不考虑作为加数)，有多少种不同的分拆方式？
8
8=1+1+1+1+1+1+1+1
8=1+1+1+1+1+1+2
8=1+1+1+1+1+3
8=1+1+1+1+2+2
8=1+1+1+1+4
8=1+1+1+2+3
8=1+1+1+5
8=1+1+2+2+2
8=1+1+2+4
8=1+1+3+3
8=1+1+6
8=1+2+2+3
8=1+2+5
8=1+3+4
8=1+7
8=2+2+2+2
8=2+2+4
8=2+3+3
8=2+6
8=3+5
8=4+4
cnt=21
对比小学奥数该题答案的呈现形式，能明显感觉到，信奥的思路与小学奥数的思路还是有很大不同的．
以下为程序代码
#include <stdio.h>
int n,a[15],cnt=0;
void dfs(int step,int sum){
int i,j;
if(sum>n)return;//剪枝
if(sum==n){
cnt++;
printf("%d=%d",n,a[1]);
for(j=2;j<=step-1;j++)printf("+%d",a[j]);
printf("\n");
}
for(i=a[step-1];i<n;i++){//此处错写成for(i=a[step-1]+1;i<n;i++){
a[step]=i;
dfs(step+1,sum+i);
}
}
int main(){
scanf("%d",&n);
a[0]=1,dfs(1,0);//此处错写成a[0]=0,dfs(1,0);
printf("cnt=%d\n",cnt);
return 0;
}
题目
2.将1-9九个数平均分成3组，使每组的3个数相加的和相等，这样的分法有几种?
思考
为何只有２种，不会证明，那就穷举法 2019-8-26 16:19
程序输出如下
ans 1
1+5+9=15
2+6+7=15
3+4+8=15
ans 2
1+6+8=15
2+4+9=15
3+5+7=15
程序代码如下：
#include <stdio.h>
#include <string.h>
int a[15],ans=0,vis[15];
void dfs(int step){
int i,j,b,c,d;
if(step==9+1&&a[1]<a[2]&&a[2]<a[3]&&a[4]<a[5]&&a[5]<a[6]&&a[7]<a[8]&&a[8]<a[9]&&a[1]<a[4]&&a[4]<a[7]){
b=a[1]+a[2]+a[3],c=a[4]+a[5]+a[6],d=a[7]+a[8]+a[9];
if(b==c&&b==d){
ans++,printf("ans %d\n",ans);
printf("%d+%d+%d=%d\n",a[1],a[2],a[3],b);
printf("%d+%d+%d=%d\n",a[4],a[5],a[6],b);
printf("%d+%d+%d=%d\n",a[7],a[8],a[9],b);
}
return;
}
for(i=1;i<=9;i++)
if(!vis[i]){
vis[i]=1;
a[step]=i;
dfs(step+1);
vis[i]=0;
}
}
int main(){
memset(vis,0,sizeof(vis));
dfs(1);
return 0;
}
题目
1.在1,2,3,4,5,6,7,8,9之间填上“+”或“-”（位置相邻的两个数或三个数可以看成一个数），使算式成立。
1 2 3 4 5 6 7 8 9
思考过程如下：
本人答案12+3-4+5+67+8+9=100
参考答案123-45-67+89=100
两者答案不同，激起了我的好奇心，究竟有多少种答案，每个答案表达式又是怎样。于是停下手头的学习，开始研究。发现问题，解决问题，比学习问题更重要。
1|2|3|4|5|6|7|8|9，之间有8个空隙，每个空隙可放“+”，“-”，或不放，3种情况。共有3^8=6561种情况，计算机1s以内轻松完成。
2个方案，要么写8个for循环，要么写个深搜，决定选择后者。
版本2
//准备采用3进制的方式开始处理此题
//3进制马上测试,3进制数据生成,成功.
//继续下一部分功能.
//有了深搜的经验,代码很快编好,输出11个等式,如下.
123-45-67+89=100
12-3-4+5-6+7+89=100
12+3+4+5-6-7+89=100
123+4-5+67-89=100
1+2+3-4+5+6+78+9=100
12+3-4+5+67+8+9=100
1+23-4+56+7+8+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
//2019-2-18 16:42
#include <stdio.h>
#include <string.h>
int sign[15];//3进制 0无符号,1"+",2"-"
int main(){
int i,j,sum,delta;
memset(sign,0,sizeof(sign));
while(sign[9]==0){
sign[0]=1,sign[1]+=1,sum=0,delta=0;
for(i=1;i<9;i++)sign[i+1]+=sign[i]/3,sign[i]%=3;
for(i=1;i<9;i++){
if(sign[i]==1||sign[i]==2){//i数字之后符号为"+"或"-"
if(sign[i-1]==1)sum+=i,delta=0;
else if(sign[i-1]==2)sum-=i,delta=0;
else if(sign[i-1]==0){
delta=delta*10+i;
j=i-1;
while(sign[j]==0)j--;
if(sign[j]==1)sum+=delta,delta=0;
else if(sign[j]==2)sum-=delta,delta=0;
}
}else if(sign[i]==0)delta=delta*10+i;//i数字之后无符号
}
//最后一个数字9处理,因9之后无符号.需单独处理
if(sign[8]==1)sum+=9;
else if(sign[8]==2)sum-=9;
else if(sign[8]==0){
j=8,delta=delta*10+9;
while(sign[j]==0)j--;
if(sign[j]==1)sum+=delta;
else if(sign[j]==2)sum-=delta;
}
if(sum==100){
for(i=1;i<9;i++){
printf("%d",i);
if(sign[i]==1)printf("+");
else if(sign[i]==2)printf("-");
}
printf("9=100\n");
}
}
return 0;
}
版本1
//核心思想,遇到"+"或"-",才开始计算之前的数据
//编着编者,感觉不对劲,还是决定开一个数组sign[i]用来存储i之后的符号情况
//sign[step]=1,j=step-1;while(sign[j]==0)j--;if(sign[j]==1)dfs(step+1,sum+delta*10+step,0);else if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);//此处写成sign[step]=1,j=step-1;while(sign[j]==0)j--;{if(sign[j]==1)dfs(step+1,sum+delta*10+step,0);}//"+"
//sign[step]=2,j=step-1;while(sign[j]==0)j--;if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);else if(sign[j]==1)dfs(step+1,sum+(delta*10+step),0);//此处写成sign[step]=2,j=step-1;while(sign[j]==0)j--;if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);//"-"
//上述2行的排查,经历了观察输出数据,静态阅读代码,大约60分钟.2019-2-18 15:55
//深搜代码写得挺狼狈,输出结果如下:
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100
共计11个答案
//原以为20分钟能解决的问题,整整用去了半天,不过,挺值的,实实在在的解决了实际问题.2019-2-18 15:59
//多次想放弃该深搜算法,采用3进制的办法,但想着此处深搜弄不出,以后更复杂的问题就更难用深搜弄出,硬着头皮,调出来了.
#include <stdio.h>
#include <string.h>
int sign[15];//sign[i]//i之后的符号,无符号0,"+"1,"-"2
void dfs(int step,int sum,int delta){//step 当前步骤,sum是在step步骤之前计算的和,delta是到step步骤之前未计算的数
int i,j;
if(step==9){
if(sign[step-1]==1)sum+=step;
if(sign[step-1]==2)sum-=step;
if(sign[step-1]==0){j=step-1;while(sign[j]==0)j--;if(sign[j]==1)sum+=delta*10+step;if(sign[j]==2)sum-=(delta*10+step);}
if(sum==100)
{
for(j=1;j<9;j++){
printf("%d",j);
if(sign[j]==1)printf("+");
if(sign[j]==2)printf("-");
}
printf("9=100\n");
}
return ;
}
if(sign[step-1]==1){//"+"
sign[step]=1,dfs(step+1,sum+step,0);//"+"
sign[step]=2,dfs(step+1,sum+step,0);//"-"
sign[step]=0,dfs(step+1,sum,delta*10+step);//无符号
}
if(sign[step-1]==2){//"-"
sign[step]=1,dfs(step+1,sum-step,0);//"+"
sign[step]=2,dfs(step+1,sum-step,0);//"-"
sign[step]=0,dfs(step+1,sum,delta*10+step);//无符号
}
if(sign[step-1]==0){
sign[step]=1,j=step-1;while(sign[j]==0)j--;if(sign[j]==1)dfs(step+1,sum+delta*10+step,0);else if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);//此处写成sign[step]=1,j=step-1;while(sign[j]==0)j--;{if(sign[j]==1)dfs(step+1,sum+delta*10+step,0);}//"+"
sign[step]=2,j=step-1;while(sign[j]==0)j--;if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);else if(sign[j]==1)dfs(step+1,sum+(delta*10+step),0);//此处写成sign[step]=2,j=step-1;while(sign[j]==0)j--;if(sign[j]==2)dfs(step+1,sum-(delta*10+step),0);//"-"
sign[step]=0,dfs(step+1,sum,delta*10+step);//不填符号
}
}
int main(){
memset(sign,0,sizeof(sign));
sign[0]=1;//"+" .初始化为"+"
dfs(1,0,0);
return 0;
}
