设计程序在表达式“123456789＝100”中左边的适当位置插入运算符“＋” 或 “

tt254120746-1778615-4744300845234609314.doc.pdf-第1页.png

第1页 / 共6页

tt254120746-1778615-4744300845234609314.doc.pdf-第2页.png

第2页 / 共6页

tt254120746-1778615-4744300845234609314.doc.pdf-第3页.png

第3页 / 共6页

tt254120746-1778615-4744300845234609314.doc.pdf-第4页.png

第4页 / 共6页

tt254120746-1778615-4744300845234609314.doc.pdf-第5页.png

第5页 / 共6页

tt254120746-1778615-4744300845234609314.doc.pdf-第6页.png

第6页 / 共6页

课程设计设计题目：设计程序在表达式“123456789＝100”中左边的适当位置插入运算符“＋” 或 “－”，以使等式成立。例如 123+45-67+8-9=100 设计目的：本次设计关键是算法分析，在确定题目以后主要利用所学知识设计算法。考查数学思维、C++基本编程语言以及数据结构语言的知识，同时进一步熟悉 Visual C++的使用，提高知识应用的能力。

设计思路算法分析：整体而言，本题实质是一个表达式求值的问题。建立模型：1○2○3○4○5○6○7○8○9=100，给八小圆圈内填写“”（不填写任何符号）“+”“-”，如果不填任何符号，则两数直接相邻构成一个数，例如 1○2 之间不填写，默认为 12；1○2○3 之间不填写默认为 123。这样计算表达式，一种可能的情况为 123+45-67+8-9=100。由于每个圆圈只能有“”“+”“-”三种情况，及三种取值，因此，我们将八个圆圈排在一起 “○○○○○○○○”构成一个八位的三进制数，及每个圆圈有 0、1、2 三个取值分别与 “”“+”“-”对应，例如：三进制数 00102012，对应的式子为 123+45-67+8-9。八位三进制数总共有38 =6561 个，也就是共有 6561 种可能的表达式（获取三进制数类似于二进制，采用除三取余法，比如用（int）i 记录从 0 到 6561 的变化，当 i=302 时，对应八位三进制数为 00102012）。操作数有 1、2、3、4、5、6、7、8、9 共九个。利用操作数和操作符号交替使用，来确定表达式这样我们用一个例子来说明：利用 for(int i=0;i<=6561;i++）循环，当 i=302 时，有初始化，默认 1 前面的操作符号位加号：+1○2○3○4○5○6○7○8○9，操作数从 2 开始也就是 for (j=2;j<=9;j++)循环，当 j=2 时，通过 2 前面的第一个小圆圈（三进制数首位上的数），我们来确定是“”“+”“-”中的哪一种。而 i=302 时对应八位三进制数为 00102012（经过不断除以 3 取余数可以获取这个三进制数每一位上的数字，依次是 0、0、1、0、2、0、1、2），除以 3 取余数我们可以得到 2 前面的三进制数为 0，也就是没有运算符即 12○3○4○5○6○7○8○9，然后切换操作数此时 j=3，而八位三进制数除以 3 取整后可得一个七位三进制数 0102012，在进行除 3 取余可得到此时操作数 3 前面的三进制数字为 0，也就是没有运算符即 123○4○5○6○7○8○9 以此类推…… 不断更新操作数和相应前面的三进制数（从八位逐步递减为一位），我们可得式子的最后表达式为 123+45-67+8-9，这样用字符串记录运算模式，然后利用判断语句 if (s==100) printf("表达式: %s=%d\n",str,s)

这样可以选择出 6561 个表达式中运算结果为 100 的式子。设计步骤： 1 在 Visual C++6.0 操作界面中，新建一个文件，文件类型为 C++ Source File，即.cpp 文件，命名为“一百”； 2 建立头文件#include “stdio.h”，#include “stdlib.h”；#define N 3 写主函数 main（）； 4 定义变量；char fuhao,str[80]; 5 利用循环语句 for (i=0;i<=6561;i++)，来记录表达式可能的所有情况，i 是每一种枚 int i,j,s,n,m,p; 5; 举的情况，把 i 分解为八位 3 进制数，每一位表示每一个位置的符号； -------------------------------------------------------------------------- --- 6 在上述循环语句中初始化各个变量， s=0 记录满足条件的表达式的和的值, m=1 初始化第一个操作数, n=i 在获取 i 对应的三进制数的每一位上的数字会破坏 i 的值，故采用另一个变量 n 来获取, p=0 用指针来记录运算过程,str[p++]=’1’对字符串数组初始化为 1； fuhao=’+’初始化第一个操作符号为“+”, 7 在第 5 步的循环语句下嵌套使用 for 语句：for (j=2;j<=9;j++),依次更新操作数经过八次循环，每次的下一个操作数是 j； ------------------------------------------------------------------------ --- 8 通过 if 语句实现：三进制下的第 j-1 位数不断除三取余后，如果不是 0，则要完成先前的操作 if (n%3) { if (fuhao=='+') s+=m; else s-=m; m=j; } 9 通过 switch 语句，此时 n 对应三进制数除以三取余只有三种情况 case 0:m=m*10+j;break; 余数为 0，没有操作符号，则与相邻的前一个数合在一起 case 1:fuhao='+';break; 余数为 1，操作符为“+”，则将操作数加到原来的和 s 中 case 2:fuhao='-';break; 余数为 2，操作符为“-”，则将原来的和减去该操作数 j； 10 通过 if 语句： if (n%3) str[p++]=fuhao; str[p++]='0'+j; n/=3;

即 n 能被三整除，记录此时的运算模式，执行到当前操作数 j,并将 n 除以三取整，这样将八位三进制数逐步变为七位、六位……,来获取三进制数各位上的数字第七步的循环结束； --------------------------------------------------------------------------- 11 对此是记录的表达式进行识别计算 if (fuhao=='+') s+=m; else s-=m; str[p]='\0'; if (s==100) printf("表达式: %s=%d\n",str,s); 12 第五步的循环结束，主函数结束。程序代码： #include”stdio.h” #include”stdlib.h” #define main() { 6561 N char fuhao,str[100]; int i,j,s,n,m,p; for (i=0;i<=N;i++) /*i 是每一种枚举的情况，把 i 分解为八位 3 进制数，每一位表示每一个位置的符号*/ { s=0; /*该方式下的和*/ m=1; /*作操作数*/ n=i; /*获取 i 在 3 进制下的每一位会破坏 i，所以借用变量 n 来获取*/ fuhao='+'; /*第一次操作方式为+*/ p=0; /*指针用来记录运算过程*/ str[p++]='1'; /*首先记录一个 1*/ for (j=2;j<=9;j++) /*八次循环，每次的下一个操作数是 j*/ { if (n%3) /*3 进制下的第 j-1 位数，如果不是 0，则要完成先前的操作*/ { if (fuhao=='+') s+=m; s-=m; else m=j; /*更新操作数*/ } switch(n%3) /*根据这一位的情况进行处理*/ { case 0:m=m*10+j; break; case 1:fuhao='+';break; case 2:fuhao='-';break; } if (n%3) str[p++]=fuhao; /*记录运算模式*/

str[p++]='0'+j; n/=3; } if (fuhao=='+') s+=m; else s-=m; str[p]='\0'; if (s==100) printf("表达式: %s=%d\n",str,s); /*判断是否满足*/ } } 设计总结： 1 建立一个 C++ Source File 的方法，进一步熟悉了 Visaul C++的操作流程； 2 算法分析的重要性本程序中尤其是三进制来划分“”“+”“-”三种情况，使得程序简洁凝练，一个个程序有一个简洁的算法可以有效地减少程序的时间、空间的复杂度本题也可采用八个 for 循环语句来实现“”“+”“-”这三种情况，这样程序繁杂冗长，容易出错； 3 熟悉 C 语言，for 循环的嵌套使用，if 语句的多次使用； 4 细节：例如本设计中由于不断对 i 进行变换，破坏了第一个 for 循环中的 i，故采用 n 来获取相关值，使用了技巧。 5 时间复杂度：8*N 即 O（N）空间复杂度：0

资料库

设计程序在表达式“123456789＝100”中左边的适当位置插入运算符“＋” 或 “－”，以使等式成立.doc

相关推荐

课程资源

热门标签

最新资料