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,並輸出索引號
}