网站建设初稿,做爰全过程免费的视网站,福州seo推广公司,陕西做网站一#xff1a;题目
给定k个正整数#xff0c;用算术运算符#xff0c;-#xff0c;#xff0c;/ 将这k个正整数连接起来#xff0c;是最终的得数恰为m。 如果有多组满足要求的表达式#xff0c;只要输出一组#xff0c;每一步算式用分号隔开。 如果无法得到m#xff…一题目
给定k个正整数用算术运算符-/ 将这k个正整数连接起来是最终的得数恰为m。 如果有多组满足要求的表达式只要输出一组每一步算式用分号隔开。 如果无法得到m得输出“No Solution”。 样例输入:d 5 125 7 2 2 12 3 第一行输入整数的个数k和m 第二行输入k个整数。 这只是其中一种结果 样例输出 7321 21*12252 252-2250 250/2125
二思路
1.排列树 子集树 2.我们穷举所有的可能的数字组合这是全排列但要注意的是在全排列中如果给出的数据有重复的数字那么我们求的全排列后的数据是有重复的所以我们要进行去重处理 3.得到全排列的结果后我们要对每一个全排列的结果进行子集树处理因为每一次往下递归都是’’,’-’,’*’,’/’;递归的终止条件就是当我们统计 sum M时候,或者是我们的操作符个数满足要求的时候如果仅仅是操作符满足个数是不统计操作符的结果的
二上码
/*
1.题目:
给定k个正整数用算术运算符-*/ 将这k个正整数连接起来是最终的得数恰为m。
如果有多组满足要求的表达式只要输出一组每一步算式用分号隔开。
如果无法得到m得输出“No Solution”。
样例输入:
5 125
7 2 2 12 3
第一行输入整数的个数k和m
第二行输入k个整数。
样例输出 7*321 21*12252 252-2250 250/21252.思路分析
从输出的样例顺序(7,3,12,2,2)可以得知,这是一种全排列后的结果,对于每组数据之间的加减乘除,我们
可以做子集树划分 */#includebits/stdc.h
using namespace std;int N,M;
int cnt 0;
vectorvectorint ans1;
vectorint path1;vectorvectorchar ans2;
vectorchar path2;//求出数字的全排列组合
void backtacking1(int N,vectorint vec,vectorbool vis){if(path1.size() N){ans1.push_back(path1);return;}for(int i 0; i N; i){if(vis[i] true) continue;vis[i] true;path1.push_back(vec[i]);backtacking1(N,vec,vis);path1.pop_back();vis[i] false;}
}//子集树的排列
//横向的for循环为加减乘除纵向的为一种全排列的结果
void backtacking2(vectorchar v1,vectorint v2,int sum,int index){if(sum M || path2.size() N - 1){ //这里递归结束的条件为满足 M时 if(sum M){ //还有的是操作符号的个数不能大于 N - 1个 ans2.push_back(path2);cnt 1;}return ; }for(int i 0; i 4; i){//这里小于4是有4个操作符 char ch v1[i];if(ch ){sum sum v2[index];}else if(ch -){sum sum - v2[index];}else if(ch *){sum sum * v2[index];}else if(ch /){sum sum / v2[index];}index;//表示纵向的一种全排列结果集的下标 path2.push_back(ch);//将符号存进去 backtacking2(v1,v2,sum,index);//这里的顺序不能乱 path2.pop_back();index--;if(ch ){sum sum - v2[index];}else if(ch -){sum sum v2[index];}else if(ch *){sum sum / v2[index];}else if(ch /){sum sum * v2[index];} }
} //验证全排列
void text01(){ for(int i 0; i ans1.size(); i){for(int j 0; j N; j){cout ans1[i][j] ;}cout endl;}
}int main(){vectorintv1;//输入的数据vectorvectorint v3;//记录可行解 vectorchar operators(4); setints[100]; setint:: iterator st;cin N M;for(int i 0; i N; i){int num;cin num;v1.push_back(num);}cout endl; vectorbool vis(N,false); backtacking1(N,v1,vis); operators[0] ;operators[1] -;operators[2] *;operators[3] /;for(int i 0; i ans1.size(); i){vectorint v2;int count 0; for(int j 0; j N; j){ v2.push_back(ans1[i][j]);if(ans1[i-1][j] ans1[i][j] i ! 0){count; } }if(count N){ // 这是为了去重的因为在全排列中如果有重复的元素那么最终输出 continue; //的结果是有重复的组数据的 }int num v2[0];backtacking2(operators,v2,num,1);if(cnt 1){//这里存的是满足条件的 数字组合 v3.push_back(v2);} cnt 0;}for(int i 0; i ans2.size(); i){//v3.size() 和ans2.size()大小是一致的 cout 操作数为:;for(int j 0; j N; j){cout v3[i][j] ;}cout endl;cout 操作符为:; for(int j 0; j N - 1; j){//N个数需要 N-1个操作符 cout ans2[i][j] ;}cout endl;}} //5 125
//7 3 12 2 2//5 125
//7 2 2 12 3下方的的数据按照操作符都可以得到正确结果
