mid算法题

㈠ 求解一道算法设计题

void invert(sequenlist *p)
{
char mid;
int i,j;
i=0;
j=p->last-1;
while(i<j)
{
mid=p->data[i];
p->data[i]=p->data[j];
p->data[j]=mid;
i++;j--;
}
}

㈡ 几个算法分析方面的题目

1. 局部最优能达到全局最优。
2. 一个问题能被分解成子问题，这个问题的解最优当且仅当所有子问题的解最优。
3. 解空间指所有的可行解组成的集合。

2. 贪心算法可用来解这个问题，按顺序将物品按重量递增顺序加入背包，直到不能加入，正确性显然，每个物品只被考虑一次，时间复杂度O( n )，可以认为是Theta( k ),其中k为最优解加入的物品数。
3. 对于每个区间[ a , b ] ， 另mid = ( a + b ) / 2 ，cnt[ a , b ] = cnt[ a , mid ] + cnt( mid , b ] , 其中cnt[ a , a ] = 1 ， 当 num[ a ] = x , 否则 cnt[ a , a ] = 0 ;时间复杂度是O( n )的，考虑满二叉树的性质，得证。（ 硬搞出来的分治算法... ）
4. 题目不完整。
5. 自己画吧...这里不好贴图，然后前序厉遍一下，写出来，伪代码也自己写吧。

时间不多，只能这么简略地写一下，希望能帮到你。

BillWSY

㈢ 算法与数据结构试题 急用！！！

这是我写的顺序查找和二分查找代码
#include<iostream.h>
#define elemtype int

int sqsearch(elemtype a[],int n,elemtype x); //顺序查找
int sqsearch2(elemtype a[],int n,elemtype x); //顺序查找，打印查找过程
int binsearch(elemtype a[],int n,elemtype x); //折半查找
int binsearch2(elemtype a[],int n,elemtype x); //折半查找，打印查找过程

void printarray(elemtype a[],int n); //打印数组数据

int main()
{
int i,x;
const int n=9;
elemtype a1[10]={0,34,23,12,56,90,78,89,45,67};
elemtype a2[10]={0,12,23,34,45,56,67,78,89,90};

//顺序查找
cout<<"顺序查找："<<endl;
cout<<"a1[]=";
printarray(a1,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=sqsearch(a1,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
sqsearch2(a1,n,x); //查找过程
cout<<"完成顺序查找！"<<endl;
//二分法查找
cout<<"二分法查找："<<endl;
cout<<"a2[]=";
printarray(a2,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=binsearch(a2,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
binsearch2(a2,n,x);
cout<<"完成顺序查找！"<<endl;
return 0;
}

//在数组a[1.2...n]中顺序查找x
//找到时返回元素下标，否则返回0
int sqsearch(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
if(a[0]==x)
return 1;
else
{
a[0]=x;
for(i=n;!(a[i]==x);--i); //若找到则i大于0
return i;
}
}

//在数组a[1.2...n]中顺序查找x,打印每次比较结果
//找到时返回元素下标，否则返回0
int sqsearch2(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
a[0]=x;
for(i=n;!(a[i]==x);--i)
if(a[i]>x)
cout<<a[i]<<">"<<x<<endl;
else
cout<<a[i]<<"<"<<x<<endl;
return i;
}

//在数组a[1.2...n]中二分法查找x
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch(elemtype a[],int n,elemtype x) //二分查找
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
return mid;
else if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}

//在数组a[1.2...n]中二分法查找x，每次打印比较结果
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch2(elemtype a[],int n,elemtype x) //查找过程
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
{
cout<<a[mid]<<"="<<x<<endl;
return mid;
}
else if(x<a[mid])
{
cout<<a[mid]<<">"<<x<<endl;
high=mid-1;
}
else
{
cout<<a[mid]<<"<"<<x<<endl;
low=mid+1;
}
}
return 0;
}

//打印顺组数据a[1....n]
void printarray(int a[],int n)
{
int i;
cout<<"{";
for(i=0;i<=n;i++)
{
cout<<a[i];
while(i<n)
{
cout<<",";
break;
}
}
cout<<"}"<<endl;
}

㈣ 王道数据结构里面的一道题，逆置算法，划圈的那点mid–left不是很懂，为什么要减去left觉得直

因为你的这个程序是递归的，会分为两边。

如果在最左边。那么left是0没有问题，

但是在右边，实际上你的个数只有mid-left。而不是mid个。

那么程序必然要写成

i<=mid-left
//因为mid指的是某个区间的中间那个数，但是这个区间实际的元素个数应该为
//(mid-left)*2
//而根据算法能够明白我们需要处理的是当前区间的前半段
//那么自然是从i=0-->i<=mid-left

你仔细想想，看看能不能明白。

我随便画了个草图。

㈤ 有15个数存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值

#include <stdio.h>
#include <stdlib.h>

int main(void) {
int ary[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int num = 16;
int pos;
int low;
int high;
int mid;
low = 1;
high = 15;
pos = 0;
while(high>=low){
mid = (low + high)/2;
if(ary[mid-1]>num){
high = mid-1;
}else if(ary[mid-1]<num){
low = mid + 1;
}else{
pos = mid;
break;
}
}
if(pos == 0){
printf("the data is not found\n");
}else{
printf("the data pos is :%d\n",pos);
}

return 0;
}

㈥ 急求完善两道简单的算法分析题

第一题的题目有误吧
返回小于x的最大元素的位置I和大于x的最大元素位置j
应该是
返回小于x的最大元素的位置I和大于x的最小元素位置j

算法有点问题

第二题的算法不对

两道题目都是要假设 a[0:n-1]是一个已排好序的数组 并且是严格单调递增的。

// 二分查找.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>

#define N 10

bool BinarySearch(int a[],int n,int x,int& i,int& j)
{
int left=0;
int right=n-1;
while(left<right-1)
{
int mid=(left+right)/2;
if(x==a[mid])
{
i=j=mid;
return true;
}
if(x>a[mid])
left=mid;
else
right=mid;
}
i=right;
j=left;
return false;
}

int SearchTag(int a[],int n)
{
int left=0;
int right=n-1;
while(left<right-1)
{
int mid=(left+right)/2;
if(mid==a[mid]) return mid;
if(mid<a[mid])
right=mid;
else
left=mid;
}
return -1;
}

int _tmain(int argc, _TCHAR* argv[])
{
int a[N];
printf("请输入%d个由小到大排列的整数\n以空格隔开，以回车结束\n",N);

int k;
for(k=0;k<N;k++)
scanf("%d",a+k);
printf("你的输入如下：\n");
for(k=0;k<N;k++)
printf("%d\t",k);
//printf("\n");
for(k=0;k<N;k++)
printf("%d\t",a[k]);
printf("\n");

if((k=SearchTag(a,N))!=-1)
printf("第%d个数字满足a[%d]=%d\n",k,k,k);
else
printf("没有找到任何一个数字满足a[i]=i\n");

int i,j;
int x;
printf("请输入你想要查找的数字\n");
scanf("%d",&x);
if(BinarySearch(a,N,x,i,j))
printf("找到了：i和j均在%d\n",j);
else
printf("没找到：j=%d\ti=%d\n",j,i);

getchar();
getchar();
return 0;
}

㈦ 二分法的算法步骤是什么

在有序的有N个元素的数组中查找用户输进去的数据x。

算法如下：

1、确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。

2、若a[mid]=x或front>=end，则结束查找；否则，向下继续。

3.、若a[mid]<x，说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

(7)mid算法题扩展阅读

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找，arr[low，mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1，high]，

直到找到为止，时间复杂度:O(log(n))。

㈧ 谢谢大神

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class arrlist
{

public:
arrlist()
{
shuzu.push_back(0xdeadbeef);
}
//O(lgN)
int listsearch(int x)
{
//二分查找
int s = 1;
int e = shuzu.size();
while(s!=e)
{
int mid = s+(e-s)/2;
if(shuzu[mid]==x)
return mid;
else if(shuzu[mid]>x)
e = mid -1;
else
s = mid+1;
}
return 0;
}
//O(lgN)
int listdelete(int x)
{
int s = 1;
int e = shuzu.size();
while(s!=e)
{
int mid = s+(e-s)/2;
if(shuzu[mid]==x)
{
int i= mid;
int j= mid;
while(i>=1 && shuzu[i]==x)
i--;
i++;
while(j<shuzu.size() && shuzu[j]==x)
j++;

shuzu.erase(i+shuzu.begin(),j+shuzu.begin());
break;
}
else if(shuzu[mid]>x)
e = mid -1;
else
s = mid+1;
}
return 0;
}
//追问才行

㈨ MID算法什么意思

MID(A1,2,3)表示A1字符串的从第二个字符开始往后的三个字符

若A1=ABCDE MID(A1,2,3)为BCD

㈩ 二分查找

#include <stdio.h>

int BinarySearch(int * R,int n,int key) // 在长度为n的数组R中查找关键字key
{
int low=0,high=n-1,mid;
while(low<=high)
{
mid=(low+high)/2;
if(key<R[mid])
{
printf("R[mid]=%d <\n",R[mid]);
high=mid-1;
}
else if(key>R[mid])
{
printf("R[mid]=%d >\n",R[mid]);
low=mid+1;
}
else
{
printf("R[mid]=%d =\n",R[mid]);
return mid; // 返回查找到的索引值
}
}
return -1;
}

void main()
{
int R[]={1,2,3,5,7,8,10,15,16,17,19,20};
printf("%d\n",BinarySearch(R,12,17)); // 测试在数组R中查找17,并输出索引号
}