C 指针原理揭秘:基于底层实现机制 (13):C 语言快速入门 2.2.6

阅读数:6 2019 年 12 月 11 日 20:21

C指针原理揭秘:基于底层实现机制(13):C语言快速入门 2.2.6

(自动猜数算法)

内容简介
全书分为准备篇、基础篇、揭秘篇、实战篇。本书力求从底层实现机制进行解析,同时配合 C/C++ 编程技巧以及某些指针运用技巧,讲解如何提高程序效能,如何避免滥用指针。
准备篇中介绍 C 指针概述、UBUNTU 及开发环境配置、AT&T 汇编简介、编译原理基础;基础篇将对 AT&T 汇编以及 C 指针基础进行介绍;揭秘篇讲述高级 C 指针的实现机制以及 C++ 指针实现机制,同时讲解编程技巧和 C/C++ 指针高级应用;实战篇讲解解释语言指针、TCC 编译实践、垃圾回收等高级 C 指针应用话题。

能不能让电脑程序拥有智能,让程序来猜数字呢?肯定可以,只需要编写 C 程序实现某种算法即可。在国内,算法最早出现在《周髀算经》 《九章算术》之中;在国外,古希腊数学家欧几里得(Euclid,约公元前 325 年—公元前 265 年)出版了《几何原本》,闻名于世。人类历史上第一次将算法编写为程序的是 Ada Byron,其于 1842 年为巴贝奇分析机编写求解伯努利微分方程的程序,Ada Byronl 也因此被大多数人认为是世界上第一位程序员。

算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。为了能让程序实现自动猜数,必须假设一个前提:程序不知道要猜的数字,也就是说这个算法中只能与要猜的数字进行比较,而不能直接“知道”要猜的数字值。分析算法目标,可使用类似于折半查找法的算法,折半查找法又称二分查找法,是一种在有序数组中查找某一特定元素的搜索算法。查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从新的中间元素开始进行比较。如果在某一步骤中数组为空,则代表找不到。这种搜索算法每进行一次比较都会使搜索范围缩小一半。

例如,在一个升序排列的数字列表 2、6、7、34、76、123、234、567、677、986 中查找数字 123 所处的位置,算法过程具体如下:首先,将 first(下限) 指向最小数字 2 的位置,last(上限) 指向最大的数字 986 的位置,得到 first 的值为 1,而 last 的值为 10,计算位于它们的 mid(中间位置)为 6,数字为 76;然后将 76 与 123 进行比较,发现 123 比 76 大,于是将 first 设为 mid 之后的位置(即 6),last 不变,按与上一步同样的方法,计算 first 与 last 的 mid 为 8,将 last 设为中间位置的前一位置;最后,再次计算新的 mid, 直到 mid 处的值等于 123 为止,这样就能成功找到 123 的位置,处于数字列表的第 6 个位置。整个过程如图 2-1 所示。

折半查找算法查找的范围每次缩小一半,因此查找效率较高,我们可以借鉴这个思想,设计自动猜数算法:当输入一个数字时,会得到一个反馈,输入的数字相对被猜数字是大了还是小了,将被猜数字作为查找目标,将 1 到输入数字的范围作为查找范围,实现自动猜数。如果输入数字大了,就将输入数字作为查找范围的上限,如果输入数字小了,就将输入数字作为查找范围的下限,每输入一次数字,就缩小了查找范围的一半,这样很快就能猜中,赢得游戏的胜利,算法过程具体如下。

C指针原理揭秘:基于底层实现机制(13):C语言快速入门 2.2.6

图 2-1 折半查找法

1)设数字范围 R 为 1~500。

2)取范围 R 以内的中间值 A,把 A 作为程序模仿人类猜测出的数字。

3)将猜测的数字 A 与被猜的结果 B 进行比较

a)如果 A>B,则将 R 的上限设为 A,回到第 2 步。

b)如果 A<B,则将 R 的下限设为 A,回到第 2 步。

c)如果 A=B,则退出程序,提示猜中数字,进入第 4 步。

4)在屏幕上输出 A 和 B,并提示猜中数字。

程序 2-9 自动猜数算法
复制代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//code:myhaspl@myhaspl.com
//date:2014-01-23
int getnumber(){
srand((int)time(0));
return rand()%499+1;
}
int main(){
int mynum;
int ispass=0;
int guessnum=getnumber();
int myrange[2]={1,500};
while (1){
mynum=(myrange[0]+myrange[1])/2;
if (mynum>guessnum){
printf(" 程序猜的数字为 %d,数字大了!\n",mynum);
myrange[1]=mynum;
}
else if(mynum<guessnum){
printf(" 程序猜的数字为 %d,数字小了!\n",mynum);
myrange[0]=mynum;
}
else{
printf(" 程序猜的数字为 %d,被猜的数字为 %d, 猜中了!\n",mynum,guessnum);
break;
}
}
}

编译后程序的运行结果如下,仅仅 7 次,程序就猜出了数字:

复制代码
$gcc guessnum.c -o myguess
$ ./myguess
程序猜的数字为 250,数字大了!
程序猜的数字为 125,数字小了!
程序猜的数字为 187,数字大了!
程序猜的数字为 156,数字小了!
程序猜的数字为 171,数字大了!
程序猜的数字为 163,数字小了!
程序猜的数字为 167,被猜的数字为 167, 猜中了!

程序 2-9 中使用了 C 语言的数组概念,数组的定义如下所示:

复制代码
类型 数组名 [数组长度]={用逗号分隔的数组初始值}

程序 2-9 中将 myrange 变量(表示猜数范围)定义为一个包含 2 个元素(第 1 个元素 1 表示下限,500 表示上限)的数组,如下面代码所示:

复制代码
int myrange[2]={1,500};

数组元素引用的方式是数组名 [数组索引],其中数组索引从 0 开始。例如,程序 2-10 计算猜数时,通过数组索引形式取得 myrange 数组的上限与下限后,计算它们之间的平均值取得猜数范围内的中间值,如下面代码所示:

复制代码
mynum=(myrange[0]+myrange[1])/2;

C指针原理揭秘:基于底层实现机制(13):C语言快速入门 2.2.6

购书地址 https://item.jd.com/12533413.html?dist=jd

评论

发布