请大家再来思考一下这个问题
题目：给定正整数 k 和 n 位正整数 a (0 <= k <= n)。
从 a 中删掉任意 k 位数字，将剩下的给位数字按原次序排列组成一个新的正整数。
对于给定的 n 位正整数 a 和正整数 k，编程计算从 a 中删去 k 位数字后能够得到的最小的数。
[例]
输入： 5412873 3
输出： 1273
请大家贴出自己的思考也好，分析也好，算法也好，代码也好，多多交流，共同进步。
以下是我的思路和实现：
程序代码：
/*
分析:
以 a[i], (0 <= i < n)表示 n 位正整数 a 的第 i 位, a[0] 为最高位, a[n - 1] 为最低位, n 位数字 a 可以写成以下形式:
a[0] * 10 ^ (n - 1) + a[1] * 10 ^ (n - 2) + a[2] * 10 ^ (n - 3) + ... + a[n - 2] * 10 ^ 1 + a[n - 1] * 10 ^ 0
经观察可知 d[0] 比 d[k], (0 < k < n) 对数字 a 的值的影响比 d[k] 更为明显, 我们说 d[0] 比 d[k] 更为重要.
一般而论, d[i] 比 d[k], (i < k < n) 更为重要.
题目要求“剩下的数字按原次序排列组成一个新的正整数”和“对于给定的正整数 a,编程计算删去 k 个数字后得到的最小数”.
因此思考的重点为如何得到最小的数.
设 n - k = m, 题目的正确答案为 m 位数字 b,
则 b[0] 必然是 a[0] ~ a[k] 中的一位数字, 且 b[0] 为 a[0] ~ a[k] 中 最小的一位数字, 如下例:
n = 4, a = 4123, k = 2;
从 4 位正整数 a 中删掉任意 2 位后,可能的结果为:
12
13
23
41
42
43
b = 12, b[0] = 1 = a[2] 为 a[0] ~ a[2] (即 4, 1, 2) 中最小的数字.
因此我们所设计的程序应首先找出a[0] ~ a[k] 中最小的一位 a[j], 并将此位作为答案的最高位 b[0].
要达到此目的,必须从 n 为正整数 a 中删除 a[0] ~ a[j - 1] 共 j 位.
因 a[j] 需要保留作为答案 b 的最高位,因此应将 j 从剩下的需要继续删除的数字中排除.
至此我们已经从 n 位正整数 a 中删除了 j 位,并排除了 1 位,接下来我们还需要删除 k - j 位.
为了保证最后的答案 b 最小, 必须保证从剩下的 n - j 位中删除 k - j位后所得的数字最小,为此我们只需要重复上述过程, 直至一共删除 k 位为止.
算法:
1. s = 0; s 表示搜索的起始位置
2. 找出 a[j] == min(a[s], a[s + 1], ... , a[k])
3. a[0] = -1, a[1] = -1 ... a[j - 1] = -1; a[0] = -1 表示删除a[0];
4. s = j + 1, k -= j - s; 从 a[j] 的下一位开始进行下一次的搜索, 即将 a[j] 从待删除数字中排除
5. 重复 2 ~ 4, 直至 k == 0 || n - s == k; n - s == k 时不需要再进行搜索, 只要把 a[s] ~ a[n] 全部删掉即可
代码:
*/
#include <stdio.h>
#include <string.h>
int main() {
char a[100] = {0}, i, j = 0, n, s = 0, is_1st_digit = 1;
int k;
printf("Please input number a: ");
scanf("%s", a);
n = strlen(a);
printf("Please tell me how many digits to be deleted: ");
scanf("%d", &k);
while (k > 0 && k < n - s) {
// find the minimun digit a[j]
for (i = s; i <= s + k; i++) {
if (a[i] < a[j]) {
if (!is_1st_digit || a[i] != '0') {
j = i;
}
}
}
// delet digits a[s] ~ a[j - 1]
for (i = s; i < j; i++) {
a[i] = -1;
}
// calculate how many more digits need to be deleted
k -= j - s;
// next search will start from a[j + 1]
j++;
s = j;
// there is only one 1st digit and we've already found it, so
is_1st_digit = 0;
}
if (k > 0) {
// delete digits d[s] ~ d[n]
n = s;
}
// printf() the answer.
for (i = 0; i < n; i++) {
if (a[i] != -1) {
printf("%c", a[i]);
}
}
printf("\n");
return 0;
}
[ 本帖最后由 voidx 于 2011-4-18 14:04 编辑 ]
