题目如下:令n=2的m次方,A是一个2n维的数组,待求最大值的数存放在A(n),A(n+1),……A(2n-1)中,所求得的最大值置于A(1),于是算法描述如下:
输入:n=2的m次方个数存在数组A(n;2n-1)中;
输出:最大数置于A(1)中。
Begin
For k=m-1 to 0 do
For j=2k+1-1 to 2k par do
A(j)=max(A(2j),A(2j+1))
End For
End For
End
具体实现:
定义全局变量如下,array用于存放产生的随机数。
int g_nCount=0,j=0;
int *array;
随机产生n个数并存于数组array中,程序代码如下:
void CDemoDlg::OnBtnInitial()
{
// 初始化数组
srand((unsigned)time(NULL));
int i,temp;
CString str;
UpdateData(true);
g_nCount=pow(2,m_intCount);
array=new int[2*g_nCount];
//根据用户的输入,产生2的m次方的随机数并存于array[n]…a[2n-1]中
for(i=g_nCount;i<2*g_nCount;i++)
{
temp=rand()/100;
array[i]=temp;
}
//显示产生的n个随机数
for(i=g_nCount;i<2*g_nCount;i++)
{
str.Format("Array[%d]= %d",i,array[i]);
m_strArray+="\r\n";
m_strArray+= str;
m_strArray+="\r\n";
}
m_strArray+="\r\n";
UpdateData(false);
}
void CDemoDlg::OnBtnCompute()
{
// 启动线程进行计算
int k;
for(k=m_intCount-1;k>=0;k--)
{
for(j=pow(2,k);j<POW(2,K+1);J++)
{
AfxBeginThread(ComputeThread,GetSafeHwnd(),
THREAD_PRIORITY_NORMAL);
}
}
//线程体:较array[2j]与array[2j+1]的大小,将大值置于array[j]中
UINT ComputeThread(LPVOID pParam)
{
if(array[2*j]>=array[2*j+1])
{
array[j]=array[2*j];
}
else
{
array[j]=array[2*j+1];
}
return 0;
}
}
//显示计算结果
void CDemoDlg::OnBtnShow()
{
// TODO: Add your control notification handler code here
int k;
CString str;
for(k=1;k<2*g_nCount;k++)
{
str.Format("Array[%d]= %d",k,array[k]);
m_strArray+="\r\n";
m_strArray+= str;
m_strArray+="\r\n";
}
UpdateData(false);
}
重置功能的实现代码,主要是将数组清空:
void CDemoDlg::OnBtnClear()
{
// TODO: Add your control notification handler code here
m_strArray.Empty ();
m_ctrlCount.SetFocus();
m_ctrlCount.Clear();
m_ctrlCount.SetSel(1);
UpdateData(false);
g_nCount=0;
j=0;
}