c语言背包问题_背包问题贪心算法_背包问题 贪心算法(12)

五、算法题

1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。

写出二分搜索的算法，并分析其时间复杂度。

1. template<class Type>

int BinarySearch(Type a[], const Type& x, int n)

{//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1

Int left=0; intright=n-1;

While (left<=right){

intmiddle=(left+right)/2;

if (x==a[middle])return middle;

if (x>a[middle])left=middle+1;

else right=middle-1;

}

Return -1;

}

时间复杂性为O(logn)

2. 利用分治算法写出合并排序的算法，并分析其时间复杂度

1. void MergeSort(Type a[], int left, int right)

{

if (left<right) {//至少有2个元素

inti=(left+right)/2; //取中点

mergeSort(a, left, i);

mergeSort(a, i+1,right);

merge(a, b, left, i,right); //合并到数组b

copy(a, b, left,right); //复制回数组a

}

}

算法在最坏情况下的时间复杂度为O(nlogn)。

3.N皇后回溯法

bool Queen::Place(int k)

{ //检查x[k]位置是否合法

for (int j=1;j<k;j++)

if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;

return true;

}

void Queen::Backtrack(intt)

{

if (t>n) sum++;

elsefor (int i=1;i<=n;i++) {

x[t]=i;

if (约束函数 )Backtrack(t+1);

}

}

4.最大团问题

void Clique::Backtrack(inti) // 计算最大团

{ if (i > n) { // 到达叶结点

for (int j = 1; j <= n; j++) bestx[j]= x[j];

bestn = cn; return;}

// 检查顶点 i 与当前团的连接

int OK = 1;

for (int j = 1; j < i; j++)

if (x[j] && a[i][j] == 0) { // i与j不相连

OK = 0; break;}

if (OK ) { // 进入左子树

x[i] = 1;cn++;

Backtrack(i+1);

x[i] = 0; cn--; }

if (cn + n - i > bestn ) { //进入右子树

x[i] = 0;

Backtrack(i+1); }

}

5.最长公共子序列问题

6．哈弗曼编码算法

算法设计与分析试题

一、概念题

1．队列 2．完全二叉树 3．堆 4．P类问题 5.NP问题

二、程序填空题

1．宽度优先图周游算法

procedure bft(g，n)

／／g的宽度优先周游／／

declare visited(n)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-12.html