《C解毒》征询意见帖

群雄逐鹿中原

hellioncu 发表于 2012-10-21 19:57
循环次数依赖于生成的随机数，存在理论上的可能。
像你这样对别人要求这么高的人，自己怎么能写这样的 ...

貌似和13楼haomarlin说的同一个道理
http://bbs.chinaunix.net/forum.p ... mp;fromuid=22014451

比如一个随机函数，可随机得出0和1。
0，1出现的概率分别为40%和60%。

但是尽管如此，仍不排除连续得到1万亿次0的可能。
只要是真随机，就一定有这种可能存在。（没学过概率论，请原谅俺这个朴素的设想）

starwing83

回复 265# pmerofc


    这里有个generate，你看如何？

1. void generate(int d[], int n) {
   
2.     char nums[] = "1234567890";
   
3.     int i, cnt = sizeof(nums) - 1;
   
4.     assert(n >= 1 && n <= cnt);
   
5.     *d++ = nums[i = rand() % --cnt] - '0'; /* from 1 to 9 */
   
6.     memmove(nums+i, nums+i+1, cnt-i); /* erase nums[i] */
   
7.     while (--n) {
   
8.         *d++ = nums[i = rand() % cnt--] - '0'; /* from 1 to cnt */
   
9.         memmove(nums+i, nums+i+1, cnt-i); /* erase nums[i] */
   
10.     }
    
11. }
    

复制代码

starwing83

回复 271# 群雄逐鹿中原


    楼主的这个算法，应该算是拉斯维加斯算法之一。有无穷循环的“可能性”，问题是这种可能性是随着循环逐次下降的。对于随机算法（主要是蒙特卡罗算法）来说，有一个公认的观点：“如果软件出问题的可能性比硬件随坏的可能性还要小，我们倾向于认为这个算法是没有问题的”，这个可能无穷循环的算法即符合这个论断。

starwing83

回复 264# pmerofc


    我不明白为嘛不采用字符数组。我的generate在字符数组下更简单，而且字符数组本身也是很方便的。最后，我完全没有发现使用字符数组有什么“引起其他方面的问题”，如果要我写这样的代码，我自己也宁愿用字符数组的……

starwing83

我自己写了一个，要不要评析一下？

1. #include <assert.h>
   
2. #include <ctype.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <time.h>
   
7. 
   
8. #define GUESS_NUM   4
   
9. #define GAME_COUNT 10
   
10. 
    
11. int check(const char nums[], const char guess[], size_t n, int *pb) {
    
12.     int i, a = 0, b = 0;
    
13.     for (i = 0; i < n; ++i) {
    
14.         if (nums[i] == guess[i])
    
15.             ++a;
    
16.         else if (strchr(nums, guess[i]) != NULL)
    
17.             ++b;
    
18.     }
    
19.     if (pb) *pb = b;
    
20.     return a;
    
21. }
    
22. 
    
23. void cswap(char *a, char *b) {
    
24.     char tmp = *a;
    
25.     *a = *b;
    
26.     *b = tmp;
    
27. }
    
28. 
    
29. void generate(char d[], size_t n) {
    
30.     char nums[] = "1234567890";
    
31.     int i, cnt = sizeof(nums) - 2;
    
32.     assert(n >= 1 && n <= cnt);
    
33.     *d++ = nums[i = rand() % cnt]; /* from 1 to 9 */
    
34.     cswap(nums+i, nums+cnt); /* remove nums[i] from 0~cnt */
    
35.     while (--n) {
    
36.         *d++ = nums[i = rand() % cnt]; /* from 1 to cnt */
    
37.         cswap(nums+i, nums+cnt); /* remove nums[i] from 0~cnt */
    
38.         --cnt; /* drop nums[cnt] */
    
39.     }
    
40.     *d++ = '\0';
    
41. }
    
42. 
    
43. int checkinput(const char buff[], size_t n) {
    
44.     int mask = 0;
    
45.     size_t i;
    
46.     for (i = 0; i < n; ++i) {
    
47.         if (!isdigit(buff[i])) {
    
48.             fprintf(stderr, "not number, retry: ");
    
49.             return 0;
    
50.         }
    
51.         if ((mask & (1 << (buff[i] - '0'))) != 0) {
    
52.             fprintf(stderr, "duplicate number, retry: ");
    
53.             return 0;
    
54.         }
    
55.         mask |= 1 << (buff[i] - '0');
    
56.     }
    
57.     return 1;
    
58. }
    
59. 
    
60. int getline(char buff[], size_t n) {
    
61.     char tmp[BUFSIZ];
    
62. retry:
    
63.     if (fgets(buff, n+1, stdin) == NULL)
    
64.         return 0;
    
65.     if (strlen(buff) != n || buff[n-1] == '\n') {
    
66.         fprintf(stderr, "expect %d number, retry: ", (int)n);
    
67.         goto retry;
    
68.     }
    
69.     while (fgets(tmp, BUFSIZ, stdin) != NULL &&
    
70.             strlen(tmp) == BUFSIZ-1 &&
    
71.             tmp[BUFSIZ-1] != '\n')
    
72.         ;
    
73.     if (!checkinput(buff, n))
    
74.         goto retry;
    
75.     return 1;
    
76. }
    
77. 
    
78. int main(void) {
    
79.     char nums[GUESS_NUM+1], guess[GUESS_NUM+1];
    
80.     int i = 0;
    
81. 
    
82.     srand((unsigned)time(NULL));
    
83.     generate(nums, GUESS_NUM);
    
84.     printf("-- Guess Number --\n");
    
85. 
    
86.     for (i = 0; i < GAME_COUNT; ++i) {
    
87.         int a, b;
    
88.         fprintf(stderr, "times %d/%d: ", i+1, GAME_COUNT);
    
89.         if (!getline(guess, GUESS_NUM))
    
90.             return 1;
    
91.         a = check(nums, guess, GUESS_NUM, &b);
    
92.         printf("%dA%dB\n", a, b);
    
93.         if (a == GUESS_NUM) {
    
94.             printf("win!\n");
    
95.             return 0;
    
96.         }
    
97.     }
    
98. 
    
99.     printf("fail! answer is %s\n", nums);
    
100.     return 1;
     
101. }
     
102. 
     

复制代码

已修改，修改了，提示，去掉了memmove。

starwing83

回复 279# pmerofc


    修改是没问题的。但是我还是要声明一下。

写这段代码的目的，是在说明采用char数组作为数据结构对这道题来说是合理的。问题在于在整个代码中一贯地处理数据结构，从头到尾都是char数组。

其次，这段代码里面最大的函数，是对输入进行处理。我是想说明，对于这种交互性的程序，对输入的处理应该进行最大的关注。只有输入被处理好了，剩下的才有意义。否则，代码谈不上健壮性。

最后，关于goto，可以说我是有意而为之的。你可以看到，在这个地方，goto是最简单的写法。我曾经试过do { .... } while (!checkinput(...));这种写法，但是我发现即使是这样，我依然需要在中间一个地方进行跳转，而一个简单的continue不能完成目的，因为即使continue，checkinput也会被执行，造成行为错误。

Roberto（Lua作者）对于goto的观点是这样的：goto的问题是历史性的。goto的出现远远早于if，while，for，switch这些控制结构。在缺乏这些现在看来是必须的数据控制结构的前提下（特别是while），goto自然被用来模拟所有的控制流程，从而导致一个函数里面出现大量的goto，更糟糕的是，那个时期还没有标号的概念，goto的参数是行号，这样大大增加了理解代码的复杂性。在控制结构趋于成熟的今天，goto的问题已经没有那么严重了。如果一个问题的最佳解决方案就是goto，那么正常的使用goto，是应该被提倡的（至少不应该仅仅以“是goto”的原因而被反对）。如果还是觉得有问题，可以思考这样的一个情形：我在Server的那个贴提出了作者的目的仅仅是为了模拟一个新的语言要素coroutine，coroutine是continuation的简化版。而continuation技术，就是第一类值的goto！什么意思呢？我们假设C里面支持continuation，那么结果可能是这样的：

lablel i = newlabel();
....
func(i);
...

func内部会这么做：goto(i)，就跳转到了label i的下一行！！这根本就是跨函数的goto，说句实在话，这种技术比goto更加灵活，更加不可控，但是为什么从没有听说人们抱怨coroutine或者continuation不安全，会导致代码可读性下降呢？

不要迷信教条，特别是在计算机领域，因为教条存在的环境很可能已经发生了巨大的变化。

在我看来，goto的三种使用方式是非常合理的（有没有其他的合理使用方式我还不清楚）：
1. 用作模拟尾递归调用。这可以在即使C编译器不支持尾递归的前提下，也能模拟正确的尾递归调用。即我的代码出现的情况。这里的goto retry，其实就是return getline(...);而已。
2. 用作跳出多重循环。这一点除了goto没有办法做到，不用goto，就意味着大量的判断和标志位。
3. 用作错误处理，这一点在大量的开源代码中可以见到，是实践证明行之有效的用法。

我对“goto猛如虎”的观念嗤之以鼻，任何教条，都不该被妖魔化，应该在完全领会教条的意图的情况下来遵守或违背，这是我一贯的观点。