西工大计算机实习报告

计算机实习汇报趣味题彩色的圆环：分析图形可知，一共有n个同心圆，外面大圆n等分，然后从每个等分点作所有同心圆的两条切线。假如用极坐标表达，可以很轻易求解切点，代码如下所示：n=10;%同心圆数量m=40;%等分点数R=1;%外圆半径s=0:0.01*pi:2*pi;%控制圆的光滑程度的极坐标角度t=0:2*pi/m:2*pi;%等分点极坐标角度x0=R*cos(t);y0=R*sin(t);%等分点直角坐标color=['b','r','c','g','m','y'];%画图颜色lc=length(color);%颜色数量长度,超过后从头开始fori=1:n%开始同心圆循环r=R/n*i;%目前同心圆半径a=acos(r/R);%切线与圆心线角度（弧度制）x1=r*cos(t-a);y1=r*sin(t-a);%任意等分点相对目前同心圆的第一种切点x2=r*cos(t+a);y2=r*sin(t+a);%任意等分点相对目前同心圆的第二个切点plot(r*cos(s),r*sin(s),color(mod(i,lc)+1));holdon;%画同心圆forj=1:m%对每一种等分点循环plot([x0(j),x1(j)],[y0(j),y1(j)],color(mod(i,lc)+1));holdon;%第一条切线plot([x0(j),x2(j)],[y0(j),y2(j)],color(mod(i,lc)+1));holdon;%第二条切线endendaxsiequal;%横纵坐标比例一致试验绘图成果如下图所示：算法题求无向图的最短途径（Dijkstra算法）：试验原理分析、原理及代码如下所示（此试验代码不仅包括了试验所规定的求带权无向图最短途径，我还拓展了求有向、无向、带权有向图最短途径的内容）：#include<iostream>#include<iomanip>usingnamespacestd;#definewuqiong0classtu{public: intchazhao(int);//查找 voidzjdingdian(intx);//增长顶点 tu(); voidzengjia();//控制增长弧边和点 voidzjhubian();//增长弧边 voidbianli();//控制遍历 voidshendu(int);//深度 voidguangdu(int);//广度 voidjindui(int);//进队列 intchudui();//出对了 boolpankong();//判空 //上面所有的函数与邻接矩阵有关 voidzxgouzao();//初始化与最小路劲有关的东东 voidzxshuchu();//求S中的最小路劲private: intkind;//类图； intlength;//顶点个数 int*dingdian;//顶点int*juzhen;//矩阵 intnum;//最大顶点数目 int*visted;//访问状况 int*duilie;//模拟队列 intduichang;//队列长度 //上面所有的变量与邻接矩阵有关 int*s;//寄存目前顶点 intslength;//目前顶点的长度 int*dist;//寄存最小路劲 int*pre;//寄存路劲; int*final;//寄存顶点};tu::tu()//初始化图{cout<<"请输入图的种类1:有向.2:无向.3:带权有向.4:带权无向"<<endl;//图的种类cin>>kind;cout<<"请输入图的顶点数目"<<endl;//为顶点赋值cin>>num;dingdian=newint[num];//为顶点分派内存保留juzhen=newint[num*num];//产生矩阵if(kind==1||kind==2)//为无权图初始化矩阵{for(inti=0;i<num*num;i++) juzhen[i]=0;}else//有权图初始化矩阵{ for(inti=0;i<num*num;i++) juzhen[i]=wuqiong;}length=0;}//增长顶点voidtu::zjdingdian(intx){ if(chazhao(x)!=-1||length==num) cout<<"图内有此顶点或图内无空间可插入，插入失败"<<endl; else { dingdian[length]=x; length++; }}//增长边voidtu::zjhubian(){ inti;//弧头 intj;//弧尾 if(kind==1||kind==2)//无权图 { cout<<"请输入弧的头和尾"<<endl; cin>>i>>j; if(kind==1)//有向图 { juzhen[i*num+j]=1; } else//无向图，两边同步取值 { juzhen[i*num+j]=1; juzhen[j*num+i]=1; } } else//权值，同上，将1改为K(权值)即可 { intk; cin>>i>>j>>k; if(kind==3) { juzhen[i*num+j]=k; } else { juzhen[i*num+j]=k; juzhen[j*num+i]=k; } }}//查找,将该数所在位置返回，若无则返回-1inttu::chazhao(intx){ for(inti=0;i<length;i++) if(x==i) returni; return-1;}//控制遍历函数voidtu::bianli()//遍历函数{ cout<<"该图的邻接矩阵为:"; inti; intj; for(i=0;i<length;i++)//将矩阵输出 { cout<<endl; for(j=0;j<length;j++) cout<<setw(6)<<juzhen[i*length+j]<<""; } cout<<endl; visted=newint[length];//为设置访问状态定义内存空间 cout<<"深度搜索:"; for(i=0;i<length;i++)//所有初始化为0即未访问状态 visted[i]=0; shendu(0);//将0作为0点运用深度访问函数 cout<<endl; cout<<"广度搜索:";for(i=0;i<length;i++)//重新设置访问状态 visted[i]=0; duilie=newint[length+1]; duilie[0]=-1;//队列初始化 duichang=0; guangdu(0);//将0作为0点运用广度访问函数}//深度遍历voidtu::shendu(intx)//采用递归的手法{ intp; visted[x]=1;//访问后置1防止反复访问 cout<<x<<""; p=x*length+1; while(p%length!=0) { if(juzhen[p]!=0&&visted[p%length]!=1)shendu(p%length); p++; }}//广度遍历voidtu::guangdu(intx){intp;visted[x]=1;cout<<x<<"";p=length*x+1;while(p%length!=0)//没有遍历属于根节点的后裔的所有兄弟结点加入到队列中(这样可以先进先出，后来的子代加入后也是先输出父亲结点){ if(juzhen[p]!=0&&visted[p%length]!=1) { visted[p%length]=1;//判断与否已经加入队列或访问 jindui(p%length); } p++;//进行下一种判断}while(pankong())//加入所有的子代兄弟节点后目前出队列并且访问，访问的方式一致会访问后优先加入其子代结点然后出队列访问{ guangdu(chudui());}}//进队列,在队头插入一种函数，这个出队入队为了广度输出voidtu::jindui(intx){duilie[duichang+1]=-1;duilie[duichang]=x;duichang++;}//出队列,将队列中的最终一种数返回inttu::chudui(){ intj; j=duilie[0];for(inti=0;i<duichang;i++) duilie[i]=duilie[i+1]; duichang--; returnj;}//判空函数，函数为空的时候返回0booltu::pankong(){ if(duichang==0) returnfalse; else returntrue;}//控制增长函数voidtu::zengjia(){ intj; for(inti=0;i<num;i++)//插入顶点 zjdingdian(i); cout<<"请输入需要增长的弧数(至少"<<num-1<<"条且保证连通)"<<endl;//插入弧 cin>>j; cout<<"请输入弧的头和尾和权值"<<endl; for(i=0;i<j;i++) { //cout<<"插入第"<<i+1<<"条弧"<<endl; zjhubian(); } }/***算法思想:依次递增序列求出最小路劲，首先将顶点加入到S当中(本程序默认为0号顶点),然后用dist数组保留到每一种顶点的最小途径长度**dist起始为顶点到其他顶点的权值(到自身为0，到无弧顶点为无穷大)**1:然后每次取v0-vk(k属于V-S)最小的路劲长度,取完之后将Vk加入S当中。**2:重新对所有的dist[i(属于v-s的i)]赋值，假如新加入的那个点到i的权值不不小于本来的权值则dist[i]=dist[k]+wki;**反复1，2懂得S=V;退出程序*/voidtu::zxgouzao()//最短途径求解{ intn,i;//n为顶点 n=0; final=newint[length];//访问状态 s=newint[length];//所求的顶点集合 dist=newint[length];//所有的最短途径 pre=newint[length];//每一种最短途径的前驱结点(运用这个将最短途径求出) for(i=0;i<length;i++) { pre[i]=n;//起初所有将前驱赋为源点 final[i]=0;//访问状态为0(即没有加入S当中) if(i==n)//源点自身的dist为0 dist[i]=0; else dist[i]=juzhen[n*length+i];//源点到目的顶点的dist初始化为权值 } pre[n]=-1;//源点前驱设为-1 s[0]=dingdian[0];//加入源点(本程序默认源点为0) final[0]=1;//源点加入S当中 slength=1;//S的长度为1 inth,h1;//定义两个要用到的变量 while(slength<length) { h=wuqiong+1;//首先将路劲设置成最大化，这样就可以将所有的路劲比较一番而后取最小值，这个值尽量比所有的权值要大！ for(i=0;i<length;i++) { if(!final[i]&&dist[i]<=h)//依次对任意顶点进行判断与否已经加入S当中，假如没加入则判断他的路劲与否最小，取最小路劲 { h=dist[i]; h1=i; } } s[h1]=h1;//取完之后将其保留到S当中 slength++;//S的长度+1 final[h1]=1;//h1已经访问了加入到S当中，将其设为0 for(i=0;i<length;i++)//重新设置dist[i]的值，i属于v-s;由于v-s中的点到v中点的最小路劲也许发生了变化，变化的主线在于h1的加入 { if(!final[i]&&dist[h1]+juzhen[h1*length+i]<dist[i])//判断h1与否会引起dist的变化，假如变化后不不小于本来的，则将目前的保留 { dist[i]=dist[h1]+juzhen[h1