C++两个函数可以相互递归吗_函数图像的一种简单近似

函数图像

的一种简单近似

在学校除了上课写作业吃饭睡觉就没有其它活动了，这种环境使我在吃饱之后可以想想别的。本周想想别的的结果是一种函数图像的简单近似。

本文将探讨一种递归求解复合表达式的算法，以及一种在经典控制台命令行环境下建立平面直角坐标系的简单技巧。

01

一些简单的归纳和规定

02

格式化用户输入

03

分治求解算法

04

绘制函数图像

05

以上内容在控制台上的表现

一些简单的归纳和规定

    在本文中，我们把形如：

    的式子称作简单式，因为显然可以通过直接运算得到这一式子的结果，且不能继续分割它。

(如果你感到一种不专业的气氛，恳请骂的小声些，毕竟这是我在宿舍里翘着二郎腿闭门造车的结果)

    相应地，把形如：

    的式子称作复杂式，因为这一式子是由多个简单式复合而成的，也就是说可以对其进行分割。

    我们知道，不同的算符在运算时具有不同的优先级。如：

    在计算时，先计算a+b=R1，再计算R1*c。讨论几种常见运算符集中出现的情况后，可以把优先级总结如下：

    其中 f 指f(x)、ln(x)等，^是指数运算符。这就是说，计算lne^2时，我们先计算e的二次方再计算其自然对数；计算sinx^3时，我们先计算x^3再计算其正弦值。

    为了使括号内的任意计算都比括号外高级，只需使：

左括号 ( 的累加优先级为4

右括号 )的累加优先级为-4

    请注意，括号并无实义。这里的累加优先级指的就是它只负责调整其后的全部算符的优先级。

    举例而言：

    这一复杂式的优先级情况为：

1. 左括号将其后所有优先级+4
2. +的优先级现在是 1+4 = 5
3. 右括号将其后所有优先级-4
4. *的优先级现在是 2+4-4 = 2

    因此我们知道，应先计算a+b=R1，再计算R1*c

    另外，我们只讨论两类算符：二元算符和一元算符。二元算符需要两个数据项，一元算符只须一个。

格式化用户输入

    在程序中，用户输入的是一个字符串。对字符串的操作往往是繁琐的，且很难分辨算符和数据。因此，在开始求解前，有必要对用户输入的函数进行格式化，把：

    格式化为多个元素的集合：

    其中a、b、c可取任意实常实数或实数变量x，例如：

    显而易见地，表中的任意元素既可以是数据(即计算机中的double型数据)，也可以是算符(可以用char枚举)。要实现这一点，需要为之建立一个类。

class Operand    {        public bool unknown = false;        public char op = '~';        public double num = 0.0d;        public Operand(bool unknown, char op, double num)        {            this.unknown = unknown;            this.op = op;            this.num = num;        }    }
           

‍

    其中，unknown标记自变量。虽然之后并没有用到，但我还是懒得删掉。

    op标记算符，op=~时，该元素为数据而非算符。

    诚然，在这种情况下，建立struct要合适些，建立链表也比建立集合要合适些。但由于我对C#也不怎么熟来着……

要实现格式化，我们采用遍历与枚举结合的方式。可以说，这种方式是最愚蠢的方式。我在宿舍床上也不禁感叹：活成了自己最厌恶的样子。

static void getItemlist(string sourcestr, double x){    itemlist = new List();    for (int i = 0; i < sourcestr.Length; ++i)    {        //把算符前的内容转换为数字并加入        if (i != 0 && ((sourcestr[i] == 'l' && sourcestr[i + 1] == 'o') || sourcestr[i] == ')' || sourcestr[i] == '+' || sourcestr[i] == '-' || sourcestr[i] == '*' || sourcestr[i] == '/' || sourcestr[i] == '^'))        {            char[] numstring = new char[i];            sourcestr.CopyTo(0, numstring, 0, i);            double num = 0;            Double.TryParse(new string(numstring), out num);            itemlist.Add(new Operand(false, '~', num));            sourcestr = sourcestr.Remove(0, i);            i = -1;            continue;        }        if (sourcestr[i] == '+' || sourcestr[i] == '-' ||            sourcestr[i] == '*' || sourcestr[i] == '/' ||            sourcestr[i] == '^' || sourcestr[i] == '(' ||            sourcestr[i] == ')')        {            itemlist.Add(new Operand(false, sourcestr[i], 0));            sourcestr = sourcestr.Remove(i, 1);            i = -1;            continue;        }        if (sourcestr[i] == 'c' || sourcestr[i] == 's' || sourcestr[i] == 't')        {            itemlist.Add(new Operand(false, sourcestr[i], 0));            sourcestr = sourcestr.Remove(i, 3);            i = -1;            continue;        }        if (sourcestr[i] == 'l')        {            if (sourcestr[i + 1] == 'n')            {                itemlist.Add(new Operand(false, 'n', 0));                sourcestr = sourcestr.Remove(i, 2);                i = -1;                continue;            }            itemlist.Add(new Operand(false, 'l', 0));            sourcestr = sourcestr.Remove(i, 3);            i = -1;            continue;        }        if (sourcestr[i] == 'x')        {            itemlist.Add(new Operand(true, '~', x));            sourcestr = sourcestr.Remove(i, 1);            i = -1;            continue;        }        if (sourcestr[i] == ';')        {            if (i == 0)                return;            char[] numstring = new char[i];            sourcestr.CopyTo(0, numstring, 0, i);            double num = 0;            Double.TryParse(new string(numstring), out num);            itemlist.Add(new Operand(false, '~', num));            return;        }    }}
           

分治求解算法

    计算简单式，只需要确定其算符(运算方式)和数据。计算复杂式则需要依据不同算符和括号规定的优先级，将其分割为多个简单式进行计算。

    这种思想被称为分治。下文将讨论的算法本质上是一种分治算法。一个分治算法将一个规模为N的问题分解成K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。[0]

    在求解复杂式这一例子中，这意味着：

1. 将一个由N个简单式合并而成的复杂式还原为N个简单式
2. 计算这N个简单式
3. 将得到的N个结果合并，即得原复杂式的解

    如何分解复杂式呢？只需要：

1. 检查。如果这一式子是最简式。计算之并返回其结果。如果不是：
2. 找出式内优先级最高的算符，如果优先级最高的算符有多个，最前的那个。这一算符一定对应一个简单式(如果算符的一个或多个数据是是复杂式，括号使它的优先级显然不可能最高)。我们把这一简单式称作最高简单式。
3. 计算最高简单式。用其结果替代最高简单式在原式内的位置。
4. 继续分解得到的结果。正是这一步造成了递归。

    使用C#的实现过程如下：

如果你觉得写的太乱、太拖沓，请大声骂。会改。

static double calculate(){    //如果不可再分，则返回    if (itemlist.Count == 1)        return itemlist[0].num;    if (itemlist.Count == 2)        return bycalculate(itemlist[0].op, itemlist[1].num);    if (itemlist.Count == 3)        return tricalculate(itemlist[0].num, itemlist[1].op, itemlist[2].num);    //maxlvel：最高优先级 maxpoint：最高优先级点 depth：括号深度(优先程度)    int maxlevel = 0, maxpoint = 0, depth = 0;    //i搜索最高优先最小子运算    for (int i = 0; i < itemlist.Count; ++i)    {        if (itemlist[i].op != '~')        {            if (itemlist[i].op == '(')                depth++;            else if (itemlist[i].op == ')')                depth--;            else            {                if (oplevel(itemlist[i].op) + depth * 4 > maxlevel)                {                    maxlevel = oplevel(itemlist[i].op) + depth * 4;                    maxpoint = i;                }            }        }    }    double minres = 0;    if (itemlist[maxpoint].op == 'n' || itemlist[maxpoint].op == 's' || itemlist[maxpoint].op == 'c' || itemlist[maxpoint].op == 't')    {        minres = bycalculate(            itemlist[maxpoint].op,            itemlist[maxpoint + 1].num);        itemlist[maxpoint] = new Operand(false, '~', minres);        itemlist.RemoveRange(maxpoint + 1, 1);    }    else    {        minres = tricalculate(        itemlist[maxpoint - 1].num,        itemlist[maxpoint].op,        itemlist[maxpoint + 1].num);        itemlist[maxpoint - 1] = new Operand(false, '~', minres);        itemlist.RemoveRange(maxpoint, 2);    }    //删除不必要的括号    delbracket();    //继续递归    return calculate();}
           

‍

    在这一过程中发生了什么呢？

    如果把这一熟悉的式子作为递归输入值。那么在第一次递归后，它被还原为：

    以上式为参数开始第二次递归。显然地，上式是一个简单式，程序直接计算它的结果，并返回。

绘制函数图像

   对定义域中每个x计算一次f(x)，得到一个二维数组：

    显然，Res中每一个数对都可以表示为平面直角坐标系中的一个点(xi, f(xi))

    要在计算机中建立这样的坐标系，一种理想的方式是建立一个二维数组，数组中的每个点都表示离散的坐标系中某种可能的取值。

    问题是，在一个自左而右、自上而下打印字符的命令行环境下，直接打印这个数组等价于建立下面这样的坐标系：

    解决这一问题的方法无外乎二：其一：自下而上地打印这个数组；其二：将原坐标系的坐标用新坐标系表示。我们选择第二种

选择难一些的方法是为写的烂货代码赎罪

    在换系之前，还必须完成下面的工作：

    为了把定义域上的函数图像完整、饱满地绘制出来，需要确定坐标系内一个单位长度对应的显示长度。这就是说：将数学上的单位转化为计算机的显示单位。在这里，一个显示单位的长度是固定的，即命令行环境中一个字符的宽度或高度。

    式中，Unit是1单位长度对应的显示长度。Size是显示区域用显示长度单位表示的边长。Range(x)是定义域宽度，Range(y)是值域宽度。为了让函数完整地显示，且x、y轴显示单位长度相等，这里的分母需要取Rangex与Rangey间的较大值。

    也就是说，如果值域或定义域很大，要完整显示定义域上的函数，就必须把Unit定义得小一些。

    之所以要在Size上-1，是计算机索引从0开始计数的缘故。试想：若不减一，函数最大值点的纵坐标将是Size，而graph的最大索引是size-1。

    然后就是愉悦地换系。要将：

    转化为：

    满足：

    其中[]为四舍五入。四舍五入是必要的，这是因为在离散的graph[][]中，索引必须是自然数。

    如果x轴和y轴在显示域内，还可以把它们在x'-y'坐标系中表示出来。

    以上就是本例中换系的数学原理。如何实现呢？

static int[] drawgraph(double[][] res, int size){    double xmin = 0, xmax = 0, ymin = 0, ymax = 0;    foreach (double[] dot in res)    {        xmax = Math.Max(xmax, dot[0]);        xmin = Math.Min(xmin, dot[0]);        ymax = Math.Max(ymax, dot[1]);        ymin = Math.Min(ymin, dot[1]);    }    double xrange = xmax - xmin;    double yrange = ymax - ymin;    double unit = (size - 1) / Math.Max(xrange, yrange);    if (xmin <= 0 && xmax >= 0)    {        for (int i = 0; i < size; ++i)            graph[i][(int)((0 - xmin) * unit)] = '|';    }    if (ymin <= 0 && ymax >= 0)    {        for (int i = 0; i < size; ++i)            graph[size - 1 - (int)((0 - ymin) * unit)][i] = '═';    }    foreach (double[] dot in res)    {        try        {            graph[size - 1 - (int)((dot[1] - ymin) * unit)][(int)((dot[0] - xmin) * unit)] = '*';        }        catch (Exception ex)        {            continue;        }    }    return new int[] { (int)(xrange * unit), size - 1 - (int)(yrange * unit) };}
           

‍

    这段程序在换系后，把函数图像经过的每个点用字符'*'替代。把x轴上的每个点用双横线制表符替代，把y轴上的每个点用竖线制表的

以上内容在控制台上的表现

    其中每个函数图像在绘制时都选择了比较能显示其特性的定义域。

注：x取的数目较少

    可以发现，这一程序在控制台上对函数图像的拟合并不明显。这是因为：

1. 显示区域设置得较小
2. 控制台字符并非正方形，这使得y=x的斜率在1到2之间。
3. 许多细节在取整中被遗失了(本质上这也是显示区域的问题，假使显示区域无限大，取整不造成影响)
4. 无限趋近于x轴的函数与x轴重合。这也是因为取整的缘故，而且调整显示区域于事无补。
5. sinx这样的奇函数不精确过零点。这是因为在对称的区间内取了偶数个点。

但是，作为在新宿舍里吃饱了撑着的产物，我认为这已经算成功了。

[0]：五大算法之一，分治算法 ，算法与数据挖掘(百家号)，2019-05-27

在给张碑林拿去拍nt视频前，这块白板被用来打草稿

经活鱼格勒低能教材审核机器

2020年初审通过

子虚高中乌有实验教科书

活鱼格勒

必修x'-y'

函数图像

鬼人扬 马人王

无情的电子诗人一号 编著

为了创造剥削，我开了赞赏。还有，赞赏所得将被用于自我放纵。