游戏平台网站制作,企业网站建设重要性,天津公司网站建设,网站建设中 动画问题: 设计一个算法在 1#xff0c;2#xff0c;……9(顺序不变)数值之间插入或者-或者什么都不插入#xff0c; 使得计算结果总是 100 的程序。 //例如 1 2 34 - 5 67 - 8 9 100。 思路: 创建一个长度为9的数组arr#xff0c;其中存放数字1到9。创建一个长度为9的字…问题: 设计一个算法在 12……9(顺序不变)数值之间插入或者-或者什么都不插入 使得计算结果总是 100 的程序。 //例如 1 2 34 - 5 67 - 8 9 100。 思路: 创建一个长度为9的数组arr其中存放数字1到9。创建一个长度为9的字符数组op用于存放操作符初始值为 。创建一个回溯函数func该函数用于搜索所有可能的表达式。在回溯函数中使用一个循环遍历所有的位置从第二个位置开始。在每个位置上有三种选择插入、插入-或者不插入任何符号。对于每种选择更新计算结果和表达式并递归调用回溯函数来搜索下一个位置。当搜索到最后一个位置时如果计算结果等于100则输出表达式。返回到上一层递归继续搜索其他可能的表达式。在主函数中调用回溯函数func从第二个位置开始搜索。 代码:
#includeiostream
using namespace std;const int N 9;
int arr[N] { 1,2,3,4,5,6,7,8,9 };
char op[N]; // 存储操作符的数组// 回溯函数用于搜索所有可能的表达式
void func(int sum, int preAdd, int i) {if (i N) { // 到达最后一个位置if (sum 100) { // 计算结果等于100cout arr[0]; // 输出第一个数字for (int j 1; j N; j) {if (op[j] ! )cout op[j]; // 输出操作符如果存在cout arr[j]; // 输出数字}cout 100 endl; // 输出结果}return;}else {// 选择插入 op[i] ;func(sum arr[i], arr[i], i 1); // 递归调用函数// 选择插入 -op[i] -;func(sum - arr[i], -arr[i], i 1); // 递归调用函数// 选择不插入任何符号op[i] ;int tempN 0;if (preAdd 0)tempN preAdd * 10 arr[i];elsetempN preAdd * 10 - arr[i];func(sum - preAdd tempN, tempN, i 1); // 递归调用函数}
}int main() {func(arr[0], arr[0], 1); // 调用回溯函数从第二个位置开始搜索return 0;
}
相关文章：
