【xdoj-离散线上练习】T234（C++）

 解题心得：

写递归函数的时候，首先写终止条件，这有助于对整个递归函数的把握。

题目：输入集合A和B，输出A到B上的所有函数。

问题描述

给定非空数字集合A和B，求出集合A到集合B上的所有函数。

输入格式

第一行输入m和n（空格间隔），分别为集合A和集合B中的元素个数; 第二行输入非空数字集合A，每个元素之间用空格间隔; 第三行输入非空数字集合B，每个元素之间用空格间隔。

输出格式

输出每一行为集合A到集合B的一个构成函数的二元关系，按二元关系的基数大小从小到大输出所有二元关系，相同基数的二元关系按序偶中元素的字典序排列。

样例输入

2 2

1 2

3 4

样例输出

{<1,3>,<2,3>}

{<1,3>,<2,4>}

{<1,4>,<2,3>}

{<1,4>,<2,4>}

实现思路： 预处理：利用优先队列将集合中元素从小到大放进数组A，B中递归实现：每行中A的元素全部被输出，是确定的，我们用递归更新B中要输出的元素，并在每次递归的末端cout一行结果 总体代码实现（已给出代码注释） #include<bits/stdc++.h> using namespace std; int main() { //预处理：利用优先队列将集合中元素从小到大放进数组A，B中 int m, n, cur; cin>>m>>n; priority_queue<int>pq; vector<int>A(m); vector<int>B(n); for(int i=0; i<m; i++) { cin>>cur; pq.push(cur); } for(int i=1; i<=m; i++) { A[m-i] = pq.top(); pq.pop(); } for(int i=0; i<n; i++) { cin>>cur; pq.push(cur); } for(int i=1; i<=n; i++) { B[n-i] = pq.top(); pq.pop(); } //观察输出样例：每行输出均有A中全部元素，B对应元素每行只有一处变化 vector<int>q(m);//q[i]携带了当前映射关系中A[i]对应的集合B中元素 //为什么用递归：因为A中元素数量不确定，事实上，如果用for循环嵌套，那么for循环的数量为 m，这是不能在确定的代码中实现的 auto dfs = [&](auto& dfs, int cnt) -> void { if(cnt == m)//递归终止条件 { cout<<"{"; for(int i=0; i<m; i++) { cout<<"<"<<A[i]<<","<<q[i]<<">"; if(i == m-1) cout<<"}"<<endl; else cout<<","; } return; } else{ for(int i=0; i<n; i++) { q[cnt] = B[i]; dfs(dfs, cnt+1); } return; } }; dfs(dfs, 0); return 0; } ~希望对你有帮助~