題目是：再次考慮線性查找問題（參見聯(lián)系2.1-3）嫉戚。假定要查找的元素等可能地為數(shù)組中地任意元素，平均需要檢查輸入序列地多少元素澈圈？最壞情況又如何呢彬檀？用θ記號給出線性朝朝地平均情況和最壞情況地運(yùn)行時間。證明你的答案极舔。
以下是證明過程與C語言程序驗證：
過程中的難點就是等差等比數(shù)列的求和凤覆，網(wǎng)上搜下公式應(yīng)該不難。
以下是C語言代碼的驗證：
````
#include
#include
#include
int main()
{
? ? int v = 23;? ? ? ? //v為某個值
? ? int count = 50000; //樣本測試的次數(shù)
? ? int size = 10;? ? //數(shù)組的大小
? ? double p = 0.2;? ? //是v的概率
? ? int h;
? ? double sumIndex = 0;
? ? int arr[size]; //定義數(shù)組
? ? srand((unsigned)time(NULL));
? ? for (int k = 0; k < count; k++)
? ? {
? ? ? ? for (int i = 0; i < size; i++)
? ? ? ? {
? ? ? ? ? ? if ((double)rand() / RAND_MAX <= p)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? arr[i] = v;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? arr[i] = 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for (int j = 0; j < size; j++)
? ? ? ? {
? ? ? ? ? ? if (arr[j] == v || (j == (size - 1) && arr[j] != v))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? v = 0;
? ? ? ? ? ? ? ? sumIndex += (j + 1);
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? v = 23;
? ? }
? ? printf("%f", (double)(sumIndex / count));
? ? return 0;
}
````
4.459680是大小為10的數(shù)組在5w次下的試驗平均結(jié)果拆魏。代入數(shù)字盯桦，與公式的答案相符。證明完畢渤刃。
