|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 mingcxx 于 2016-9-10 20:42 编辑
题目:编写一个程序解决选择问题。令k = N / 2。画出表格显示你的程序对于N为不同值时的运行时间。
(设有一组N个数确定其中第k个最大者,称选择问题(selection problem)。)
思路:读入前k个数到临时数组tmp(并按降序排列)。然后逐个读取后续数字X,当X大于第k个数时,将其加入数组tmp(并按降序排列)。最后返回位置k-1上的值。
实现:- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #define N 10000
- int select(int arr[], int n, int k);
- int main(void)
- {
- int * arr;
- int value;
- clock_t elapse;
- system("color 0A");
- srand((unsigned)time(NULL));
- arr = (int *)malloc(sizeof(int) * N);;
- for (int j = 0; j < N; j++)
- {
- arr[j] = rand() % 100000;
- printf("%d ", arr[j]);
- }
- putchar('\n');
- elapse = clock();
- value = select(arr, N, N / 2);
- elapse = clock() - elapse;
- printf("Value: %d, elapsed: %.4lfs\n", value, (double)elapse / 1000);
- free(arr);
- system("pause");
- return 0;
- }
-
- /*选择数组中第k个最大者*/
- int select(int arr[], int n, int k)
- {
- int * tmp;
- int i, j, ret;
- tmp = (int *)malloc(sizeof(int) * k);
- tmp[0] = arr[0];
- for (i = 1; i < k; i++) //读入k个元素并降序排列
- {
- tmp[i] = arr[i];
- for (j = i; j > 0; j--)
- {
- if (arr[i] > tmp[j - 1])
- {
- tmp[j] = tmp[j - 1];
- tmp[j - 1] = arr[i];
- }
- }
- }
- for (i = k; i < n; i++) //读入arr[k]
- {
- if (tmp[k - 1] < arr[i])
- {
- tmp[k - 1] = arr[i];
- for (j = k - 1; j > 0; j--)
- {
- if (arr[i] > tmp[j - 1])
- {
- tmp[j] = tmp[j - 1];
- tmp[j - 1] = arr[i];
- }
- }
- }
- }
- ret = tmp[k - 1];
- free(tmp);
- return ret;
- }
复制代码 记录:
小记:该算法在输入数据量较少时,可以在合理的时间内给出结果。如果数据量过大,这个算法就不切实际了。 |
|