约瑟夫问题:n个骑士编号1,2,...,n,围坐在圆桌旁。编号为1的骑士从1开始报数,报到m的骑士出列,然后下一个位置再从1开始报数,找出最后留在圆桌旁的骑士编号。 (1)编写一个函数模板。以一种顺序容器的类型作为模板参数,在模板中使用指定类型的顺序容器求解约瑟夫问题。m,n是该函数模板的形参。 (2)分别以vector<int>,deque<int>,list<int>作为类型参数调用该函数模板,调用时将n设为较大的数,将m设为较小的数(例如令n=100000,n=5)。观察3种情况下调用该函数模板所需花费的时间。 注:本题答案的提交只需选择一种顺序容器类型作为模板参数。 【输入形式】 程序参考的输入(数字前为提示文字): Input n and m:7 3 【输出形式】 程序参考的输出: Result:4 【样例输入】 Input n and m:7 3 【样例输出】 Result:4 【样例说明】 【评分标准】 #include<iostream> #include<vector> using namespace std; int main() { vector<int> a; int n,m,x=0; cout<<"Input n and m:"; cin>>n>>m; a.resize(n); for(int i=0;i<n;i++) { a[i]=i+1; } cout<<"Result:"<<a[0]<<endl; return 0; }
时间: 2024-01-09 17:04:30 浏览: 30
```cpp
#include<iostream>
#include<vector>
#include<deque>
#include<list>
#include<chrono> // 用于计时
using namespace std;
// 定义函数模板
template<typename Container>
int josephus(int n, int m) {
Container knights(n); // 创建容器并初始化
for(int i = 0; i < n; i++) {
knights[i] = i + 1;
}
int pos = 0; // 初始位置为0
while(n > 1) {
pos = (pos + m - 1) % n; // 计算出列位置
knights.erase(knights.begin() + pos); // 移除骑士
n--; // 骑士数减1
}
return knights[0]; // 返回最后剩余的骑士编号
}
int main() {
int n, m;
cout << "Input n and m: ";
cin >> n >> m;
// 使用vector容器
auto start = chrono::steady_clock::now(); // 记录开始时间
int result = josephus<vector<int>>(n, m);
auto end = chrono::steady_clock::now(); // 记录结束时间
cout << "Using vector: " << result << endl;
cout << "Time cost: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 使用deque容器
start = chrono::steady_clock::now();
result = josephus<deque<int>>(n, m);
end = chrono::steady_clock::now();
cout << "Using deque: " << result << endl;
cout << "Time cost: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
// 使用list容器
start = chrono::steady_clock::now();
result = josephus<list<int>>(n, m);
end = chrono::steady_clock::now();
cout << "Using list: " << result << endl;
cout << "Time cost: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " us" << endl;
return 0;
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)