Joseph question: n knight numbers 1, 2, n. Sitting around the round table. Knights numbered 1 start counting from 1, those who report to m are listed, and then the next position starts counting from 1 to find the last knight number left next to the round table. (1) Write a function template. Using a type of sequential container as a template parameter, solve the Joseph problem using a specified type of sequential container in the template. m. N is the formal parameter of the function template. (2) Call the function template with vector<int>, deque<int>, and list<int>as type parameters. When calling, set n to a larger number and m to a smaller number (such as n=100000, n=5). Observe the time it takes to call the function template in three scenarios. Note: To submit the answer to this question, only one sequential container type needs to be selected as the template parameter. [Input Form] Input for program reference (prompt text before numbers): Input n and m:7 3 Output Form Output of program reference: Result:4 Sample Input Input n and m:7 3 Sample output Result:4 Sample Description Scoring criteria #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-10 08:04:44 浏览: 76
Here's the function template to solve the Joseph problem using a specified type of sequential container as the template parameter:
```cpp
template<typename Container>
int joseph(int n, int m) {
Container knights;
for (int i = 1; i <= n; ++i) {
knights.push_back(i);
}
auto it = knights.begin();
while (knights.size() > 1) {
for (int i = 1; i < m; ++i) {
++it;
if (it == knights.end()) {
it = knights.begin();
}
}
it = knights.erase(it);
if (it == knights.end()) {
it = knights.begin();
}
}
return knights.front();
}
```
The function takes two integer parameters `n` and `m`, which are the number of knights and the count to skip before removing a knight, respectively. The function returns the number of the last knight left standing.
To call the function with different sequential container types, we can use the following code:
```cpp
int main() {
int n = 100000;
int m = 5;
// Using vector<int>
auto start_time = chrono::steady_clock::now();
int result = joseph<vector<int>>(n, m);
auto end_time = chrono::steady_clock::now();
cout << "vector<int>: " << result << ", time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << "ms" << endl;
// Using deque<int>
start_time = chrono::steady_clock::now();
result = joseph<deque<int>>(n, m);
end_time = chrono::steady_clock::now();
cout << "deque<int>: " << result << ", time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << "ms" << endl;
// Using list<int>
start_time = chrono::steady_clock::now();
result = joseph<list<int>>(n, m);
end_time = chrono::steady_clock::now();
cout << "list<int>: " << result << ", time: " << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << "ms" << endl;
return 0;
}
```
This code first sets `n` and `m` to the desired values. It then calls the `joseph` function with `vector<int>`, `deque<int>`, and `list<int>` as the sequential container types, and measures the time it takes to run each call using the `chrono` library. Finally, it prints the results and the execution times for each container type.
Note that the time it takes to run the function depends on the size of `n` and the value of `m`. For large values of `n` and small values of `m`, the function may take a long time to run, especially for `list<int>` which has slower insertions and deletions than `vector<int>` and `deque<int>`.
阅读全文