我是 C 的初學者，我需要幫助。我想做的是在（1-100）之間創建一個陣列。陣列中的一個數字將消失，它會呼叫丟失的數字。輸出將是陣列中的“缺失數字”。我需要演示線性搜索、插值搜索和二分搜索的實作來解決這個問題。
問題是輸出總是與已宣告的陣列相同。玩編碼很有趣，但我真的需要幫助來解決這個任務。
#include <stdio.h>
#include <time.h>
int MissingNum(int a[], int n)
{
int i, total;
total = (n 1) * (n 2) / 2;
for (i = 0; i < n; i )
total -= a[i];
return total;
}
int LS(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i )
if (arr[i] == x)
return i;
return -1;
}
int BS(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return BS(arr, l, mid - 1, x);
return BS(arr, mid 1, r, x);
}
return -1;
}
int IS(int arr[], int lo, int hi, int x)
{
int pos;
if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
pos = lo (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
return IS(arr, pos 1, hi, x);
if (arr[pos] > x)
return IS(arr, lo, pos - 1, x);
}
return -1;
}
int main(void)
{
int choice;
int arr[] = {86, 56, 95, 59, 18, 91, 73, 80, 31, 87, 84, 51, 16, 27, 40, 60, 26, 20, 6, 92, 25,100,
48, 90, 15, 96, 69, 71, 76, 47, 74, 49, 63, 38, 33, 3, 55, 14, 45, 46, 30, 35, 53, 50,
62, 39, 42, 10, 88, 17, 77, 9, 72, 81, 37, 82, 21, 61, 43, 78, 23, 58, 83, 12, 54, 13,
89, 1, 24, 7, 99, 64, 93, 5, 57, 29, 41, 94, 34, 44, 36, 85, 4, 68, 22, 28, 75, 66, 65,
11, 19, 97, 70, 79, 8, 52, 32, 9, 8, 2, 67};
int x = MissingNum(arr,99);
int n = sizeof(arr) / sizeof(arr[0]);
int process;
do
{
printf("\t\tMissing integer is %d\n\n", x);
printf("Choose your type of search\n");
printf("1. Linear search\n");
printf("2. Binary search\n");
printf("3. Interpolation search\n\n");
printf("Insert input: ");
scanf("%d",&process);
switch (process) {
case 1 : {
clock_t countstart = clock();
int result = LS(arr, n, x);
int length = sizeof(arr)/sizeof(arr[0]);
printf("List of Integers : \n");
for (int i = 0; i < length; i ) {
printf("%d ", arr[i]);
}
if (result == -1)
{
printf(" \n\nMissing Integer : %d \n", x);
}
clock_t countstop = clock();
printf("\n\nExecution for Linear Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);
}
break;
case 2 : {
clock_t countstart = clock();
int output = BS(arr, 0, n - 1, x);
int length = sizeof(arr)/sizeof(arr[0]);
printf("List of Integers : \n");
for (int i = 0; i < length; i )
{
printf("%d ", arr[i]);
}
if (output == -1)
{
printf(" \n\nBinary Search Integer : %d \n",x);
}
clock_t countstop = clock();
printf("\n\nExecution time for Binary Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);
}
break;
case 3 :{
clock_t countstart = clock();
int index = IS(arr, 0, n - 1, x);
int length = sizeof(arr)/sizeof(arr[0]);
printf("List of Integers : \n");
for (int i = 0; i < length; i )
{
printf("%d ", arr[i]);
}
if (index == -1)
{
printf(" \n\nInterpolation Search Integer : %d \n",x);
}
clock_t countstop = clock();
printf("\n\nExecution time for Interpolation Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);
}
break;
default : printf("Invalid code please try again");
break;
}
printf("\n\nDo you want to continue? Enter '1' if YES and '2' if NO : ");
scanf(" %d" ,&choice);
}while(choice==1);
getchar();
return 0;
}
uj5u.com熱心網友回復：
請仔細檢查是否, 9, 8,有錯別字。我懷疑你想要, 那里。, 98,你會有一個干凈初始化的 100 條目陣列，沒有丟失的數字。你會有一個 99 個條目的陣列，缺少 98 個
。,
我嘗試使用該錯字修復所有三個演算法，結果找到了 98 個。
用 98 替換不同的初始數字會導致所有三個演算法都找到該數字。
你的實作對我來說似乎有問題。
LS 通過陣列查看外部提供的數字是否丟失，并確認是否丟失。那實際上并沒有找到丟失的號碼。對于 IS 和 BS 幾乎相同。
無論數字MissingNum()猜測（并且猜測不正確），只要它不在陣列中（對于超過 100 的任何數字都是如此），所有三個演算法都會確認。MissingNum()猜測不正確，因為它對陣列 init 做出假設（一個缺失，所有其他一次），顯示的陣列 init 不匹配。當我嘗試猜測時，猜測是 150，對你來說可能是一樣的。顯然錯了。所有演算法都證實了這一猜測的事實應該讓你懷疑。修正我提出的錯字修正了MissingNum()假設。它猜對了（98）并且所有三個演算法都熱情地同意——它們應該被涂上焦油和羽毛。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/430166.html
下一篇：通過平方求冪的時間復雜度是多少？