C++cantor函数

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 集。

下面是代码示例：

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++ 代码：

#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$ 的矩阵，分别表示初始状态和目标状态，输出为最少需要多少步才能从初始状态到达目标状态，以及从初始状态到达目标状态的解路径。