算法设计与分析习题答?-6?- 百度文库 ر

CFDHȻٻO(n2)ʱɼӷ㼴ɡƷ㷨ʵ־˷ʱܡܷٸĽ㷨

ϰ5

1. ۰㷨ȷȷ㷨ȷ֤ȷ

˵ԭ

int BinSearch(int r[ ], int n, int k) {

int low = 0, high = n - 1; int mid;

while (low <= high) {

mid = (low + high) / 2; if (k < r[mid]) high = mid;

else if (k > r[mid]) low = mid;

else return mid; }

return 0; }

ȷ㷨

int BinSearch1(int r[ ], int n, int k) {

int low = 0, high = n - 1; int mid;

while (low <= high) {

mid = (low + high) / 2; if (k < r[mid]) high = mid - 1;

else if (k > r[mid]) low = mid + 1;

else return mid; }

return 0; }

2. д۰ҵĵݹ㷨ʱܡ

//۰ҵĵݹʵ

#include using namespace std;

int digui_search(int a[],int low,int high,int x) {

if (low > high) return 0;

int mid = (low+high)/2; if (a[mid] == x) return mid;

else if (a[mid] < x)

digui_search(a,low,mid-1,x); else

digui_search(a,mid+1,high,x); }

int main() { int a[6]={0,1,2,9,5,3}; int result=digui_search(a,0,5,5);

cout<

3. ޸۰㷨ʹܹ֮зΧҡνΧҪҳڸֵab֮

Ԫأab

޸ĵڶ㷨ʵ֣

//۰㷨ʹܹ֮зΧ

#include using namespace std;

//۰зΧҺ

void digui_search(int min, int max, int a[], int low, int high) {

int mid;

mid=(low+high)/2; if(a[mid]

digui_search(min, max, a, mid, high);

else if(a[mid]>max)

digui_search(min, max, a, low, mid); else {

for(int i=mid; a[i]>=min && i>=low; i--) cout<

for(int j=mid+1; a[j]<=max && j<=high; j++) cout<

void main() {

int r[6], min, max;

cout<<\Ԫأ\ for(int i=0; i<6; i++) cin>>r[i];

cout<<\ҷΧСֵminֵmax\

cin>>min>>max;

digui_search(min, max, r, 0, 5); cout<

4. mnСʾmnСlcm(m, n)mnԼgcd(m, n)֮¹ϵlcm(m, n)=mn/gcd(m, n)

//С

#include using namespace std;

int main (void) {

int a,b; int i=1;

cin>>a>>b;

while((i%a!=0)||(i%b!=0)) ++i;

cout<<\СΪ\

return 0; }

(㷨ȽֱӣҪʹĽŷ㷨ԼȻĹʽС)

5. 뷨ѡ֪k1, k2, ?, knǶѣ㷨k1, k2, ?, kn, kn+1ΪѣΪѣ

գ

void SiftHeap(int r[ ], int k, int n) {

int i, j, temp;

i = k; j = 2 * i + 1; //iΪҪɸĽ㣬jΪi while (j < n) //ɸѡûнеҶ {

if (j < n-1 && r[j] < r[j+1]) j++; //ȽiҺӣjΪϴ if (r[i] > r[j]) //ѾҺеĽϴ break; else { temp = r[i]; r[i] = r[j]; r[j] = temp; //ɸj i = j; j = 2 * i + 1; //ɸλԭjλ } } }

еѣ

6. 㷨ʵڴɾһԪأҪ㷨ʱ临ΪO(log2n)

//Ҫɾa[k]һԪa[n-1] //Ȼе

void de_SiftHeap(int r[ ], int k, int n) {

int i, j, temp,temp1; i = k; j = 2 * i + 1; if(i<0||i>n-1) return error; else if(i==n-1) free(a[i]);

else //iΪҪɸĽ㣬jΪi

while (j < n) //ɸѡûнеҶ {

temp1=a[i]; //a[n-1]a[k]