删数问题（无输出）

xliotx

我知道这个东西发到这里可能不太合适，但这个问题我问了好多地方，实在是没有结果，希望各位大牛能帮忙解释下。谢谢。
【问题描述】输入一个高精度的大正整数S（S最长可达240位），去掉其中任意N位数字后剩下的数字按原次序组成一个新的正整数S’。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数S’最小。
【输入形式】输入有两行：
1.第一行是大整数S。其中S最长可达240位。
2.第二行是整数N。S、N均以非0数字开头。
【输出形式】输出有一行，是在S中删除N位后所得的最小数字S’。
【样例输入1】
178543
4
【样例输出1】13

【样例输入2】
1002
1
【样例输出2】002

【样例说明】样例1中输入整数S=178543，N=4，要求在178543中删除4位，使剩下的数字最小。正确答案为S’ = 13。样例2中输入整数S＝1002，N＝1，删完一位后S’ = 002，而不是2，即2之前的0也必须输出。
【运行时限】程序一次运行的最长时间限制在15秒内，超出则认为程序错误。

下面是我写的程序：

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. int main()
   
6. {
   
7.         char integer[250], result[250];
   
8.         int start = 0, length, strlength, n, i = 0, j, k = 0;
   
9. 
   
10.         fgets(integer, 249, stdin);
    
11.         strlength = strlen(integer);
    
12.         integer[strlength - 1] = '\0';
    
13.         scanf("%d", &n);
    
14.         length = strlength - n;
    
15.         for (i = 0; i <= 9; i++)
    
16.                 for (j = start; j < length && length <= strlength; j++)
    
17.                         if (integer[j] == i) {
    
18.                                 result[k++] = i;
    
19.                                 length++;
    
20.                                 start = j + 1；
    
21.                         }
    
22.         fputs(result, stdout);
    
23.         return 0;
    
24. }
    

复制代码

思路是：
从头开始由0-9开始检测，到末尾前所需位数为止，遇到最小的数字就放到result里，如果有，继续检测，没有，责从头再来。最后打出result。
现在的问题是，编译没错误，但没有输出。
搞了很长时间，没弄明白。
请高手帮解决一下，再次感谢。　

没本

姑且先不论你的算法正确与否，根据你的程序：for (i = 0; i <= 9; i++); result[k++] = i; 最后输出的result数组的每个单元都是0到9，以字符方式显示的话，ascii码0结束符，1-9都是控制符，当然不显示。
例如result[0]==1 ，你要显示的话就要先result[0] += '0'; 就能显示了。

xliotx

把fputs改成

1.         for (i = 0; i < k; i++)
   
2.                 printf("%d", result[i] + '0');
   

复制代码

还是不行。

remote fish

从表达上来讲, 楼主可能愿意把
for (i = 0; i <= 9; i++)
改为
for (i = '0'; i <= '9'; i++)

P.S. 最近在看 Haskell, 用 Haskell 写了一个, 提供四种解法, solve 看起来是穷举, 但是根据 haskell 的惰性求值原则, 实际上与 solve2 应该是一样的. solve2 则是手工根据各种不同的情况来进行处理. solve3 换了一种递归策略, solve4 进一步对 solve3 进行了归纳, 于是算法本身也描述得很清晰了. 由于本来也没打算让大家看明白, 因此注释就不加了, 纯当娱乐

2. main = do
3.     let (s, n) = ("1219", "1")
4.     --let (s, n) = ("172839", "3")
5.     --let (s, n) = ("312", "4")
6.     --let (s, n) = ("312", "1")
7.     --let (s, n) = ("555678", "3")
8.     --let (s, n) = ("555432", "3")
9.     --let (s, n) = ("555632", "3")
10.     --let (s, n) = ("555478", "3")
11.     --(s, n) <- input
12.     let result = solve s (read n)
13.     putStrLn ("result: " ++ result)
14.     let result2 = solve2 s (read n)
15.     putStrLn ("result2: " ++ result2)
16.     let result3 = solve3 s (read n)
17.     putStrLn ("result3: " ++ result3)
18.     let result4 = solve4 s (read n)
19.     putStrLn ("result4: " ++ result4)
20.     return ()
22. input :: IO (String, String)
23. input = do
24.     putStrLn "input S:"
25.     s <- getLine
26.     putStrLn "input N:"
27.     n <- getLine
28.     return (s, n)
30. solve :: String -> Int -> String
31. solve s 0 = s
32. solve s n
33.     | (n >= length s) = ""
34. solve (s0 : ss) n =
35.     min (s0 : solve ss n) (solve ss (n - 1))
37. solve2 :: String -> Int -> String
38. solve2 s 0 = s
39. solve2 s n
40.     | (n >= length s) = ""
41. solve2 (s0 : s1 : []) 1
42.     | (s0 <  s1) = s0 : []
43.     | (s0 >= s1) = s1 : []
44. solve2 (s0 : s1 : ss) 1
45.     | (s0 <= s1) = s0 : solve2 (s1 : ss) 1
46.     | (s0 >  s1) = s1 : ss
47. solve2 (s0 : s1 : ss) n
48.     | (s0 <  s1) = s0 : solve2 (s1 : ss) n
49.     | (s0 >  s1) = solve2 (s1 : ss) (n - 1)
50.     | (s0 == s1) = solve2 (s0 : solve2 (s1 : ss) (n - 1)) 1
52. solve3 :: String -> Int -> String
53. solve3 s 0 = s
54. solve3 (s0 : s1 : []) 1
55.     | (s0 <  s1) = s0 : []
56.     | (s0 >= s1) = s1 : []
57. solve3 (s0 : s1 : ss) 1
58.     | (s0 <= s1) = s0 : solve3 (s1 : ss) 1
59.     | (s0 >  s1) = s1 : ss
60. solve3 s n =
61.     solve3 (solve3 s (n - 1)) 1
62.    
63. solve4 :: String -> Int -> String
64. solve4 s 0 = s
65. solve4 (s0 : []) 1 = []
66. solve4 (s0 : s1 : ss) 1
67.     | (s0 <= s1) = s0 : solve4 (s1 : ss) 1
68.     | (s0 >  s1) = s1 : ss
69. solve4 s n = solve4 (solve4 s (n - 1)) 1
70.    
71. -- vim: set ts=4 sts=4 sw=4 et ai :

复制代码

没本

S到达240位的时候穷举不现实，需要线性规划单纯形法来解。

回xliotx：你用了%d就不需要+'0'了。+'0'的话用%c

xliotx

由于上课，不经常上网，所以回复的比较晚，谢谢楼上两位。
昨天看一楼的回复，晚上躺床上想到的，是数字和字符关系弄混，原来的算法也有些问题.
以下是我改过的.通过测试。

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. /* scan from 0 - 9, test the input, rescan if get the result. */
   
6. int main()
   
7. {
   
8.         char integer[250], result[250];
   
9.         int start = 0, strlength, n, i = 0, j, temp, k = 0;
   
10. 
    
11.         fgets(integer, 249, stdin);
    
12.         strlength = strlen(integer) - 1;
    
13.         integer[strlength] = '\0';
    
14.         scanf("%d", &n);
    
15.         for (i = 0; i <= 9; i++) {
    
16.                 temp = i;
    
17.                 for (j = start; j <= n && n < strlength; j++)
    
18.                         if (integer[j] == temp + '0') {
    
19.                                 result[k++] = temp + '0';
    
20.                                 n++;
    
21.                                 start = j + 1;
    
22.                                 i = -1;
    
23.                                 break;
    
24.                         }
    
25.         }
    
26.         for (i = 0; i < k; i++)
    
27.                 printf("%c", result[i]);
    
28.         return 0;
    
29. }
    

复制代码

思路是要在从左到右扫描一次，在满足所剩长度的前提下，取最小数作第一位（0-9的扫描），扫到后，从这位开始，重新开始扫描最小数。重复做下去，直到去满所要求的位数。

再次感谢大家的帮助。

xliotx

搜索了一下Haskell 语言，挺有意思的。
但目前3楼的高人写的东西敝人基本看不懂...

remote fish

我也只是刚开始学, 写着玩的. 由于 Haskell 的表达方式还没有习惯, 所以除了第一种穷举外, 后面几种代码上的演进也表明了我向 Haskell 的思维方式的逐渐演变. 解释一下最后一种算法, 就当做广告吧

2. -- 这是注释行
4. -- 这一行可以看作是函数的类型声明
5. solve4 :: String -> Int -> String
7. -- 下面开始求解
9. -- 从一个序列中删除 0 个数, 显然不做任何改动
10. solve4 s 0 = s
12. -- 从一个仅包含一个数的序列中删除一个数, 得到的是空序列
13. solve4 (s0 : []) 1 = []
15. -- 从一个长度大于 1 的序列中删除 1 个数, 要再分两种情况进行讨论
16. --  -- 当第一个数字大于第二个数字时, 显然删去第一个数字即得到结果
17. --  -- 当第一个数字不大于第二个数字时, 保留第一个数, 并在剩下的子序列中进行删一个数的操作  
18. solve4 (s0 : s1 : ss) 1
19.     | (s0 <= s1) = s0 : solve4 (s1 : ss) 1
20.     | (s0 >  s1) = s1 : ss
22. -- 删除 n 个数, 就是进行 n 次 "删除一个数" 的操作
23. solve4 s n = solve4 (solve4 s (n - 1)) 1

复制代码

Haskell 的表达与数学归纳法非常像, 通过逐渐减小问题的规模, 直至边界情况, 来简化并最终解决问题. 把上面的 4 种情况概括一下, 就是

重复 N 次:
    寻找从序列左边第一个元素开始的最长单调非降子序列, 删除其最后一个元素.

所谓单调非降子序列, 就是满足 S_i <= S_{i+1} 的子序列.

remote fish

solve4 的算法，是 O(N^2) 级别，但是对此算法进行分析我们可发现，N 次删除一个数的操作中，每一次都有决大部分的遍历是重复的，对此我们可再进行一些优化。在分析算法之前，先帖一段 Haskell 代码

1. 
   
2. solve5 s n =
   
3.     reverse $ helper [] s n
   
4.     where
   
5.         helper :: String -> String -> Int -> String
   
6.         helper d         s@([]   ) 0 = d
   
7.         helper d         s@(s':ss) 0 = helper (s':d) ss 0
   
8.         helper d@([]   ) s@(s':ss) n = helper (s':[]) ss n
   
9.         helper d@(d':ds) s@([]   ) n = helper ds [] (n - 1)
   
10.         helper d@(d':ds) s@(s':ss) n
    
11.             | (d' >  s')             = helper ds s (n - 1)
    
12.             | (d' <= s')             = helper (s':d) ss n
    

复制代码

用自然语言进行描述的话，就是：
(1) 将原始序列视为一个栈 s，右则数据在栈底，左侧数据在栈顶
(2) 另准备一个栈 d 来保存结果
(3) 待删除数的个数为 n
(4) 当 d 为空时，将 s 弹栈并压入 d
(5) 当 d 有数据时：
(5a)   比较 d 与 s 的栈顶 top(d) 与 top(s)，如果 top(d) > top(s)，d 弹栈，同时 n <- (n - 1)
(5b)   如果 top(d) <= top(s)，s 弹栈并压入 d 中
(6) 如果 s 栈空，则 d 弹栈，同时 n <- (n - 1)
(7) 如果 n != 0，则从 (4) 重新开始
(8) 如果 n 已为零时，将 s 依次弹栈并压入 d 中
(9) d 中保存的是最终结果，左侧数据在栈底，右侧数据在栈顶

此算法中，对 s 遍历一次，同时 d 要进行 n 次扔数据的操作。如果 s 的长度为 m，则最终时间复杂度为 O(m + n)

用 C 来实现的话

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include <time.h>
   
6. 
   
7. void randStr(char * s, int m)
   
8. {
   
9.         while (m--) {
   
10.                 *(s++) = rand() / (RAND_MAX + 1.0) * 10.0 + '0';
    
11.         }
    
12.         s[m] = 0;
    
13. }
    
14. 
    
15. void solve(char * d, char * s, int n)
    
16. {
    
17.         char * d0 = d--;
    
18. 
    
19.         for ( ; n; --d, --n) {
    
20.                 while (d < d0 || *d <= *s) {
    
21.                         *(++d) = *(s++);
    
22.                 }
    
23.         }
    
24.         while (*(++d) = *(s++)) ;
    
25. }
    
26. int main(void)
    
27. {
    
28.         srand(time(NULL));
    
29.         int m = 100000000;
    
30.         int n = m - 100;
    
31. 
    
32.         char * s = malloc(m + 1);
    
33.         randStr(s, m);
    
34. 
    
35.         char * d = malloc(m);
    
36.         printf("begin\n");
    
37.         solve(d, s, n);
    
38.         printf("d: %s\n", d);
    
39. 
    
40.         free(d);
    
41.         free(s);
    
42.         return 0;
    
43. }
    

复制代码

其中 randStr() 是随机数列生成器，solve() 是解答器

完整的 Haskell 则如下

1. 
   
2. import IO
   
3. import Random
   
4. 
   
5. main = do
   
6.     s <- randStr 1000000
   
7.     let n = "999900"
   
8.     print "begin"
   
9.     let result5 = solve5 s (read n)
   
10.     putStrLn ("result5: " ++ result5)
    
11.     return ()
    
12. 
    
13. randStr :: Int -> IO String
    
14. randStr 0 = return []
    
15. randStr n = do
    
16.     num <- randomRIO('0', '9')
    
17.     str <- randStr (n - 1)
    
18.     return (num : str)
    
19. 
    
20. solve5 :: String -> Int ->String
    
21. solve5 s n =
    
22.     reverse $ helper [] s n
    
23.     where
    
24.         helper :: String -> String -> Int -> String
    
25.         helper d         s@([]   ) 0 = d
    
26.         helper d         s@(s':ss) 0 = helper (s':d) ss 0
    
27.         helper d@([]   ) s@(s':ss) n = helper (s':[]) ss n
    
28.         helper d@(d':ds) s@([]   ) n = helper ds [] (n - 1)
    
29.         helper d@(d':ds) s@(s':ss) n
    
30.             | (d' >  s')             = helper ds s (n - 1)
    
31.             | (d' <= s')             = helper (s':d) ss n
    
32. 
    
33. -- vim: set ts=4 sts=4 sw=4 et ai :
    

复制代码

同样，randStr 是随机数列生成器，solve5 是解答器

下面来看一看运行效率

1. 
   
2. $ gcc -O3 main.c && time ./a.out
   
3. begin
   
4. d: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
   
5. 
   
6. real        0m4.600s
   
7. user        0m4.532s
   
8. sys        0m0.064s
   
9. 
   
10. $ ghc -O3 Main.hs && time ./a.out
    
11. "begin"
    
12. result5: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    
13. 
    
14. real        0m3.892s
    
15. user        0m3.748s
    
16. sys        0m0.144s
    

复制代码

我们可以看到，Haskell 中是 1000000 个数据保留 100 个，C 中是 100000000 个数据保留 100 个，二者的耗时在同一量级，因此 Haskell 的速度大约比 C 慢 100 倍。不过值得说明的是，两个程序的耗时中，实际上大半都是花在随机数生成过程中，因此具体计算部分的耗时有待更严密的比较