C++cantor函数
时间: 2024-08-14 17:06:13 浏览: 105
Cantor函数,也称为中间值迭代函数或Cantor集构造函数,是一个经典的数学构造,用于生成一个无理数集合,即Cantor集。这个函数通常在实数分析和计算机科学中被用作教学示例,因为它展示了连续函数可以有不可数多个零点,尽管整体函数值域是有限的。
Cantor函数的基本定义是从0到1的区间[0,1]上定义的一个单调递增函数。它的工作原理是通过不断将区间二分,并删除每个部分的中间三分之一,形成一系列越来越细的“梳齿”。初始区间被划分为两个相等的部分[0,1/3]和[2/3,1],然后删除[1/3,2/3]这一部分,以此类推。这样剩下的部分会无限逼近0和1之间的某个特定数值,该数值就是Cantor函数的结果。
Cantor函数的具体公式可以用迭代的方式来表达,例如:
\[ f_0(x) = x \]
\[ f_{n+1}(x) = \begin{cases}
2f_n(x) & \text{if } x < 1/3 \\
2f_n(x) - 1 & \text{otherwise}
\end{cases} \]
随着n的增长,函数f_n(x)将收敛到Cantor函数。虽然Cantor函数在整个定义域内只取了0和1两个值,但它仍然是一个连续函数,因为每次删除的部分都是闭合区间内部的。
相关问题
使用mfc编程在窗口中一次绘制n=0~5的所有cantor集
好的,我理解了你的问题。首先,对于不了解 Cantor 集的人来说,它是由 Georg Cantor 发明的一类自相似的集合。Cantor 集是一个闭集,也就是说它包含所有的极限点。在 Cantor 集中,每个点都可以被表示为三进制数,其中每个数字可以是0、1或2。那么,我们可以使用 MFC 编程在窗口中一次性绘制 n=0~5 的所有 Cantor 集。
下面是代码示例:
```c++
void CCantorView::OnDraw(CDC* pDC)
{
CCantorDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
if (!pDoc)
return;
int nWidth = 700; // 窗口宽度
int nHeight = 400; // 窗口高度
int nMaxIter = 5; // 最大迭代次数
int nRectWidth = nWidth / pow(3, nMaxIter); // 矩形宽度
int nRectHeight = 20; // 矩形高度
int nXPos = 0; // 矩形起始横坐标
int nYPos = 50; // 矩形起始纵坐标
// 绘制 Cantor 集
for (int i = 0; i <= nMaxIter; i++)
{
for (int j = 0; j < pow(3, i); j++)
{
if (i == 0)
{
// 绘制第一级矩形
pDC->Rectangle(nXPos, nYPos, nXPos + nRectWidth, nYPos + nRectHeight);
nXPos += nRectWidth;
}
else
{
// 绘制更高级别的矩形
if (j % 3 != 1)
{
pDC->Rectangle(nXPos, nYPos, nXPos + nRectWidth, nYPos + nRectHeight);
}
nXPos += nRectWidth;
}
}
nXPos = 0;
nYPos += nRectHeight * 2;
nRectWidth /= 3;
}
}
```
这段代码会在窗口中绘制从 0 级到 5 级的所有 Cantor 集,其中每个级别的集合都在上一级别的集合上方。你可以在 `OnDraw` 函数中调用这个函数,然后在你的程序中使用该函数来绘制 Cantor 集。
宽度优先八数码c++
下面是一个基于宽度优先搜索算法实现的八数码问题解决程序的 C++ 代码:
```c++
#include <iostream>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
// 八数码的状态结构体
struct node {
int num[3][3]; // 表示八数码的矩阵
int x, y; // 空格的位置
int step; // 到达当前状态的步数
int pre; // 前驱状态的编号
} s, e, u, v;
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; // 阶乘
int dx[] = {-1, 0, 1, 0}; // 上下左右移动
int dy[] = {0, 1, 0, -1};
int cantor(int a[]) { // 康拓展开
int sum = 0;
for (int i = 0; i < 9; i++) {
int t = 0;
for (int j = i + 1; j < 9; j++)
if (a[i] > a[j])
t++;
sum += t * fac[9 - i - 1];
}
return sum;
}
void reverse_cantor(int x, int a[]) { // 康拓展开的逆运算
int vis[10] = {0};
for (int i = 0; i < 9; i++) {
int t = x / fac[9 - i - 1];
x %= fac[9 - i - 1];
for (int j = 1; j <= 9; j++)
if (!vis[j]) {
if (t == 0) {
a[i] = j;
vis[j] = 1;
break;
} else
t--;
}
}
}
int bfs() {
queue<node> q;
map<int, int> mp;
s.step = 0;
s.pre = -1;
int a[10];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
a[i * 3 + j] = s.num[i][j];
mp[cantor(a)] = 1;
q.push(s);
while (!q.empty()) {
u = q.front();
q.pop();
if (memcmp(u.num, e.num, sizeof(u.num)) == 0)
return u.pre;
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i], ny = u.y + dy[i];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
memcpy(&v, &u, sizeof(u));
swap(v.num[u.x][u.y], v.num[nx][ny]);
v.x = nx, v.y = ny;
v.step++;
int a[10];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
a[i * 3 + j] = v.num[i][j];
int code = cantor(a);
if (!mp[code]) {
mp[code] = 1;
v.pre = mp.size() - 1;
q.push(v);
}
}
}
}
return -1;
}
int main() {
// 输入初始状态和目标状态
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
cin >> s.num[i][j];
if (s.num[i][j] == 0)
s.x = i, s.y = j;
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cin >> e.num[i][j];
int ans = bfs();
if (ans == -1)
cout << "无解" << endl;
else {
cout << "步数为:" << u.step << endl;
int path[1000], cnt = 0;
while (ans != -1) {
path[cnt++] = u.pre;
u = q[u.pre];
}
cout << "解路径为:";
for (int i = cnt - 1; i >= 0; i--)
cout << " " << path[i];
cout << endl;
}
return 0;
}
```
其中,`cantor` 函数实现康拓展开,用于将每个状态映射到一个唯一的整数上;`reverse_cantor` 函数实现康拓展开的逆运算,用于从一个整数反推出对应的状态;`bfs` 函数实现基于宽度优先搜索算法的八数码问题的解决。程序的输入为两个 $3\times3$ 的矩阵,分别表示初始状态和目标状态,输出为最少需要多少步才能从初始状态到达目标状态,以及从初始状态到达目标状态的解路径。
阅读全文