Question

c语言123456789=100编程思想

题目是:在这九个数中间添加+,-符号，使得1 2 3 4 5 6 7 8 9 ＝100成立.
现已有完整程序,但是算法思想不理解,请高手针对下面程序给出详细算法思想.好的话可以追加分数.
main()
{
char op,str[80];
int i,j,s,n,m,ptr;
for (i=0;i<=6561;i++) /*i是每一种枚举的情况，把i分解为八位3进制数，每一位表示每一个位置的符号*/
{
s=0; /*该方式下的和*/
m=1; /*作操作数*/
n=i; /*获取i在3进制下的每一位会破坏i，所以借用变量n来获取*/
op='+'; /*第一次操作方式为+*/
ptr=0; /*指针用来记录运算过程*/
str[ptr++]='1'; /*首先记录一个1*/
for (j=2;j<=9;j++) /*八次循环，每次的下一个操作数是j*/
{
if (n%3) /*3进制下的第j-1位数，如果不是0，则要完成先前的操作*/
{
if (op=='+') s+=m; else s-=m;m=j;
}
switch(n%3) /*根据这一位的情况进行处理*/
{
case 0:m=m*10+j;break;
case 1:op='+';break;
case 2:op='-';break;
}
if (n%3) str[ptr++]=op; /*记录运算模式*/
str[ptr++]='0'+j;
n/=3;
}
if (op=='+') s+=m; else s-=m;
str[ptr]='\0';
if (s==100) printf("FOUND: %s=%d\n",str,s); /*判断是否满足*/
}
}
基本上懂了,但是如何用“n/3”和“n%3”实现在什么位置填加什么符号还请在详细解释一下.

Answer 1

就是个深度优先搜索。

枚举所有符号可能添加的情况。

{
s=0; /*该方式下的和*/
m=1; /*作操作数*/
n=i; /*获取i在3进制下的每一位会破坏i，所以借用变量n来获取*/
op='+'; /*第一次操作方式为+*/
ptr=0; /*指针用来记录运算过程*/
str[ptr++]='1'; /*首先记录一个1*/
for (j=2;j<=9;j++) /*八次循环，每次的下一个操作数是j*/
{
if (n%3) /*3进制下的第j-1位数，如果不是0，则要完成先前的操作*/
{
if (op=='+') s+=m; else s-=m;m=j;
}
这段是在做拆符号的事情，就是根据i的值确定那8个空格填什么
switch(n%3) /*根据这一位的情况进行处理*/
{
case 0:m=m*10+j;break;
case 1:op='+';break;
case 2:op='-';break;
}
if (n%3) str[ptr++]=op; /*记录运算模式*/
str[ptr++]='0'+j;
n/=3;
}
就是按照填好的符号，计算表达式的结果
然后就是判断是不是是100。

Answer 2

1. 模型表示
在1 2 3 4 5 6 7 8 9九个数字中插入“+”或“-”符号使得结果为100，实际上是有八个地方需要插入符号。用下划线表示可以填入符号的位置1_2_3_4_5_6_7_8_9=100：而这样问题就变成了在这8个地方插入适当的“+”“-”符号使等式成立。
2. 算法设计
为得出符合条件的符号插入方式，选择了深度优先搜索，枚举所有符号可能添加的情况并计算它们的和，如果和等于100则输出。因为有8个位置可以插入符号，并且符号有“+”“-”和无符号3种可能。所以采用一个8位的3进制数来表示更容易解决问题。8位的每一位对应一个位置，每一位3进制数为0、1、2分别表示无符号、“+”、“-”三种符号，所以3的8次方为6561，枚举这6561种情况的循环语句就是for(i=0;i<6561;i++)，程序就变得非常直观。另外如何对每个位置上使用什么符号来使等式成立则是本次设计的核心算法。我们选择8个允许添加操作符号的地方和在每个地方判断是否添加操作符号以及添加哪个操作符号。比如：以3的倍数开始的连续3个组合数，其第一个位置上依次为空、“+”和“-”，而从第二个到第八个位置上的选择则完全相同。
3. 程序实现
定义字符a,b用于记录操作方式和运算过程，定义整形i,j,s,n,m,x，S存放和，m为操作数，n用于存放i在3进制下的值，x记录运算过程。
八次循环，根据i的值分析确定8个空格填什么符号。
for (j=2;j<=9;j++)
{
if (n%3) /*3
{
if (a=='+') s+=m; else s-=m;m=j;
}
按照填好的符号，计算表达式的结果
最后判断和是不是100。
switch(n%3)
{
case 0:m=m*10+j;break;
case 1:a='+';break;
case 2:a='-';break;
}
if (n%3) b[x++]=a;
b[x++]='0'+j;
n/=3;
}
if (a=='+') s+=m; else s-=m;
b[x]='\0';
if (s==100) printf("%s=%d\n",b,s);
}

Answer 3

1、这个算法不错，只是有一个小BUG，即
for (i=0;i<=6561;i++)应该写为
for (i=0;i<6561;i++)
而
for (j=2;j<=9;j++) 应该写为
for (j=2;j<9;j++)
2、这个算法的整体思想为其实就是枚举出所有可能的组合，并计算它们的和，如果等于100，则输出。那么它是如何枚举的呢？从算法注释及代码，我们可以看出算法用到三进制表示方法，也就是说“1 2 3 4 5 6 7 8 9”中每个允许添加操作符号的地方，都有三种可能：空、+和-，而总共有8个允许添加操作符号的地方，因此，组合数就是3^8=6561，这也解释了使用i<6561而不是i<=6561。
此外，它又是如何处理枚举的每种组合的呢？我们看到代码中出现了包含“n/3”和“n%3”这样的指令，很自然的想到它们正是在依次选择8个允许添加操作符号的地方和在每个地方判断是否添加操作符号以及添加哪个操作符号。比如：以3的倍数开始的连续3个组合数，其第一个位置上依次为空、+和-，而从第二个到第八个位置上的选择则完全相同。
下面具体解释一下指令“n/3”和“n%3”的作用。根据前面的说明，算法使用三进制表示方法来表示每种符号组合，举例来说，第123个符号组合的三进制8位表示方法为n=00011120(3)=123(10)，那么当“n%3”时，返回最低位的0，而“n/3”则返回0001112(3)，也就是说n右移了一位（三进制位），主要是方便下一次（计数器j）通过“n%3”计算新的最低位。现在将计数器j每次递增运行后，n的结果列示如下（第二列n/3之后n的最高位补0）：
j=2，n=00011120(3)，n%3=0
j=3，n=00001112(3)，n%3=2
j=4，n=00000111(3)，n%3=1
j=5，n=00000011(3)，n%3=1
j=6，n=00000001(3)，n%3=1
j=7，n=00000000(3)，n%3=0
j=8，n=00000000(3)，n%3=0

Answer 4

深搜

Answer 5

哈，以前几个月前写过一个，我把软件发到你的邮箱了，注意查收。下面是代码，用vc写的：
　　#include
"stdafx.h"
　　#include
　　#include
　　#include
"resource.h"
　　#include
"maindlg.h"
　　bool
winapi
main_proc(hwnd
hwnd,
uint
umsg,
wparam
wparam,
lparam
lparam)
　　{
　　switch(umsg)
　　{
　　handle_msg(hwnd,
wm_initdialog,
main_oninitdialog);
　　handle_msg(hwnd,
wm_command,
main_oncommand);
　　handle_msg(hwnd,wm_close,
main_onclose);
　　}
　　return
false;
　　}
　　bool
main_oninitdialog(hwnd
hwnd,
hwnd
hwndfocus,
lparam
lparam)
　　{
　　return
true;
　　}
　　void
main_oncommand(hwnd
hwnd,
int
id,
hwnd
hwndctl,
uint
codenotify)
　　{
　　tchar
str1[256],str2[256];
　　getdlgitemtext(hwnd,idc_edit1,str1,sizeof(str1));
　　getdlgitemtext(hwnd,idc_edit2,str2,sizeof(str2));
　　int
i1=atoi(str1);
　　int
i2=atoi(str2);
　　int
i3=i1+i2;
　　tchar
s1[256],s2[256],s3[256],s4[256];
　　itoa(i3,s1,2);
　　itoa(i3,s2,8);
　　itoa(i3,s3,10);
　　itoa(i3,s4,16);
　　switch(id)
　　{
　　case
idc_2:
　　{
　　setdlgitemtext(hwnd,idc_edit3,s1);
　　break;
　　}
　　case
idc_8:
　　{
　　setdlgitemtext(hwnd,idc_edit3,s2);
　　break;
　　}
　　case
idc_10:
　　{
　　setdlgitemtext(hwnd,idc_edit3,s3);
　　break;
　　case
idc_16:
　　{
　　setdlgitemtext(hwnd,idc_edit3,s4);
　　break;
　　}
　　}
　　default:
　　break;
　　}
　　}
　　void
main_onclose(hwnd
hwnd)
　　{
　　enddialog(hwnd,
0);
　　}