旭++
张旭的C++学习笔记
posts - 5, comments - 8, trackbacks - 0, articles - 0
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
智能猜数字程序中的疑问
Posted on 2007-12-01 17:05
张旭
阅读(484)
评论(0)
编辑
收藏
引用
今天花了一下午的时间学习李老师新写的智能猜数字程序,从执行效率上来看,在取值范围比我做的大1万倍的情况下,计算次数几乎相同。所以我学习的重点集中在,算法是如何优化的。
首先回忆我自己的程序算法,是先创造一个结果全集(在取四位的情况下全集是1万),在根据提示逐步筛选出正确的答案。但是这种算法在全集总数巨大的时候(李老师的程序取8位,全集为1亿),那么程序的执行效率必然是大打折扣的。
智能猜数字游戏中最关键的就是计算机产生假设的那个函数,李老师的相关函数是
char
*
generate_new_answer (RECORD
*
ar, OPTIONS
*
opt)
我的疑问也主要集中在这部分,先说说我看明白的部分。
1
if
(
!
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是集合中剩余结果的数量。
1
ar
->
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
}
上面这段是进入循环之后的第二段代码,
将这个结果和前几次的猜测做“猜数字判断”,如果和之前的猜测结果不完全相同的,则跳出。
这一点不太明白。首先为什么要和之前的结果做比对。之前的结果是猜数和答案的关系。而新猜数和旧猜数之间的关系能说明什么呢?这不是惯常的思路。
1
if
(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时,也就是(当前数字和之前猜数)的比对结果和(之前猜数和答案)的比对结果都不一样的时候。这该数字为新的猜数。返回。
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
Powered by:
C++博客
Copyright © 张旭
日历
<
2007年12月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
公告
本博客文章全部原创,转载请留言告知本人,并注名出处。
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
实训日志
随笔档案
2007年12月 (5)
文章分类
参考文档
学习笔记
搜索
最新评论
1. re: linux fork函数学习
你知道fork后系统是怎么分清那个该子进程运行哪些是父进程运行吗?
--过客
2. re: linux fork函数学习[未登录]
请问最后一个程序,是不是father和son的输出没有规律,第一组是father和son的组合,第二组是两个father和两个son的组合,最后一组是四个father和四个son的组合就是了吗?
--noname
3. re: linux fork函数学习[未登录]
good!
--noname
4. re: linux fork函数学习
gcc怎么写
--er
5. re: linux fork函数学习
很强大。。。
--林
阅读排行榜
1. linux fork函数学习(11573)
2. Linux FTP server 学习小结(C)(2307)
3. TCP/IP编程实现远程文件传输(2201)
4. socket编程学习笔记(1)(622)
5. 智能猜数字程序中的疑问(484)
评论排行榜
1. linux fork函数学习(7)
2. Linux FTP server 学习小结(C)(1)
3. socket编程学习笔记(1)(0)
4. TCP/IP编程实现远程文件传输(0)
5. 智能猜数字程序中的疑问(0)