在不改变代码的情况下进行填空查找n在数组a中最后一次出现的位置(数组首元素的位置为零)。 输入5个整数，将它们存入数组a中，再输入1个数n，然后在数组中查找n， 如果找到，输出n最后一次出现的相应下标，否则，输出“Not Found”。#include <stdio.h> int main(void) { int a[5]; int i,k,n,f=0; for(i=0;i<=4;i++) scanf("%d",&a[i]); scanf("%d",&n); for(i=0;i<10;i++) /************found************/ if(___(1)___) { f=1; /************found************/ ___(2)___; } if(f) printf("%d is No. %d\n", n,k); else printf(" %d not found !\n",n); return 0; }

在不改变代码的情况下进行填空，完整代码如下：

#include <stdio.h> 

int main(void) {     
    int a[5];    
    int i, k = -1, n, f = 0; // 初始化k为-1，表示未找到
    for(i = 0; i <= 4; i++) 
        scanf("%d", &a[i]); 
    scanf("%d", &n); 

    for(i = 0; i < 5; i++) { // 这里应该循环5次，而不是10次
        if(a[i] == n) { 
            f = 1; 
            k = i; // 记录最后一次出现的下标
        } 
    } 

    if(f) 
        printf("%d is No. %d\n", n, k); 
    else 
        printf("%d not found!\n", n); 

    return 0; 
}

相关问题

程序用“快速顺序查找法”查找数组a中是否存在某一关键字。请填空。

"快速顺序查找法"（也称为快速排序算法的一部分）是一种线性搜索策略，用于在有序数组中查找特定的关键字。以下是基本步骤：

1. **选择基准元素**：通常选择数组的第一个元素作为基准值。
2. **分区操作**：将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于或等于基准。这个过程通常通过一趟比较完成。
3. **递归查找**：如果基准位置就是目标关键字，返回 true；若关键字比基准小，在数组的左半部分查找；若关键字比基准大，在右半部分查找。
4. **结束条件**：如果遍历完整个数组都没有找到关键字，返回 false。

在实际编程中，可以采用如下的伪代码表示:

function quickSearch(array a, target key):
    if array is empty or key is not in array:
        return False
    
    pivot = getFirstElement(a)
    less = [element for element in a if element < pivot]
    equalOrGreater = [element for element in a if element >= pivot]

    if key in equalOrGreater:
        # 递归在右侧查找
        return quickSearch(equalOrGreater, key)
    else:
        # 如果目标不在右侧，它一定在左侧
        return quickSearch(less, key)

有15个已经排好序的数存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。 如果该数不在数组中，则输出无此数。请填空。 变量说明：top，bott为查找区间两端点的下标；loca为查找成功与否的开关变量。

### 回答1：
算法如下：

1. 初始化变量top为数组最后一个元素的下标，bott为数组第一个元素的下标，loca为。

2. 用折半查找法查找该数在数组中的位置：

a. 计算中间位置mid=(top+bott)/2。

b. 如果该数等于数组中第mid个元素的值，则将loca设为1，表示查找成功。

c. 如果该数小于数组中第mid个元素的值，则将top设为mid-1，继续在左半部分查找。

d. 如果该数大于数组中第mid个元素的值，则将bott设为mid+1，继续在右半部分查找。

3. 如果查找成功，则输出该数在数组中的位置；否则输出无此数。

代码如下：

int binary_search(int a[], int n, int x)
{
int top = n - 1, bott = , mid, loca = ;
while (top >= bott)
{
mid = (top + bott) / 2;
if (x == a[mid])
{
loca = 1;
break;
}
else if (x < a[mid])
top = mid - 1;
else
bott = mid + 1;
}
if (loca)
return mid + 1;
else
return -1;
}

int main()
{
int a[15] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};
int n = 15, x, pos;
printf("请输入要查找的数：");
scanf("%d", &x);
pos = binary_search(a, n, x);
if (pos == -1)
printf("无此数\n");
else

### 回答2：
折半查找法是一种高效的查找算法，在有序数组中查找元素时比线性查找更快速。具体实现方法如下：

1. 定义变量top为查找区间的最高端下标（即数组最后一个元素的下标），bott为查找区间的最低端下标（即数组第一个元素的下标），loca为查找成功与否的开关变量，初值为0。
2. 判断top和bott的大小，若top比bott小，则查找失败，输出无此数。否则，令mid等于top和bott之和的一半（向下取整）。
3. 比较mid位置的元素与输入的数。若它们相等，则说明查找成功，将loca变量的值置为1，输出mid+1表示该数是数组中第几个元素的值。若mid位置的元素小于输入的数，则在[mid+1,top]区间内继续查找。否则，在[bott,mid-1]区间内继续查找。
4. 重复步骤2-3，直到查找成功（loca=1）或查找失败（top<bott）。

以下是用C语言实现折半查找的代码：

#include <stdio.h>

int binary_search(int *arr, int len, int target) {
    int top = len-1, bott = 0, loca = 0;
    while (top >= bott) {
        int mid = (top + bott) / 2;
        if (arr[mid] == target) {
            loca = 1;
            return mid+1;
        } else if (arr[mid] < target) {
            bott = mid+1;
        } else {
            top = mid-1;
        }
    }
    if (!loca) {
        printf("无此数\n");
        return -1;
    }
}

int main() {
    int arr[15] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};
    int len = sizeof(arr) / sizeof(arr[0]);
    int target;
    printf("请输入要查找的数：");
    scanf("%d", &target);
    int pos = binary_search(arr, len, target);
    if (pos != -1) {
        printf("该数是数组中第%d个元素的值\n", pos);
    }
    return 0;
}

假设输入的数为13，则输出为“该数是数组中第7个元素的值”。假设输入的数为26，则输出为“无此数”。

### 回答3：
折半查找法也被称为二分查找法，其主要思想是将有序数组分成两半，通过与中间元素的比较来判断要查找的数在左侧还是右侧，再将查找区间缩小一半，直到查找到目标数或区间为空。

对于本题，我们可以使用如下的代码实现：

int num[15] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}; // 已排序数组
int n; // 要查找的数
int top = 14, bott = 0; // 查找区间的上下界
int loca = 0; // 查找成功与否的开关变量
int mid; // 中间元素的下标

printf("请输入要查找的数：");
scanf("%d", &n);

while (top >= bott) {
    mid = (top + bott) / 2; // 取中间元素下标

    if (num[mid] == n) {
        loca = mid + 1; // 找到了，记录位置
        break; // 结束循环
    } else if (num[mid] > n) {
        top = mid - 1; // 在左半部分查找
    } else {
        bott = mid + 1; // 在右半部分查找
    }
}

if (loca == 0) {
    printf("无此数。\n");
} else {
    printf("%d 是数组中的第 %d 个元素。\n", n, loca);
}

在这段代码中，我们首先定义了一个已排好序的数组 `num`，并且输入了需要查找的数 `n`。接着，我们使用 `while` 循环来查找数在数组中的位置，其中 `top` 和 `bott` 分别表示查找区间的上下界， `mid` 表示中间元素的下标。每次查找时，我们先比较要查找的数和中间元素的大小关系，如果相等则已经找到，记录位置后结束循环；如果要查找的数比中间元素小，则在左半部分查找，将查找区间的上界 `top` 设为中间元素的前一个位置，继续下一轮循环；如果要查找的数比中间元素大，则在右半部分查找，将查找区间的下界 `bott` 设为中间元素的后一个位置，继续下一轮循环。如果最终 `loca` 仍为零，则说明要查找的数不在数组中，输出无此数；否则输出该数在数组中的位置。

需要注意的是，在比较大小时，我们使用了 `num[mid] == n` 和 `num[mid] > n` 这两种情况，而没有使用 `num[mid] < n` 的情况。这是因为如果 `num[mid] < n`，则该数一定在中间元素的后面，因此将查找区间的下界设为中间元素的后一个位置即可。