spotted-deer / c-algorithm Goto Github PK

#include
using namespace std;

void OptimalBinaryTree(double a, double b, int n, double *w, double m, int s)
{//s存储结点，w记录其下标从i到j概率总和（成功b和失败a），m记录期望值，最小即最优
for (int i = 0; i <= n; i++)
{
w[i + 1][i] = a[i];
m[i + 1][i] = 0;//i>j的情况处理，i<=j在下边
}
for (int r = 0; r < n; r++){//r控制长度
for (int i = 1; i <= n - r; i++)
{
int j = i + r;
/问题在这/
w[i][j] = a[j] + b[j]+w[i][j - 1] ;
//warning！！写成a[j] + b[j]+w[i][j - 1]是错的，写成w[i][j - 1] + a[j] + b[j]是对的！！呵呵！！
/********************************************************************/
m[i][j] = m[i + 1][j];
s[i][j] = i;//相当于每一行的初始化
cout << s[i][j] << " ";
for (int k = i + 1; k <= j; k++)
{
double temp = m[i][k - 1] + m[k + 1][j];
if (temp < m[i][j])//如果第k个小就替换
{
m[i][j] = temp;
s[i][j] = k;
cout << s[i][j] << endl;
}
}
m[i][j] += w[i][j];
}cout << endl;
}
}

void TraceBack(int i, int j, int **s)
{
if (j>i)//右上角矩阵
{
int root = s[i][j];
cout << "S" << root << "是根节点" << endl;
if (s[i][root - 1]>0)
cout << "S" << root << "的右孩子是S" << s[i][root - 1] << endl;
if (s[root + 1][j]>0)
cout << "S" << root << "的左孩子是S" << s[root + 1][j] << endl;
TraceBack(i, root - 1, s);
TraceBack(root + 1, j, s);
}
}

int main()
{
int n, i;
cout << "please input the number of node:";
cin >> n;
double *b = new double[n + 1];//成功概率，从下标开始
double *a = new double[n + 1];//失败概率，从下标开始，下标代表所有搜索都失败的概率
double *w = new double[n + 2];
double *m = new double[n + 2];//n+2如果是n+1会越界
int *s = new int[n + 2];//在traceback中越界，所以是n+2
for (i = 0; i <= n + 1; i++)
{
w[i] = new double[n + 2];
m[i] = new double[n + 2];
s[i] = new int[n + 2];
}
cout << "please input the success rate:";
for (i = 1; i <= n; i++)
cin >> b[i];
cout << "please input the fail rate:";
for (i = 0; i <= n; i++)
cin >> a[i];
//double b[n + 1] = { -1, 0.15, 0.1, 0.05, 0.1, 0.2 };
//double a[n + 1] = { 0.05, 0.1, 0.05, 0.05, 0.05, 0.1 };
for (i = 0; i <= n + 1; i++)
{
for (int j = i - 1; j >= 0; j--)
{
m[i][j] = 0;
w[i][j] = 0;
s[i][j] = 0;
}
}
OptimalBinaryTree(a, b, n, w, m, s);
TraceBack(1, n, s);
cout << endl;
for (i = 1; i <= n+1; i++)
{
for (int j = 0; j <= n; j++)
{
cout << w[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (i = 1; i <= n+1; i++)
{
for (int j = 0; j <= n; j++)
{
cout << m[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (i = 1; i <= n+1; i++)
{
for (int j = 0; j <= n; j++)
{
cout << s[i][j] << " ";
}
cout << endl;
}
cout << endl;

for (i = 0; i <= n + 1; i++)
{
	delete[] w[i];
	delete[] m[i];
	delete[] s[i];
}
delete[] w;
delete[] m;
delete[] s;
delete[] a;
delete[] b;
system("pause");

}