问题描述：编写函数，对一个有序的整型数组进行二分检索（也称折半查找）。
函数声明为：int binarysearch(int a[], int n, int key)或其它合适形式。
输入：依次输入n, key及n个元素（n不超过10,输入时确保数组元素递增）
输出：根据检索结果输出Y/N 样例1：
输入：5 3 1 2 3 4 5 输出：Y 样例2：
输入：10 8 11 22 33 44 55 56 78 79 80 100
输出：N
#include <stdio.h>
int binarysearch(int a[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 查找成功
if (a[mid] == key) {
return 1; // 找到
}
// 查找左半部分
else if (a[mid] > key) {
right = mid - 1;
}
// 查找右半部分
else {
left = mid + 1;
}
}
return 0; // 没找到
}
int main() {
int n, key;
// 输入n和key
scanf("%d %d", &n, &key);
int a[n];
// 输入数组元素
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 调用二分查找函数
if (binarysearch(a, n, key)) {
printf("Y\n"); // 找到
} else {
printf("N\n"); // 没找到
}
return 0;
}
题目编号：Exp04-Enhance04,GJBook3-06-21
题目名称：索引数组排序 题目描述：已知n（n≤100）个元素的整型数组 A 未排序，一个索引数组 B 保存 A 的下标。编写程序，在不改变数组A的情况下，只改变数组 B完成对A的递增排序，如下所示：排序后索引数组B的第一个元素值是A数组中最小元素的下标。
#include <stdio.h>
void indexSort(int A[], int B[], int n) {
// 使用选择排序对B进行排序，按A[B[i]]值的大小进行排序
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (A[B[j]] < A[B[minIndex]]) {
minIndex = j;
}
}
// 交换B[i]和B[minIndex]
int temp = B[i];
B[i] = B[minIndex];
B[minIndex] = temp;
}
}
int main() {
int n;
// 输入数组大小n
scanf("%d", &n);
int A[n], B[n];
// 输入数组A的元素
for (int i = 0; i < n; i++) {
scanf("%d", &A[i]);
}
// 初始化索引数组B
for (int i = 0; i < n; i++) {
B[i] = i;
}
// 输出排序前的数组A
for (int i = 0; i < n; i++) {
if (i != 0) printf(" ");
printf("%d", A[i]);
}
printf("\n");
// 调用索引排序函数
indexSort(A, B, n);
// 输出排序后的索引数组B
for (int i = 0; i < n; i++) {
if (i != 0) printf(" ");
printf("%d", B[i]);
}
printf("\n");
return 0;
}
题目编号：Exp04-Basic07，GJBook3-06-01
题目名称：检验矩阵重复元素
题目描述：编写程序判断任意给定n*n的两维整型数组中是否有相同元素。
输入：第一行输入数组行数n（≤10），第二行随机输入nn个整数作为数组元素值。
输出：如果数组中有相同元素，则输出YES；否则，输出NO。
样例1： 输入： 3 1 2 3 4 5 6 7 8 9 输出： NO
样例2： 输入： 3 1 1 2 3 4 5 6 7 8 输出： YES
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int arr[n * n];
int foundDuplicate = 0; // 标志变量，是否找到重复元素
// 输入二维数组元素，展平成一维数组
for (int i = 0; i < n * n; i++) {
scanf("%d", &arr[i]);
}
// 检查是否有重复元素
for (int i = 0; i < n * n; i++) {
for (int j = i + 1; j < n * n; j++) {
if (arr[i] == arr[j]) {
foundDuplicate = 1;
break;
}
}
if (foundDuplicate) {
break;
}
}
// 输出结果
if (foundDuplicate) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
题目编号：Exp04-Enhance01,GJBook3-06-25
题目名称：规则形式构建集合
题目描述： 设整数集合 M 定义如下：
(1) 1∈M ； (2) 若 x ∈M , 则 2x+1 ∈M , 3x+1 ∈M ；
(3) 没有别的整数属于集合 M 。
编程序按递增顺序生成并输出集合 M 的前n项
输入：一个正整数n（≤300）。
输出：按递增序列输出n个属于集合M的整数，各数间以一个西文空格间隔；最后一个数后无字符。
样例1: 输入：10 输出：1 3 4 7 9 10 13 15 19 21
样例2： 输入：1 输出：1
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 300
// 使用一个队列来模拟最小堆
int heap[MAX_N * 10], heapSize = 0;
int visited[MAX_N * 1000] = {0}; // 标记元素是否访问过
// 比较函数，用于堆排序
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
// 向堆中插入元素
void insertHeap(int value) {
heap[heapSize++] = value;
qsort(heap, heapSize, sizeof(int), compare); // 重新排序堆
}
// 主程序
int main() {
int n;
scanf("%d", &n);
// 初始化堆，先加入1
insertHeap(1);
visited[1] = 1;
// 生成集合M并输出前n项
int result[MAX_N];
for (int i = 0; i < n; i++) {
// 获取堆顶的最小元素
int x = heap[0];
// 将堆顶元素放入结果数组
result[i] = x;
// 移除堆顶元素（模拟堆的删除操作）
for (int j = 0; j < heapSize - 1; j++) {
heap[j] = heap[j + 1];
}
heapSize--;
// 生成新的元素
int next1 = 2 * x + 1;
int next2 = 3 * x + 1;
// 如果没有出现过，插入堆中
if (!visited[next1]) {
visited[next1] = 1;
insertHeap(next1);
}
if (!visited[next2]) {
visited[next2] = 1;
insertHeap(next2);
}
}
// 输出前n个元素
for (int i = 0; i < n; i++) {
printf("%d", result[i]);
if (i != n - 1) {
printf(" ");
}
}
printf("\n");
return 0;
}
题目编号：Exp04-Basic10，GJBook3-06-12
题目名称：字符串反序
问题描述：编写程序，将给定的字符串反序输出。
输入：一个长度不超过255的字符串，字符串中可能含有空白字符。
输出：反序输出的字符串。
样例1：
输入 A
输出 A
样例2：
输入 123 45
输出 54 321
#include <stdio.h>
#include <string.h>
int main() {
char str[256]; // 用于存储输入的字符串
// 读取输入的字符串，使用fgets来处理空白字符
fgets(str, sizeof(str), stdin);
// 计算字符串的长度
int len = strlen(str);
// 去掉可能的换行符
if (str[len - 1] == '\n') {
str[len - 1] = '\0';
len--;
}
// 反转字符串
for (int i = 0; i < len / 2; i++) {
// 交换字符
char temp = str[i];
str[i] = str[len - 1 - i];
str[len - 1 - i] = temp;
}
// 输出反转后的字符串
printf("%s\n", str);
return 0;
}