一、题目
题目描述
某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某 1 笔或几笔。如果已知明细账目清单,能通过编程找到漏掉的是哪 1 笔或几笔吗?
如果有多种可能,则输出所有可能的情况。
输入描述
用户输入的第一行是:有错的总金额。
接下来是一个整数 n,表示下面将要输入的明细账目的条数。
再接下来是 n 行整数,分别表示每笔账目的金额。
为了方便,不妨假设所有的金额都是整数;每笔金额不超过 1000,金额的明细条数不超过 100。
输出描述
所有可能漏掉的金额组合。每个情况 1 行。金额按照从小到大排列,中间用空格分开。
二、我的思路
1、首先按题目要求将数据接收存放到数组里面,然后使用冒泡排序将每一笔的金额从小到大排序。
2、使用递归遍历每一种金额的组合。
3、在遍历每一种组合的时候,当遇到了需要的金额,如果在新的数组里没有该组合,将该组合放到新的数组里面。
4、当存放完成后,输出该组合到屏幕上,然后退出该分支。
三、代码
#include <iostream> #include <cstring> #include <string> using namespace std; int length = 1000; int loal = 0; string* str = new string[length]; //a[]是数组 x是上一级的金额 N是一共有多少笔钱 n是循环开始 set是标记数组 em是要的金钱 void dfs(int a[], int x, int N, int n, int em, char set[]) { if (x == em) { //当当前的存储长度小于总长度时可以进行存储操作 if (loal < length) { string strcmp_1; //先将set数组的值放到strcmp_1数组里面 for (int i = 0; i < N; i++) { if (set[i] != '0') { strcmp_1 += set[i]; } } //遍历当前的str,查看是否有一样的,如果没有就输出set(当前的符合题目输出的数组) int t = 0; for (t = 0; t < loal; t++) { //使用临时存储的strcmp_1与str中的所有字符串比较,如果有一样的那就跳出循环 if (!strcmp(strcmp_1.c_str(), str[t].c_str())) { break; } } //如果t>大于当前的loal说明没有相同的 if (t >= loal) { //将当前的strcmp_1存放到str中 str[loal] = strcmp_1; loal++; //输出当前的组合 for (int i = 0; i < N; i++) { if (set[i] != '0') { cout << set[i] << " "; } } cout << endl; } } return; } //递归使用递归进入每一种组合的分支 for (int i = n; i < N; ++i) { set[i] = a[i] + '0'; dfs(a, a[i] + x, N, ++n, em, set); set[i] = '0'; } } int main() { // 请在此输入您的代码 //每笔金额的数组 int a[100]; //存放修改该后的数组 char set[1000]; //给数组清零 memset(set, '0', sizeof(set)); //一共多少笔 int mark = 0; //错误的金额 int jing = 0; //全部钱加起来 int sum = 0; cin >> jing; cin >> mark; //输入每笔金额 for (int i = 0; i < mark; i++) { cin >> a[i]; sum += a[i]; } //先使用冒泡排序,由 小到大排序 int temp = 0; for (int i = 0; i < mark; i++) { for (int j = i; j < mark; ++j) { if (a[i] > a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } } //使用递归 dfs(a, 0, mark, 0, sum - jing, set); return 0; }
四、结束
为了美好的明天,继续加油吧
标签:set,int,金额,C++,++,查错,str,strcmp,loal From: https://www.cnblogs.com/kianaz/p/17322535.html