演算法歷年題

Ⅰ 高中數學演算法、程序的題

1. 說法1和3是正確的（2錯，演算法是不唯一的，故有好演算法與差演算法之分，在編程時應選擇最好的演算法，加快程序的運行速度）

2. 1錯了（賦值號=右端需為確定的值，而非變數；）

Ⅱ 面試會出哪些經典演算法題

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

(2)演算法歷年題擴展閱讀：

演算法的重要性：

1、演算法能力能夠准確辨別一個程序員的技術功底是否扎實；

2、演算法能力是發掘程序員的學習能力與成長潛力的關鍵手段；

3、演算法能力能夠協助判斷程序員在面對新問題時，分析並解決問題的能力；

4、演算法能力是設計一個高性能系統、性能優化的必備基礎。

Ⅲ 知名公司經典演算法筆試題和面試題答案

微軟

有一個整數數組，請求出兩兩之差絕對值最小的值，記住，只要得出最小值即可，不需要求出是哪兩個數。

寫一個函數，檢查字元是否是整數，如果是，返回其整數值。(或者：怎樣只用4行代碼編寫出一個從字元串到長整形的函數?)

給出一個函數來輸出一個字元串的所有排列。

請編寫實現malloc()內存分配函數功能一樣的代碼。給孫答出一個函數來復制兩個字元串A和B。字元串A的後幾個位元組和字元串B的前幾個位元組重疊。

怎樣編寫一個程序，把一個有序整數數組放到二叉樹中?

怎樣從頂部開始逐層列印二叉樹結點數據?請編程。

怎樣把一個鏈表掉個順序(也就是反序，注意鏈表的邊界條件並考慮空鏈表)?

請編寫能直接實現int atoi(const char * pstr)函數功能的代碼。

編程實現兩個正整數的除法，編程實現兩個正整數的除法，當然不能用除法操作符。

1

// return x/y.

2

int span(const int x, const int y)

3

{

4

....

5

}

在排序數組中，找出給定數字的出現次數，比如 [1, 2, 2, 2, 3] 中2的出現次數是3次。

平面上N個點，每兩個點都確定一條直線，求出斜率最大的那條直線所通過的兩個點(斜率不存在的情況不考慮)。時間效率越高越好。

一個整數數列，元素取值可能是0~65535中的任意一個數，相同數值不會重復出現。0是例外，可以反復出現。請設計一個演算法，當你從該數列中隨意選取5個數值，判斷這5個數值是否連續相鄰。注意：

5個數值允許是亂序的。比如：8 7 5 0 6

0可以通配任意數值。比如：8 7 5 0 6 中的0可以通配成9或者4

0可以多次出現。

復雜度如果是O(n2)則不得分。

設計一個演算法，找出二叉樹上任意兩個結點的最近共同父結點。復雜度如果是O(n2)則不得分。

一棵排序二叉樹，令 f=(最大值+最小值)/2，設計一個演算法，找出距離f值最近、大於f值的結點。復雜度如果是O(n2)則不得分。

一個整數數列，元素取值可能是1~N(N是一個較大的正整數)中的任意一個數，相同數值不會重復出現。設計一個演算法，找出數列中符合條件的數對的個數，滿足數對中兩數的和等於N+1。復雜度最好是O(n)，如果是O(n2)則不得分。

Google

正整數序列Q中的每個元素都至少能被正整數a和b中的一個整除，現給定a和b，需要計算出Q中的前幾項，例如，當a=3，b=5，N=6時，序列為3，5，6，9，10，12 (1)、設計一個函數void generate(int a,int b,int N ,int * Q)計算Q的前幾項(2)、設計測試數據來驗證函數程序在各種輸入下的正確性。

有一個由大小寫組成的字元串，現在需要對他進行修改，將其中的所有小寫字母排在答謝字母的前面(大寫或小寫字母之間不要求保持原來次序)，如有可能盡量選擇時間和空間效率高的演算法 c語言函數原型void proc(char *str) 也可以採用你自己熟悉的語言。

如何隨機選取1000個關鍵字，給定一個數據流，其純宴中包含無窮盡的搜索關鍵字(比如，人們在谷歌搜索時不斷輸入的關鍵字)。如何才能從這個無窮盡的流中隨機的選取1000個關鍵字?

判斷一個自然數是否是某個數的平方。說明：當然不能使用開方運算。

給定能隨機生成整數1到5的函數，寫出能隨機生成整數1到7的函數。

1024! 末尾有多少個0?

有5個海盜，按照等級從5到1排列，最大的海盜有權提議他們如何分享100枚金幣。但其他人要對此表決，如果多數反對，那他就會被殺死。他應該提出怎樣的方案，既讓自己拿到盡可能多的金幣又不會被殺死?(提示：有一個海盜能拿到98%的金幣)

23、Google2015華南地區筆試題。給定一個集合A=[0,1,3,8](該集合中的元素都是在0，9之間的數字，但未必全部包含)，指定任意一個正整數K，做凱銀請用A中的元素組成一個大於K的最小正整數。比如，A=[1,0] K=21 那麼輸出結構應該為100。

網路

用C語言實現一個revert函數，它的功能是將輸入的字元串在原串上倒序後返回。

用C語言實現函數void * memmove(void *dest, const void *src, size_t n)。memmove 函數的功能是拷貝src所指的內存內容前n個位元組到dest所指的地址上。分析：由於可以把任何類型的指針賦給void類型的指針，這個函數主要是實現各種數據類型的拷貝。

有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一隻螞蟻。木桿很細，不能同時通過一隻螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會後退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鍾可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。

騰訊

請定義一個宏，比較兩個數a、b的大小，不能使用大於、小於、if語句

兩個數相乘，小數點後位數沒有限制，請寫一個高精度演算法

有A、B、C、D四個人，要在夜裡過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鍾，只有一支手電筒，並且同時最多隻能兩個人一起過橋。請問，如何安排，能夠在17分鍾內這四個人都過橋?

有12個小球,外形相同,其中一個小球的質量與其他11個不同，給一個天平,問如何用3次把這個小球找出來，並且求出這個小球是比其他的輕還是重

在一個文件中有 10G 個整數，亂序排列，要求找出中位數。內存限制為 2G。只寫出思路即可。

一個文件中有40億個整數，每個整數為四個位元組，內存為1GB，寫出一個演算法：求出這個文件里的整數里不包含的一個整數。

騰訊伺服器每秒有2w個QQ號同時上線，找出5min內重新登入的qq號並列印出來。 1 2

Ⅳ 軟體設計師下午考試歷年c語言演算法有哪些 有代碼更好

07年下：
試題五（共15分）
閱讀以下說明和C代碼，將應填入 （n） 處的字句寫在答題紙的對應欄內。
【說明】
在差薯敏一個簡化的繪圖程序中，支持的圖形種類有點(point)和圓(circle)，在設計過程中採用面向對象思想，認為所有的點和圓都是一種圖形(shape)，並定義了類型shape_t、point_t和circle_t分別表示基本圖形、點和圓，並且點和圓具有基本圖形的所有特徵。
[C代碼]
typedef enum { point,circle } shape_type; /* 程序中的兩種圖形：點和圓 */
typedef struct { /* 基本的圖形類型 */
shape_type type; /* 圖形手鏈種類標識：點或者圓 */
void (*destroy)(); /* 銷毀圖形操作的函數指針 */
void (*draw)(); /* 繪制圖形操作的函數指針 */
} shape_t;
typedef struct { shape_t common; int x; int y; } point_t; /* 定義點類型，x、y為點坐標 */
void destroyPoint(point_t* this) { free(this); printf("Point destoryed!\n"); } /* 銷毀點對象 */
void drawPoint(point_t* this) { printf("P(%d,%d)", this->x, this->y); } /* 繪制點對象 */
shape_t* createPoint(va_list* ap) { /* 創建點對象，並設置其屬性 */
point_t* p_point;
if( (p_point = (point_t*)malloc(sizeof(point_t))) == NULL ) return NULL;
p_point->common.type = point; p_point->common.destroy = destroyPoint;
p_point->common.draw = drawPoint;
p_point->x = va_arg(*ap, int); /* 設置點的橫坐標 */
p_point->y = va_arg(*ap, int); /* 設置點的縱坐標 */
return (shape_t*)p_point; /* 返回點對象虛枝指針 */
}
typedef struct { /* 定義圓類型 */
shape_t common;
point_t *center; /* 圓心點 */
int radius; /* 圓半徑 */
} circle_t;
void destroyCircle(circle_t* this){
free( （1） ); free(this); printf("Circle destoryed!\n");
}
void drawCircle(circle_t* this) {
printf("C(");
（2） .draw( this->center ); /* 繪制圓心 */
printf(",%d)", this->radius);
}
shape_t* createCircle(va_list* ap) { /* 創建一個圓，並設置其屬性 */
circle_t* p_circle;
if( (p_circle = (circle_t*)malloc(sizeof(circle_t))) == NULL ) return NULL;
p_circle->common.type = circle; p_circle->common.destroy = destroyCircle;
p_circle->common.draw = drawCircle;
（3） = createPoint(ap); /* 設置圓心 */
p_circle->radius = va_arg(*ap, int); /* 設置圓半徑 */
return p_circle;
}
shape_t* createShape(shape_type st, ...) { /* 創建某一種具體的圖形 */
va_list ap; /* 可變參數列表 */
shape_t* p_shape = NULL;
（4） (ap, st);
if( st == point ) p_shape = createPoint( &ap); /* 創建點對象 */
if( st == circle ) p_shape = createCircle(&ap); /* 創建圓對象 */
va_end(ap);
return p_shape;
}
int main( ) {
int i; /* 循環控制變數，用於循環計數 */
shape_t* shapes[2]; /* 圖形指針數組，存儲圖形的地址 */
shapes[0] = createShape( point, 2, 3); /* 橫坐標為2，縱坐標為3 */
shapes[1] = createShape( circle, 20, 40, 10); /* 圓心坐標(20,40)，半徑為10 */
for(i=0; i<2; i++) { shapes[i]->draw(shapes[i]); printf("\n"); } /* 繪制數組中圖形 */
for( i = 1; i >= 0; i-- ) shapes[i]->destroy(shapes[i]); /* 銷毀數組中圖形 */
return 0;
}
[運行結果]
P(2,3)

08上：
試題四（10 分）
閱讀下列說明，回答問題 1 至問題 3，將解答填入答題紙的對應欄內。
[說明]
以下代碼由 C 語言書寫，在輸入三個整數後，能夠輸出最大數和最小數。
int main( void )
{
int a, b, c, max, min;
printf( "input three numbers: " );
scanf( "%d%d%d", &a, &b, &c );
if( a > b ) /*判斷 1*/
{
max = a;
min = b;
}
else
{
max = b;
min = a;
}
if( max < c ) /*判斷 2*/
max = c;
else if( min > c ) /*判斷 3*/
min = c;
printf( "max=%d\nmin=%d", max, min );
return 0;
}
08下
【問題 3】（2 分） 【問題 1】中偽代碼的時間復雜度為 （6） （用 Ο 符號表示）。
試題五（共 15 分）
閱讀下列說明和 C 函數，將應填入 （n） 處的字句寫在答題紙的對應欄內。
【說明】
已知集合 A 和 B 的元素分別用不含頭結點的單鏈表存儲，函數 Difference()用於求解集合 A 與 B 的差集，並將結果保存在集合 A 的單鏈表中。例如，若集合 A={5，10，20，15，25，30}，集合 B={5，15，35，25}，如圖 5-1(a)所示，運算完成後的結果如圖 5-1(b)所示。

圖 5-1 集合 A、B 運算前後示意圖
鏈表結點的結構類型定義如下：
typedef struct Node{
ElemType elem;
struct Node *next;
}NodeType;

【C 函數】
void Difference(NodeType **LA, NodeType *LB)
{
NodeType *pa, *pb, *pre, *q;
pre = NULL;
(1) ;
while (pa) {
pb = LB;
while ( （2） )
pb = pb->next;
if ( （3） ) {
if (!pre)
*LA = （4） ;
else
（5） = pa->next;
q = pa;
pa = pa->next;
free(q);
}
else {
（6） ;
pa = pa->next;
}
}
}

09年
試題五（共 15 分）
閱讀下列說明和 C 函數代碼，將應填入 （n） 處的字句寫在答題紙的對應欄內。
【說明】
對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結點，且每個結點僅訪問一次的過程。函數 InOrder()藉助棧實現二叉樹的非遞歸中序遍歷運算。
設二叉樹採用二叉鏈表存儲，結點類型定義如下：
typedef struct BtNode{
ElemType data; /*結點的數據域，ElemType 的具體定義省略*/
struct BtNode *lchild,*rchild; /*結點的左、右孩子指針域*/
}BtNode, *BTree;
在函數 InOrder()中，用棧暫存二叉樹中各個結點的指針，並將棧表示為不含頭結點的單向鏈表（簡稱鏈棧），其結點類型定義如下：
typedef struct StNode{
BTree elem; /*鏈棧的結點類型*/
struct StNode *link; /*棧中的元素是指向二叉鏈表結點的指針*/
}StNode;
假設從棧頂到棧底的元素為 en、en-1、…、e1，則不含頭結點的鏈棧示意圖如圖 5-1所示。

圖 5-1 鏈棧示意圖
【C 函數】
int InOrder(BTree root) /* 實現二叉樹的非遞歸中序遍歷 */
{
BTree ptr; /* ptr 用於指向二叉樹中的結點 */
StNode *q; /* q 暫存鏈棧中新創建或待刪除的結點指針*/
StNode *stacktop = NULL; /* 初始化空棧的棧頂指針 stacktop */
ptr = root; /* ptr 指向二叉樹的根結點 */
while ( （1） || stacktop != NULL) {
while (ptr != NULL) {
q = (StNode *)malloc(sizeof(StNode));
if (q == NULL)
return -1;
q->elem = ptr;
(2) ;
stacktop = q; /*stacktop 指向新的棧頂*/
ptr = （3） ; /*進入左子樹*/
}
q = stacktop;
（4） ; /*棧頂元素出棧*/
visit(q); /*visit 是訪問結點的函數，其具體定義省略*/
ptr = （5） ; /*進入右子樹*/
free(q); /*釋放原棧頂元素的結點空間*/
}
return 0;
}/*InOrder*/

09年下：
試題七（共 15 分）
閱讀以下說明和C程序，將應填入 （n） 處的字句寫在答題紙的對應欄內。
【說明】
現有 n（n < 1000）節火車車廂，順序編號為 1,2,3,...,n，按編號連續依次從 A 方向的 鐵軌駛入，從 B 方向鐵軌駛出，一旦車廂進入車站（Station）就不能再回到 A 方向的鐵軌 上；一旦車廂駛入 B 方向鐵軌就不能再回到車站，如圖 7-1 所示，其中 Station 為棧結構， 初始為空且最多能停放 1000 節車廂。

圖 7-1 車站示意圖
下面的 C 程序判斷能否從 B 方向駛出預先指定的車廂序列，程序中使用了棧類型STACK,關於棧基本操作的函數原型說明如下：
void InitStack(STACK *s)：初始化棧。
void Push(STACK *s,int e): 將一個整數壓棧，棧中元素數目增 1。
void Pop(STACK *s)：棧頂元素出棧，棧中元素數目減 1。
int Top(STACK s)：返回非空棧的棧頂元素值，棧中元素數目不變。
int IsEmpty(STACK s)：若是空棧則返回 1，否則返回 0。
【C程序】
#include<stdio.h>
/*此處為棧類型及其基本操作的定義，省略*/
int main( ){
STACK station;
int state[1000];
int n; /*車廂數*/
int begin, i, j, maxNo; /*maxNo 為 A 端正待入棧的車廂編號*/
printf("請輸入車廂數： ");
scanf("%d",&n);
printf("請輸入需要判斷的車廂編號序列（以空格分隔）： ");
if (n < 1) return -1;
for (i = 0; i<n; i++) /* 讀入需要駛出的車廂編號序列,存入數組 state[] */
scanf("%d",&state[i]);
（1） ; /*初始化棧*/
maxNo = 1;
for(i = 0; i < n; ){/*檢查輸出序列中的每個車廂號 state[i]是否能從棧中獲取*/
if ( （2） ){/*當棧不為空時*/
if (state[i] == Top(station)){ /*棧頂車廂號等於被檢查車廂號*/
printf("%d ",Top(station)); Pop(&station); i++;
}
else
if
( （3） ){ printf("error\n"); return 1;
}
else{
begin (4) ;
for(j = begin+1; j<=state[i]; j++)
{ Push(&station, j);
}
}
}
else { /*當棧為空時*/
begin = maxNo;
for(j = begin; j<=state[i]; j++){ Push(&station, j);
}
maxNo = （5） ;
}
}
printf("OK");
return 0;
}

Ⅳ 幾個演算法分析方面的題目

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

Ⅵ 邏輯演算法題(不斷更新)

問：有1000瓶葯劑和10隻老鼠，葯劑中有1瓶毒葯，喝了一周內死亡（有的題目改成了五分鍾，五分鍾真虧他能喂完），如何在仿早一周內找到這瓶毒葯。
答：將這1000瓶葯劑編號0~999，並轉換為二進制 就是0000000001~1111101000，從右向左開始，讓第一隻老鼠喝所有右起第一位編號為1的葯劑，第二隻老鼠喝所有右起第二位編號為1的葯劑，依次類推，10隻老鼠喝完10位的葯劑，一周後，如果第一隻老鼠死亡，那麼毒葯的從右起第一位為1，未死亡的話就為0，所以根據死亡狀態就可以知道該瓶毒葯的二進制。
例如狀態是：死亡，存活，死亡，存活，存活，存活，死亡，存活，死亡，存活 = 010111010=186
從上面例銀瞎子就可以知道第二種和第三種問題的解法了吧

測試時間提升為兩周就說明第一周測試不死的老鼠可以拿來繼續第二周的測試 ，所以老鼠的狀態就變成了三種：存活（未實驗），死亡，實驗後存活。
將全部葯劑編號後轉為三進制數，老鼠右起依次喝0編號的葯劑，如果死亡，那麼該位編號為0，鋒大空如果未死亡，那麼可能為1和2，第二周把存活的老鼠繼續喝該位1編號的葯劑，如果死亡就為1，存活就為2，這樣就找到了毒葯的三進制編號，然後轉換成下標即可。

總結:有 n 只小白鼠 m周的時間可以從 (m+1)^n 個瓶子中檢驗出毒葯來。

Ⅶ 演算法問題

#include <stdio.h>
#include <stdlib.h>
#include <string.h>物飢

int money_count(int money) //第一題判螞搏
{
int SortedMonType[7] = {100,50,20,10,5,2,1};
int Money_left = money;
int Money_count = 0;
int CurMoney_index = 0;
int i;

for(i=0;i<7;i++)
{
int Tempcount = (int)(Money_left/掘祥SortedMonType[i]);
Money_count += Tempcount;
Money_left = Money_left - Tempcount*SortedMonType[i];
if(Money_left==0) break;
}

return Money_count;

}

float equal(float *arr, int size) //第二題
{
if(size == 1)
return arr[0]/size;

return (arr[0] + equal(arr+1, size-1) * (size-1))/size;
}

void main()
{
float arr[8] = {11,22,33,44,55,66,77,88};

printf("equal = %f \n",equal(arr, 8));

printf("%d\n", money_count(381));
}

Ⅷ 演算法題目

C C B A
給點分吧，嘿嘿

Ⅸ 演算法分析與設計題目

第一題用貪心思想 找出用時最短的m個作業交給機器同時開始加工 然後再依次將剩下的作業中最短完成作業取出放入已完成的機器加工 當最後一台機器完工時間就是所用最短時間 思路是這樣子 具體演算法實現的話。。由於我也是學生=、=寫代碼還不是很熟練。。可能等我寫好了你考試來不及。。。你還是自己來吧

第二題
1.背包問題是什麼=、=我們教材不一樣 不了解具體問題。。
2.4皇後
#include<iostream.h>
const int n = 4 ;
const int n_sub = n - 1 ;
int queen[n] ;
bool row[n] ;
bool passive[2*n-1];
bool negative[2*n-1];
int main()
{
int cur = 0 ;
bool flag = false ;
queen[0] = -1 ;
int count = 0 ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag)
{
queen[cur]++ ;
if(queen[cur] >= n)
{
queen[cur] = -1 ;
cur-- ;
if(cur>=0)
{
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
false ;
}
else
{
if(row[queen[cur]] == false)
{
flag = true ;
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
}
else
flag = true ;
if(flag) {
if(cur == n-1)
{
count++ ;
}
row[queen[cur]] = true ;
passive[queen[cur] + cur] = true ;
negative[n_sub + cur - queen[cur]] = true ;
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
flag = false ;
}
}
}
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
這個是代碼。。。狀態空間樹這里畫不出來。。。

第三題
你網路下基本都有的=、=。。。我網路出來不好意思貼了你自己去看下吧
比如1.的答案：
最壞情況給出了演算法執行時間的上界，我們可以確信，無論給什麼輸入，演算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。

Ⅹ 演算法與數據結構試題 急用！！！

這是我寫的順序查找和二分查找代碼
#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;
}