新普金娱乐网址


极端充分流动, 最小割问题同算法实现

撕下了一致页一页的日历,就到高考了

数学JavaScript与Lisp,通向编程圣殿[1]: “树”的根底测算

  • 十月 03, 2018
  • 数学
  • 没有评论
作者:feiquan

出处:http://www.cnblogs.com/feiquan/

版权声明:本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

大家写文都不容易,请尊重劳动成果~ 这里谢谢大家啦(*/ω\*)

JavaScript于规划时,注入了Scheme的血流,虽然设计者为“商业”目的,为夫绷上了“C外衣”和“面向对象的礼帽”,但是那个本质上该是Lisp的,Lisp的沉思,我们好当JavaScript作出相同的学,你只是待采取“子集”,抛开伪装的“C外衣”和浮泛的“面向对象礼帽”。

  首先,我们用仓储一个立方的连带信息。

历史及大势为我渐渐相信,在初期,我们需要再优化更省资源的编程方式,能让机器运转的代码更产生价,随着电脑硬件的进步,“节省资源”“高并作”“分布式”都用不再是用考虑的,智能化的次序将会晤成为主导。

   创建类Point_3V来存放三维点,Line_2V来存放在二维点,Line来存放三维线,Line_2V来存放在二维线,face_2V来存放二维面,face来存放三维面,cube来定义一个矩形。以上的第二维都是因此来平行投影时行使的,三维则是存放在于三维空间受到真正是的矩形的信,且立即几乎单三维类之间下了看似的存续来实现。

很多年前,许多口都嘲笑JavaScript,至今还发生,只是为其简要低效的浮点数计算和一味难以预测的档次系统,至今还来人数于用类型系统说事,你甚至看TypeScript加入了型系统。

  有关面的检测,使用了里检测法。

呵呵~~~

  有关面的填充,使用了子填充。

校友,Lisp中是不曾路系统宣称的,即便要编译器有,但是编写过程是从未有过的,这虽是JavaScript为什么从来不。

  代码如下:

JavaScript深众化的“C外衣”让他以浏览器获得了榜首的地位,但是只有明智之士才知:JavaScript之所以可流行,是乘内部轻量、逻辑有序的数据结构和计量办法,而这些还是Lisp的魂所在。

  

再过几年,或者10年,高并发分布式将不再是主题,因为实现他们都非常简单。智能化的主次,可分析的次序用见面成为主题。即数学将会见变成真正的程序。现在就来矣有JavaScript的机上库,甚至神经网络库,虽然还尚无常见采用,但是硬件速度之升级换代肯定会要其大放异彩。

//3V_Point三维点
class Point_3V{
public:
    double x,y,z;
    bool v;

    Point_3V(){
        x=0;y=0;z=0;
        v=false;
    }
    Point_3V(double a,double b,double c){
        x=a;y=b;z=c;
        v=false;
    }
    Point_3V(double a,CPoint p){
        x=a;y=p.x;z=p.y;
        v=false;
    }
    Point_3V(CPoint p,double a){
        x=p.x;y=p.y;z=a;
        v=false;
    }
    void set_Point(double a,double b,double c){
        x=a;y=b;z=c;
    }
    void set_Point(Point_3V p){
        x=p.x;y=p.y;z=p.z;
    }
    void set_Point(Point_3V *p){
        x=p->x;y=p->y;z=p->z;
    }
    //投影一个三维点,返回投影点
    CPoint reflect_Point_3V(Point_3V v,CPoint move){
        CPoint p2;
        double  a,b;
        a=this->x-v.x/v.z*this->z+move.x;
        b=this->y-v.y/v.z*this->z+move.y;

        p2.SetPoint((int)a,(int)b);
        return p2;
    }
};

//二维线
class Line_2V{
public :
    CPoint start,end;
    Line_2V(){
        start.SetPoint(0,0);
        end.SetPoint(0,0);
    }
    Line_2V(CPoint x,CPoint y ){
        start=x;end=y;
    }
    void fill(CDC *p){
        p->MoveTo(start);
        p->LineTo(end);
    }
};

//基于点填充线(不会开辟新空间)
class Line :public Point_3V 
{
public :
    Point_3V *start;
    Point_3V end;
    bool v;
    Line(){
        start=new Point_3V[1];
        v=false;
    }
    Line(int a,int b,int c ,Point_3V e ):Point_3V(a,b,c),start(this),end(e){
        v=false;
    }
    Line( int s_x,int s_y,int s_z,int e_x,int e_y,int e_z):Point_3V(s_x,s_y,s_z),start(this),end(e_x,e_y,e_z){
        v=false;
    }
    Line(Line *p){
        this->start=p->start;
        this->end=p->end;
        v=false;
    }
    //三维线投影
    Line_2V reflect_Line(Point_3V v,CPoint move,bool draw,CDC  *p){
        CPoint s=start->reflect_Point_3V(v,move);
        CPoint e=end.reflect_Point_3V(v,move);
        Line_2V temp(s,e);
        if(draw)temp.fill(p);
        return temp;
    }
    void set_Line(int s_x,int s_y,int s_z,int e_x,int e_y,int e_z){
        this->start->set_Point(s_x,s_y,s_z);
        this->end.set_Point(e_x,e_y,e_z);
    }
    void set_Line(Point_3V s,Point_3V e){
        this->x=s.x;
        this->y=s.y;
        this->z=s.z;
        this->v=s.v;
        this->start->set_Point(s);
        this->end.set_Point(e);
    }
};

class face_2V{
public :
    //逆时针
    Line_2V a,b,c,d;
    face_2V(){

    }
    face_2V(Line_2V i,Line_2V j,Line_2V k,Line_2V l ){
        a=i;b=j;c=k;d=l;
    }

    void B(int x,int y,int c1_fill,int c2,CDC *p){

        //种子填充
        int center=p->GetPixel(x,y);
        if(center!=c1_fill&&center!=c2){
            p->SetPixel(x,y,c1_fill);
            B(x+1,y,c1_fill,c2,p);B(x-1,y,c1_fill,c2,p);
            B(x,y+1,c1_fill,c2,p);B(x,y-1,c1_fill,c2,p);
        }
    }

    void fill(int c1_fill,int c2,CDC *p){
        a.fill(p);b.fill(p);c.fill(p);d.fill(p);
        B(((a.start.x+c.start.x)/2),((a.start.y+c.start.y )/2), c1_fill, c2,p);
    }
};

//基于点填充面(不会开辟新空间)
class face :public Line{
public :
    Point_3V *p;//逆时针
    Line *l1,l2,l3,l4;//l1只能是指针,为了是其与点公用一个存储空间
    bool v;
    face(){
        p=new Point_3V[4];
        l1=new Line[1];
        v=false;
    }
    face(Point_3V *q[4]){
        this->start=q[0];
        this->end=*q[1];

        p=new Point_3V[4];
        l1=new Line[1];

        v=false;
        l1->set_Line(p[0],p[1]);
        l2.set_Line(p[1],p[2]);
        l3.set_Line(p[2],p[4]);
        l4.set_Line(p[4],p[0]);
    }
    face(Point_3V a,Point_3V b,Point_3V c,Point_3V d){
        p=new Point_3V[4];
        l1=new Line[1];
        p[0]=a;p[0]=b,p[0]=c,p[0]=d;
        v=false;

        l1->set_Line(p[0],p[1]);
        l2.set_Line(p[1],p[2]);
        l3.set_Line(p[2],p[4]);
        l4.set_Line(p[4],p[0]);
    }
    face( face *p1){
        p=new Point_3V[4];
        l1=new Line[1];
        this->start=p1->start;
        this->end=p1->end;

        p[0]=p1->p[0];
        p[1]=p1->p[1];

        l1->set_Line(p[0],p[1] );
        v=false;
    }
    face(int s_x,int s_y,int s_z,int e_x,int e_y,int e_z,Line p2,Line p3,Line p4):Line(s_x,s_y,s_z,e_x,e_y,e_z),l1(this),l2(p2),l3(p3),l4(p4){
        p=new Point_3V[4];
        l1=new Line[1];
        v=false;
    }
    void set_Point(Point_3V q[4]){
        for(int i=0;i<4;i++){
            p[i]=q[i];
        }
    }
    void set_Line(){
        l1->set_Line(p[0],p[1]);
        l2.set_Line(p[1],p[2]);
        l3.set_Line(p[2],p[4]);
        l4.set_Line(p[4],p[0]);
    }
    void set_Face(Point_3V q[4]){
        for(int i=0;i<4;i++){
            p[i]=q[i];
        }
        l1->set_Line(p[0],p[1]);
        l2.set_Line(p[1],p[2]);
        l3.set_Line(p[2],p[4]);
        l4.set_Line(p[4],p[0]);
    }
    void set_Face(Point_3V q1,Point_3V q2,Point_3V q3,Point_3V q4){
        p[0]=q1;
        p[1]=q2;
        p[2]=q3;
        p[3]=q4;

        l1->set_Line(p[0],p[1]);
        l2.set_Line(p[1],p[2]);
        l3.set_Line(p[2],p[3]);
        l4.set_Line(p[3],p[0]);
    }
    //三维向量的向量积
    Point_3V xiangliangji( Point_3V a ,Point_3V b){
        //矩阵形式,和i,j,k是否为偶数或奇数有关,切记
        return Point_3V(a.y*b.z-a.z*b.y,-(a.x*b.z-a.z*b.x),a.x*b.y-a.y*b.x);
    }

    //三维向量的点乘
    double diancheng( Point_3V a ,Point_3V b){
        double temp=a.x*b.x+a.y*b.y+a.z*b.z;
        return temp;
    }

    //求一个面的法向量,输入一个面按逆时针方向的所有点的数组
    Point_3V n( face *one_face){
        Point_3V a,b,n;
        if(one_face->p!=NULL){
            a.set_Point(one_face->p[1].x-one_face->p[0].x,one_face->p[1].y-one_face->p[0].y,one_face->p[1].z-one_face->p[0].z);
            b.set_Point(one_face->p[2].x-one_face->p[0].x,one_face->p[2].y-one_face->p[0].y,one_face->p[2].z-one_face->p[0].z);
            n=xiangliangji(a,b);
            return n;
        }else{
            return n;
        }
    }

    //判断一个面是否可见,如果一个面可见,则这个面上的四个点也可见
    bool view_face(face *one_face, Point_3V v){
            double cos,a_mo,b_mo;

            //求一个面的法向量
            Point_3V fa;
            fa=n(one_face);

            double a_temp=pow((double)fa.x,2)+pow((double)fa.y,2)+pow((double)fa.z,2);
            a_mo=sqrt(a_temp);
            double b_temp=pow(v.x,2)+pow(v.y,2)+pow(v.z,2);
            b_mo=sqrt(b_temp);
            double fz=diancheng(fa,v);
            double fm=a_mo*b_mo;
            cos=fz/fm;
            if(cos<=0){
                one_face->v=true;
                //判断这个多边形体的各个点是否可见
                for(int j=0;j<4;j++){
                    one_face->p[j].v=true;
                }
                return true;
            }else{
                return false;
            }
    }

    //3V面投影
    void reflect_Face(Point_3V v,CPoint move,bool draw_Line,bool fill_face,int c1_fill,int c2,CDC  *p){
        if(view_face(this,v)){
            Line_2V l2_1=l1->reflect_Line(v,move,draw_Line,p);
            Line_2V l2_2=l2.reflect_Line(v,move,draw_Line,p);
            Line_2V l2_3=l3.reflect_Line(v,move,draw_Line,p);
            Line_2V l2_4=l4.reflect_Line(v,move,draw_Line,p);
            if(fill_face){
                face_2V f2(l2_1,l2_2,l2_3,l2_4);
                f2.fill(c1_fill,c2,p);
            }
        }
    }

};


//多边形 p+f-l=2
class cube{
private:
    bool isCube;
public :
    int point_num,face_num,line_num;
    Point_3V p[8];
    Line l[12];
    face f[6];
    cube(){
        point_num=0;
        face_num=0;
        line_num=0;
    }
    cube(int point_nums,int line_nums,int face_nums){
        if(point_nums+face_nums-line_nums==2){//公式
            point_num=point_nums;
            face_num=face_nums;
            line_num=line_nums;
            /*p=new Point_3V[point_num];

            l=new Line[line_num];

            f=new face[face_num];*/

            isCube=true;
        }else{
        cube();
        isCube=false;
        }
    }

    void set_Point(Point_3V *point){
        for(int i=0;i<point_num;i++){
            p[i]=point[i];
        }

    }

    void set_cube(Point_3V *point){
        set_Point(point);

        //上下 左右 前后 
        f[0].set_Face(p[0],p[1],p[2],p[3]);//上
        f[1].set_Face( p[7],p[6],p[5],p[4]);//下 

        f[2].set_Face(p[0],p[4],p[5],p[1]);//左
        f[3].set_Face(p[3],p[2],p[6],p[7]);//右 


        f[4].set_Face(p[1],p[5],p[6],p[2]);//前
        f[5].set_Face(p[0],p[3],p[7],p[4]);//后 
    }

    void reflect_Cube(Point_3V v,CPoint move,bool draw_Line,bool fill_face,int *c1_fill,int c2,CDC  *p){
        f[0].reflect_Face(v,move,draw_Line,fill_face,c1_fill[0],c2,p);
        f[1].reflect_Face(v,move,draw_Line,fill_face,c1_fill[1],c2,p);

        f[2].reflect_Face(v,move,draw_Line,fill_face,c1_fill[2],c2,p);
        f[3].reflect_Face(v,move,draw_Line,fill_face,c1_fill[3],c2,p);

        f[4].reflect_Face(v,move,draw_Line,fill_face,c1_fill[4],c2,p);
        f[5].reflect_Face(v,move,draw_Line,fill_face,c1_fill[5],c2,p);
    }

    void fill( int p){
        switch(p){
        case 0: {point_num=2+line_num-face_num;} break; //已知其它两个,求点
        case 1:{line_num=point_num+face_num-2;}break;//已知其它两个,求线
        case 2:{face_num=2+line_num-point_num;}break;//已知其它两个,求面
        }
    }

};

void CMy1View::OnDraw(CDC* pDC)
{
    CMy1Doc* pDoc = GetDocument();
    ASSERT_VALID(pDoc);
    if (!pDoc)
        return;

    // TODO: 在此处为本机数据添加绘制代码

    Point_3V  p[8]={ 
        Point_3V(0,0,100),//0
        Point_3V(100,0,100),//1
        Point_3V(100,100,100),//2
        Point_3V(0,100,100),//3
        Point_3V(0,0,0),//4
        Point_3V(100,0,0),//5
        Point_3V(100,100,0),//6
        Point_3V(0,100,0)//7
    };

    //偏移量
    CPoint move;
    move.SetPoint(200,200);

    //视点
    Point_3V v(1,1.2,1);

    //颜色
    int color[6]={RGB(255,0,0),RGB(0,255,0),RGB(0,0,255),RGB(255,255,0),RGB(255,0,255),RGB(0,255,255)};
    //cube
    int point_num=8,face_num=12,line_num=6;
    cube cb(point_num,face_num,line_num);
    cb.set_cube(p);
    cb.reflect_Cube(v,move,true,false,color,0,pDC);//线框模式
    //cb.reflect_Cube(v,move,true,true,color,0,pDC);//填充模式
}

据此,从现在始于,掌握JavaScript的Lisp本质是可怜主要的,这会为咱们刻画起更加“智慧”的次。

实验结果

陶铸之主干

吃咱来点莫过于的东西,无论言语多么鲜华,没有干脆清晰的解决问题,都是架空的。所以,让咱们于Lisp的本色开始,也是Lisp的绝无仅有:列表开始。

当任何的编程语言课程,更欣赏用“Tree树”这个字来形容,那么受咱们来拘禁同样棵树:

        A
   /  /   \  \
  B   C    D   E
 /   / \
F   G   H

头的及时颗树,如何用程序来代表也?
作JavaScript,你得为此JSON来代表,用数组对象表示。

那么Lisp是怎表示的?

(A (B F) (C G H) D E)

立就是是Lisp的列表表示法,只发一个方(元素 ...),然后因这递归。
咱得以形容来一致之JavaScript方式:

['A', ['B', 'F'], ['C', 'G', 'H'], 'D', 'E']

密切查看,你非常轻就能够查获一个原理:
她们都是利用数组嵌套的,并且递归

于一些层面来讲,JavaScript的作者毕为及时门语言融入了Lisp的列表,虽然尚未提供方便的car
cdr函数,但是一旦想如果效仿,是蛮便宜之。

 数学 1                         
          数学 2

复扑朔迷离的同等棵树

吃咱更管培植做的稍复杂一点,看看当怎么用JavaScript表示:

        A
   /  /   \  \
  B   C    D   E
 /   / \    \
F   G   H    I
   /     \
  J       K

冲我们地方的演绎,可以如此表示马上棵树:

['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E']
  • 使用数组表示节点
  • 一致株树本身便是一个专门深之节点,所以树即是节点,树即是数组
  • 各国一个主节点,是一个数组的首先件
  • 各个一个数组第一起后面的备因素,都是该数组第一桩的直接字节点

如利用Lisp来表示,那么就棵树就是一个列表:

(A (B F) (C (G J) (H K)) (D I) E)

今,你应该了解,表示同样棵树,在JavaScript中凡多么好,多么的Lisp吧!

              线框                                        
             填充

否培养添加计

叫咱描绘单程序,来把咱才的树绘制一下,来代表一下JavaScript的Lisp血统。

依,我们形容个次,输入

['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E']

每当控制台上打印出这么的培育图形:

A
  B
    F
  C
    G
      J
    H
      K
  D
    I
  E

当节点的深浅增加一个不时,打印的字符前面加2个空格,这个培训图形字符串表示如下:

A\n  B\n    F\n  C\n    G\n      J\n    H\n      K\n  D\n    I\n  E\n

今日于咱们来编写Lisp血统的JavaScript程序:

  1. 一个盘算空格的次序

    率先我们要一个会计算空格的顺序。当节点在0深度时,输出0单空格,第一单深时,输出1只空格,第2只深时,输出2独空格,这样咱们才会行打印

    A
      B
    ...
    

    如此的格式字符。

    function spaces(n) {
        return (function walk(i, spaces) {
            if (i <= 0) {
                return spaces;
            }
            return walk(i - 1, spaces + '  ');
        } (n, ''));
    }
    

    就是死Lisp的先后,使用了递归的点子,来计算空格。
    当输入要求n的时候,这个次递归计算,返回所有的空格。

    spaces(3) => '   ' 
    
  2. 一个乘除字符的顺序

    富有的递归操作都得以就此“左->右”来表示
    咱们无停歇的算计“左”的价,然后将她们相加

    概念计算(节点):
    万一节点是一个字符: 返回字符
    如节点是一个空结构:返回”
    其余,有效节点:   返回结果 = 计算(节点第一码) +
    计算(节点后边的项)

    function string(list, deep, isCarList) { 
        // 如果节点是一个字符:返回字符
        if (typeof list === 'string') {
            return spaces(deep) + list + '\n';
        }
        // 如果节点是一个空节点:返回''
        if (list instanceof Array && list.length === 0) {
            return '';
        }
        // 其他,有效节点:返回结果 = 计算(节点第一项) + 计算(节点后边的项)
        var car = list.shift(),
            cdr = list;  
        return isCarList
               ? string(car, deep, false) + string(cdr, deep + 1, false)
               : car instanceof Array
                 ? string(car, deep, true) + string(cdr, deep, false)
                 : string(car, deep, false) + string(cdr, deep, false);
    }   
    

    夫程序定义为string(list, deep, isCarList)。

    list就是各个一个节点的值,最初步是
    [‘A’, [‘B’, ‘F’], [‘C’, [‘G’, ‘J’], [‘H’, ‘K’]], [‘D’,
    ‘I’], ‘E’]。

    咱们取list最左边的宗,即list[0],为了和Lisp保持一致,我们运用了list.shift(),将第一项提取出来,剩下的list作为等操作的新的list,然后对第一码和剩余的list进行递归求值。

    率先宗有或啊是独数组。

    若是您精心察看,你会意识就大像样斐波那契数列,甚至就是是斐波那么契数列。

  3. 打印

    当今足打印我们的主次了:

    console.log(string(['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E'], 0, true));
    

    开拓nodejs控制台,输入程序,你以会望:

    A
      B
        F
      C
        G
          J
        H
          K
      D
        I
      E   
    

    斯树型图。

 

改善版的树形打印程序

末段,发上一个完好无损的改进版:

function spaces(n, star) {
    if (typeof star !== 'string') {
        star = ' ';
    }
    return (function walk(i, spaces) {
        if (i <= 0) {
            return spaces;
        }
        return walk(i - 1, spaces + star + star);
    } (n, ''));
}

function string(list, star) { 
    return (function walk(list, deep, isCarList) {
        if (typeof list === 'string') {
            return spaces(deep, star) + list + '\n' ;
        }
        if (list instanceof Array && list.length === 0) {
            return '';
        }
        var car = list.shift(), cdr = list;  
        return isCarList
               ? walk(car, deep, false) + walk(cdr, deep + 1, false)
               : car instanceof Array
                 ? walk(car, deep, true) + walk(cdr, deep, false)
                 : walk(car, deep, false) + walk(cdr, deep, false);    
    }(list, 0, true));
}

console.log(string(['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E'], '--'));

以此顺序将会见输出这样的一个塑造:

A
----B
--------F
----C
--------G
------------J
--------H
------------K
----D
--------I
----E

备考:为了说明简单,此文中之代码并未开深刻的精打细算优化,特别是缓存,如果你想了解怎么通过缓存记忆进一步升级计算效率,可以参照算法技巧:
如何采取JavaScript编写高效的fabonacci数列。

试行总结:


创建类Point_3V来存放在三维点,Line_2V来存放在二维点,Line来存放在三维线,Line_2V来存放二维线,face_2V来存放在二维面,face来存放在三维面,cube来定义一个矩形。以上之次维都是用来平行投影时采取的,三维则是存放在于三维空间受到真实存在的矩形的音讯,且这几只三维类之间用了接近的接续来落实。


矩形点的输入顺序应该遵照逆时针来输入,这是坐每个面之法向量有些许种植结果,但是下背面检测法,只有向为立方体的外表才为刚刚方向,所以按照逆时针得出这当及简单只非同台线的向阳量,然后要出双方的叉积就可以对得出面的法向量。

l  立方体投影的贯彻思路是(假设数据现已不易输入):

    cube(8点,12棱,6面)-> reflect_Cube(进行立方体的影)->
f[i].reflect_Face(进行    每个面之阴影) ->
view_face(判断这当是否可见,如果可见则拿是面子的4点设置为可   
见;如果不可见则判断下个面是否可见)
->l2.reflect_Line(进行一个面4长条线条线的投 影)->
end.reflect_Point_3V(进行这漫长线的鲜单点投影)->判断是否画线(如果也真正,画  
线;否则不写)


在创建每一个三维真实的触发,线,面时默认不可见,由于采用了,类的累,所以照使创建丝时,要管及时漫漫线之起点是自从基类三维点继承过来的音信,所以应该利用指针,那么在线的构造函数中尽管该也是指针动态的开创一个空间,否则程序执行时,会无法访问这个指针的长空。


以进展编程时,数学功底要实在,我于展开有限独向量的叉积运算时,未考虑到矩阵奇、偶列的标志不同,所以造成结果吧产图所著,最后经断点测试才明白是原因。

 数学 3

 

面填充时的思绪:

用中OnDraw()函数里之cb.reflect_Cube(v,move,true,false,color,0,pDC);

    换位cb.reflect_Cube(v,move,true,true,color,0,pDC);就好。

实验总结:

   
不同颜色之照用了数组中存放不同的颜色信息来兑现,填充方式采用了种填充,种子的职应用了四边形的中坚坐标。

试参考文献:

http://www.docin.com/touch\_new/preview\_new.do?id=489294049&html=1

 补充:

提议大家以运用种子填充时,使用VC6.0,不要因此VS,VS会报错:(世家而出好的主意来化解这题目,请联系我:2283320260@q数学q.com

数学 4

欢迎大家一同座谈

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图