用C++编写程序 动态规划

答案：
//==
#include <iostream>
using namespace std;
#include <cmath>
//--
struct Coordinate  //顶点
{
float x;
float y;
};
//--
float Module(Coordinate a,Coordinate b)  //求两点的模值
{
float module=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
return (float)sqrt(module);
}
//--
float W(Coordinate a,Coordinate b,Coordinate c)  //权函数
{
return Module(a,b)+Module(b,c)+Module(a,c);
}
//--
void Triangle_Dissect(Coordinate v[11],float m[10][10],int s[10][10],int n)  //最优剖分
{
for(int i=1;i<n;i++)
{
m[i][i]=0;
}
for(int l=2;l<=n-1;l++)
{
         for(i=1;i<=n-l;i++)
         {
             int j=i+l-1;
             m[i][j]=m[i+1][j]+W(v[i-1],v[i],v[j]);
 s[i][j]=i;
             for(int k=i;k<=j-1;k++)
             {
                 float q=m[i][k]+m[k+1][j]+W(v[i-1],v[k],v[j]);
 if(q<m[i][j])
                 {
                      m[i][j]=q;
                      s[i][j]=k;
                  }
              }
         }
}
}
//--
bool judge(Coordinate a,Coordinate b,Coordinate v[11],int n)  //判断能否构成凸多边形
{
float t[11];
int j=0;
int k=0;
for(int i=0;i<n;i++)
{
if(a.x==b.x)
t[i]=v[i].x-a.x;
else if(a.y==b.y)
t[i]=v[i].y-a.y;
else
t[i]=(v[i].y-a.y)/(b.y-a.y)-(v[i].x-a.x)/(b.x-a.x);
}
for(i=0;i<n;i++)
{
if(t[i]>0)
j++;
if(t[i]<0)
k++;
}
if(j==n-2||k==n-2)
return true;
else
return false;
}
//--
bool input(Coordinate v[11],int n)  //输入顶点坐标，并判断能否构成凸多边形
{
for(int i=0;i<n;i++)
{
cout<<"输入顶点v"<<i<<"坐标";
cin>>v[i].x>>v[i].y;
}
int t[11];
for(i=0;i<n;i++)
{
if(i==n-1)
t[i]=judge(v[i],v[0],v,n);
else
t[i]=judge(v[i],v[i+1],v,n);
}
int j=0;
for(i=0;i<n;i++)
{
if(t[i]>0)
j++;
}
if(j==n)
return true;
else
return false;
}
//--
void outputm(float a[10][10],int n)  //输出数组m中保存的数据
{
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(j<i)
{
cout.width(16);
cout<<"*";
}
else
{
cout.width(16);
cout<<a[i][j];
}
}
cout<<endl;
}
}
//--
void outputs(int a[10][10],int n)  //输出数组s中保存的数据
{
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(j<=i)
{
cout.width(12);
cout<<"*";
}
else
{
cout.width(12);
cout<<a[i][j];
}
}
cout<<endl;
}
}
//--
void Triangle_Print(int i,int j,int s[10][10])  //输出最优剖分出的全部三角形
{
if(i==j)
return;
Triangle_Print(i,s[i][j],s);
Triangle_Print(s[i][j]+1,j,s);
cout<<"三角形:v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl;
}
//--
void main()
{
int n; 
Coordinate v[11];  
float m[10][10];  
int s[10][10];
cout<<"输入顶点个数，限定10个"<<endl;
cin>>n;
if(n>10)
cout<<"输入有误"<<endl;
else
{
cout<<"输入各顶点坐标"<<endl;
if(input(v,n))
{
Triangle_Dissect(v,m,s,n);
cout<<endl<<"数组m中记录的数据为:"<<endl;
outputm(m,n);
cout<<"数组s中记录的数据为:"<<endl;
outputs(s,n);
cout<<"最优凸多边形三角剖分为："<<endl;
Triangle_Print(1,n-1,s);
}
else
cout<<"不能构成凸多边形"<<endl;
}
}
//===
呵呵 这类问题好难 写了一整天啊 学到了很多 还是有收获的
//最优凸多边形三角剖分算法
#include "iostream"
#include "math.h"
 using namespace std;
 typedef struct 
  {
     double x;
     double y;
 }point;
 double distanse(point x,point y)
  {
     double dis= (y.y-x.y)*(y.y-x.y)+(y.x-x.x)*(y.x-x.x);
     return sqrt(dis);
 }
 int main()
  {
     int m;cin>>m;
     int x,i,j,k,d;
     double temp;
     for( x=0;x<m;x++)
      {
     int n;cin>>n;
          point *v =new point[n];
     for(i=0;i<n;i++)
              cin>>v[i].x>>v[i].y;
     double **t=new double*[n];
     for(i=0;i<n;i++)
      {
              t[i]=new double[n];
              t[i][i]=0;
          }
     for(d=2;d<n;d++)
      {
         for(i=1;i<n-d+1;i++)
          {
                  j=i+d-1;
                  t[i][j]=32767;
             for(k=i;k<j;k++)
              {
                 if(k==i) 
                  {//一条直线和一个多边行 v[i-1] v[k]         v[k] v[j]
                     if(j-k==1) temp=0;
                     else temp=t[i][k]+t[k+1][j]+distanse(v[k],v[j]);            
                      }
                 else
                  {
                     if(j-k==1)
                      {//一个多边形和一条直线 v[i-1] v[k]        v[k] v[j]
                              temp=t[i][k]+t[k+1][j]+distanse(v[k],v[i-1]);
                          }
                     else
                          temp=distanse(v[k],v[j])+distanse(v[i-1],v[k])+t[i][k]+t[k+1][j];
                      }
             if(temp<t[i][j])
                          t[i][j]=temp;
                  }
              }
          }cout.precision(4);
          cout<<t[1][n-1]<<endl;
     if(x!=m) cout<<endl;
          }
     return 0;
 }

上一个：一道C++程序出错了，求解。
下一个：C++制表符"\t”的用法