Pancake numbers: Difference between revisions
→{{header|C++}}
Line 81:
=={{header|C++}}==
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <numeric>
#include <iomanip>
std::vector<int32_t> flip_stack(std::vector<int32_t> stack, int32_t index) {
reverse(stack.begin(), stack.begin() + index);
}
std::pair<std::vector<int32_t>, int32_t> pancake(int32_t number) {
std::vector<int32_t> initial_stack(number);
std::iota(initial_stack.begin(), initial_stack.end(), 1);
std::map<std::vector<int32_t>, int32_t> stack_flips = { std::make_pair(initial_stack, 1) };
std::queue<std::vector<int32_t>> queue;
queue.push(initial_stack);
while ( ! queue.empty() ) {
std::vector<int32_t> stack = queue.front();
queue.pop();
const int32_t flips = stack_flips[stack] + 1;
std::vector<int32_t> flipped = flip_stack(stack, i);
if ( stack_flips.find(flipped) == stack_flips.end() ) {
stack_flips[flipped] = flips;
queue.push(flipped);
}
}
}
auto ptr = std::max_element(
stack_flips.begin(), stack_flips.end(),
[] ( const auto & pair1, const auto & pair2 ) {
return pair1.second < pair2.second;
}
);
return std::make_pair(ptr->first, ptr->second);
}
int main() {
std::pair<std::vector<int32_t>, int32_t> result = pancake(n);
▲ for (int j = 1; j < 6; j++) {
for ( uint64_t i = 0; i < result.first.size() - 1; ++i ) {
▲ std::cout << "p(" << std::setw(2) << n << ") = " << std::setw(2) << pancake(n) << " ";
std::cout << result.first[i] << ", ";
}
std::cout << result.first.back() << "]" << std::endl;
}
▲ return 0;
}
▲}</syntaxhighlight>
</syntaxhighlight>
{{ out }}
<pre>
pancake(1) = 1. Example [1]
pancake(2) = 2. Example [2, 1]
pancake(3) = 4. Example [1, 3, 2]
pancake(4) = 5. Example [2, 4, 1, 3]
pancake(5) = 6. Example [1, 3, 2, 5, 4]
pancake(6) = 8. Example [4, 6, 2, 5, 1, 3]
pancake(7) = 9. Example [1, 3, 7, 5, 2, 6, 4]
pancake(8) = 10. Example [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 11. Example [1, 2, 5, 8, 3, 6, 9, 4, 7]
</pre>
=={{header|Cowgol}}==
| |||