1. 编程实现堆排序
#include
usingnamespace std;
void SwapValue(int &m, int &n)
{
int temp = m;
m = n;
n = temp;
}
void max_heap(vector
{
int l = 2*i;
int r = 2*i+1;
int largest = i;
if(l<=heap_size && vec[l-1]>vec[largest-1])
largest = l;
if(r<=heap_size && vec[r-1]>vec[largest-1])
largest = r;
if(largest!=i)
{
SwapValue(vec[largest-1],vec[i-1]);
max_heap(vec, largest, heap_size);
}
}
void heapSort(vector
{
int heap_size = ();
for(int i=heap_size/2; i>=1; i–)
max_heap(vec, i, heap_size);
for(int i=heap_size; i>=1; i–)
{
SwapValue(vec[0],vec[i-1]);
max_heap(vec, 1, i);
}
}
void print(vector
{
for(int i=0; i
cout<
cout<
}
int main()
{
vector
_back(23);
_back(5);
_back(1);
_back(10);
_back(13);
_back(32);
_back(21);
_back(14);
_back(19);
_back(20);
cout<<“排序前: “<
print(vec);
heapSort(vec);
cout<<“排序后: “<
print(vec);
return 0;
}
2.求一个正整数N的开方,要求不能用库函数sqrt(),结果的`精度在0.001
解析:牛顿迭代
#include
using namespace std;
int main()
{
int N;
cout<<“输入N的值:“;
cin>>N
double x1 = 1;//初值
double x2 = x1/2.0+N/2.0/x1;
while( fabs(x2-x1)>0.001)
{
x1 = x2;
x2 = x1/2.0+N/2.0/x1;
}
cout<
return 0;
}
3.给定一个矩阵intmaxtrixA[m][n],每行和每列都是增序的,实现一个算法去找矩阵中的某个元素element.
解法一:
#include
using namespace std;
const int M = 4;
const int N = 4;
int main
{
int matrix[M][N] = {};
double element;
int flag = 1;
for(int j=0; j
{
if(matrix[i][j] == element)
cout<<“位置“<
while( flag
–flag;
while( flag
++flag;
}
}
解法二:
bool Find(int *matrixA, int m, int n, int element)
{
bool found = false;
if(matrixA != NULL & m & n)
{
int i,j;
i=0;j=n-1;
while(i
{
if(maxtrixA[i*n+j] == element)
{
found = true;
break;
}
else if(matrix[i*n+j]>element
–j;
else
++i
}
}
}