用C++编写找出10000以内的同构数的程序
时间: 2024-09-26 17:10:46 浏览: 9
同构数是指将数字的数码重新排列后,得到的新数等于原数本身的两个数。比如,61 = 16。要在C++中编写一个找出10000以内同构数的程序,你可以采用哈希集合(如`std::unordered_set`)来存储已经遇到的数字,并遍历到指定范围。
下面是一个简单的示例代码:
```cpp
#include <iostream>
#include <unordered_set>
#include <vector>
bool isIsomorphic(std::string s, std::string t) {
std::unordered_map<char, char> map_s_to_t, map_t_to_s;
for (size_t i = 0; i < s.size(); ++i) {
if (map_s_to_t.find(s[i]) != map_s_to_t.end() && map_s_to_t[s[i]] != t[i]) {
return false;
}
if (map_t_to_s.find(t[i]) != map_t_to_s.end() && map_t_to_s[t[i]] != s[i]) {
return false;
}
map_s_to_t[s[i]] = t[i];
map_t_to_s[t[i]] = s[i];
}
return true;
}
int findIsomorphicPairs(int n) {
std::vector<int> numbers(n + 1);
for (int i = 1; i <= n; ++i) {
numbers[i] = std::stoi(std::to_string(i));
}
int count = 0;
std::unordered_set<int> visited;
for (int num : numbers) {
std::string str_num = std::to_string(num);
for (int j = num + 1; j <= n; ++j) {
if (isIsomorphic(str_num, std::to_string(j)) && !visited.count(j)) {
count++;
visited.insert(j);
}
}
}
return count;
}
int main() {
int limit = 10000;
int result = findIsomorphicPairs(limit);
std::cout << "在1到" << limit << "之间,有 " << result << " 对同构数.\n";
return 0;
}
```
这个程序首先将1到n的整数转换成字符串,然后逐个检查每个数字与其之后的数字是否同构。如果找到一对,它会增加计数并标记已访问过的数字,避免重复计算。最后,它会输出满足条件的同构对的数量。