实验一 枚举算法 一、实验学时 2 学时。 二、实验目的 1．掌握枚举算法的基本思想和解题步骤。 2．掌握分解质因数问题的枚举解法。 3．掌握完美四则运算式问题的枚举解法 4．熟悉用C语言实现递归算法。 三、预习要求 1．复习C语言程序设计中的递归调用。 2．能熟练编写出递归算法的C语言程序。 四、实验内容 编写、调试下面两个问题的C语言程序，要求用递归调用实现。 1．分解质因数。对给定区间[m,n]的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。 例如, 2012=2*2*503, 2011=(素数!)。 2．完美四则运算式。把数字1,2,...,9这9个数字填入以下含加减乘除的综合运算式中的9个□中,使得该式成立 □□×□+□□□÷□-□□=0 要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在数式的一位数中（即排除各式中的各个1位数为1这一平凡情形）。 五、实验结果 给出程序源代码和程序运行结果(或程序运行结果屏幕截图)。 1．分解质因数问题。 ① 程序源代码 ② 程序运行结果 ③程序分析 2．完美四则运算式问题。 ① 程序源代码 ② 程序运行结果 ③程序分析

### 关于枚举算法的实验指导 #### 分解质因数的递归实现 分解质因数是指将一个正整数表示为其质因子相乘的形式。以下是基于递归的方法来实现这一功能。 程序逻辑如下： 1. 定义函数 `factorize` 接收当前待分解的数值以及可能的最小质因子。 2. 若当前数值等于 1，则停止递归并返回结果。 3. 否则，尝试找到能够整除该数值的第一个质因子，并将其记录下来。 4. 对剩余部分继续调用递归函数处理。 下面是完整的 C 语言代码： ```c #include <stdio.h> void factorize(int n, int divisor) { if (n == 1) { return; } if (n % divisor == 0) { printf("%d ", divisor); factorize(n / divisor, divisor); // 继续分解商的部分 } else { factorize(n, divisor + 1); // 尝试下一个可能的因子 } } int main() { int num; printf("请输入要分解质因数的数字："); scanf("%d", &num); if (num <= 1) { printf("无法分解小于等于1的数字。\n"); } else { printf("%d 的质因数为：", num); factorize(num, 2); // 开始从最小质数2开始寻找 printf("\n"); } return 0; } ``` 运行此程序时，用户输入任意大于 1 的自然数即可获得其对应的质因数组合[^1]。 --- #### 完美四则运算式的递归实现 所谓“完美四则运算式”，通常指的是通过给定的一组操作符和操作数构建合法表达式的过程。这里假设目标是从一组固定的数字集合出发，利用加减乘除四种基本算术运算生成特定的结果值。 下面是一个简单的例子展示如何使用递归来穷尽所有可能性直到匹配到期望的目标答案为止。 核心思路在于每次选取两个尚未参与计算的操作数执行某种二元运算后再加入候选列表重新考虑其余未使用的成员直至满足条件或者遍历完毕全部组合情况结束搜索过程。 具体实现如下所示: ```c #include <stdio.h> #include <stdlib.h> typedef enum { ADD, SUBTRACT, MULTIPLY, DIVIDE } Operator; // 辅助结构体存储中间状态信息 struct State { double value; char op_symbol; }; double apply_operator(double a, double b, Operator oper) { switch (oper) { case ADD: return a + b; case SUBTRACT: return a - b; case MULTIPLY: return a * b; case DIVIDE: if (b != 0) return a / b; break; } return NAN; // 非法操作返回特殊标记 } void try_solve(const double numbers[], size_t count, const double target, struct State history[], size_t hist_len) { if (count == 1 && fabs(numbers[0] - target) < 1e-6) { // 找到了解决方案... for (size_t i = 0; i < hist_len; ++i) { putchar(history[i].op_symbol); printf("%.2lf", history[i].value); } puts(""); return; } for (size_t i = 0; i < count; ++i) { for (Operator o = ADD; o <= DIVIDE; ++o) { for (size_t j = 0; j < count; ++j) { if (i == j) continue; double new_val = apply_operator(numbers[i], numbers[j], o); if (!isnan(new_val)) { double temp[count - 1]; size_t k = 0; for (size_t m = 0; m < count; ++m) { if (m != i && m != j) { temp[k++] = numbers[m]; } } temp[k] = new_val; struct State next_hist(hist_len + 1); memcpy(next_hist.data(), history, sizeof(struct State)*hist_len); next_hist[hist_len].op_symbol = ('+' + ((int)o)); next_hist[hist_len].value = new_val; try_solve(temp, k + 1, target, next_hist.data(), hist_len + 1); } } } } } int main() { double nums[] = {2, 3, 5}; double goal = 10; struct State initial_history(0); try_solve(nums, 3, goal, NULL, 0); return 0; } ``` 注意这段伪代码仅作为概念验证用途，在实际应用前需进一步优化调整细节以适应不同场景需求[^2]. --- ### 运行结果示例 对于上面提到的功能模块分别测试几个典型样例数据点观察预期行为表现是否符合设计初衷。 例如针对质因数分解部分当输入参数设为 `84` 则输出应呈现形式类似于 `"2 2 3 7"` 表明成功拆分成了四个素数连乘积关系；而至于后者由于涉及较多变量配置选项因此难以直接列举确切实例但理论上只要遵循既定规则就能逐步逼近最终解答路径之一. ---