旭++

张旭的C++学习笔记
posts - 5, comments - 8, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

智能猜数字程序中的疑问

Posted on 2007-12-01 17:05 张旭 阅读(481) 评论(0)  编辑 收藏 引用
      今天花了一下午的时间学习李老师新写的智能猜数字程序,从执行效率上来看,在取值范围比我做的大1万倍的情况下,计算次数几乎相同。所以我学习的重点集中在,算法是如何优化的。
      首先回忆我自己的程序算法,是先创造一个结果全集(在取四位的情况下全集是1万),在根据提示逐步筛选出正确的答案。但是这种算法在全集总数巨大的时候(李老师的程序取8位,全集为1亿),那么程序的执行效率必然是大打折扣的。
      智能猜数字游戏中最关键的就是计算机产生假设的那个函数,李老师的相关函数是

char * generate_new_answer (RECORD * ar, OPTIONS * opt)

      我的疑问也主要集中在这部分,先说说我看明白的部分。

 1if (!ar->count)
 2    {   // First step work
 3//        i = size = (unsigned long) pow (opt->total_num, opt->select_num)+2;
 4  
 5        for (i=0, size = 1; i<opt->select_num;i++)//计算集合的总数 
 6        {
 7            size *= opt->total_num;
 8        }

 9        i = size = size + 2
10        
11        for (j=0; j<opt->select_num; j++)
12        {
13            ar->answer[ar->count  ][opt->select_num-j-1= opt->resource [(opt->total_num*10-j-1)%opt->total_num];
14            ar->answer[ar->count+1][j] = opt->resource [opt->total_num-1];
15        }

16        return (ar->answer[ar->count]);
17    }
 
      上面这一段是当还未进行猜测的时候触发的一段函数。
      5-9行是计算一下整个集合的数量,10选8的结果应该是10的8次方,1亿。其中变量i在之前静态声明。
      11-15行是生成第一次和第二次要猜测的answer。至于为什么要固定第一次和第二次的猜测答案。在我的程序中也有类似的设定,我的全集是(0000-9999)规定第一次猜测9876,第二次猜测2345。这样做的好处是可以最大限度的加速猜测速度。如果第一次猜0000,而第二次猜1111的话,排除掉的结果比较少。
      最后函数返回第一次的猜测结果。 
      
for (; i; i--)
    
{

    }

      上面这个循环是当有了猜测数后,开始进行排除工作,最后产生一个有效的新的答案。i是集合中剩余结果的数量。

 1ar->answer[ar->count][0++;
 2        for (j=0; j<opt->select_num; j++)
 3        {
 4            if (ar->answer[ar->count][j] > opt->resource [opt->total_num-1])
 5            {
 6                ar->answer[ar->count][j] = opt->resource [0];
 7                ar->answer[ar->count][j+1]++;
 8                ar->answer[ar->count][opt->select_num] = 0;
 9            }
 else
10            {
11                break;
12            }

13        }

      上面这段是进入循环之后的第一段代码,
      1行,猜测次数加1.
      2-13行从注释来看这是生成一个新的答案系列,可是我只能看出这是对本次对比筛选的答案的检查,看是否超出全集中的范围。
1  for (j=0; j<ar->count; j++)
2        {   // compare with all records
3            give_answer_tip (tip, ar->answer[j], ar->answer[ar->count], opt->select_num);
4            if (tip[0!= ar->tip[j][0|| tip[1!= ar->tip[j][1])
5            {
6                break;
7            }

8        }

      上面这段是进入循环之后的第二段代码,
      将这个结果和前几次的猜测做“猜数字判断”,如果和之前的猜测结果不完全相同的,则跳出。
      这一点不太明白。首先为什么要和之前的结果做比对。之前的结果是猜数和答案的关系。而新猜数和旧猜数之间的关系能说明什么呢?这不是惯常的思路。      
1if (j == ar->count)
2        {   // pass all records check, record new answer
3            memcpy (ar->answer[ar->count+1], ar->answer[ar->count], opt->select_num);
4            return (ar->answer[ar->count]);
5        }

      当上一个循环没有break时,也就是(当前数字和之前猜数)的比对结果和(之前猜数和答案)的比对结果都不一样的时候。这该数字为新的猜数。返回。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理