- 零基础学算法（第4版）
- 张昆 戴艳
- 2179字
- 2025-02-25 05:17:48
1.2 算法的作用：猜价格游戏
提起算法和算法设计，首先想到它是一门计算机基础课程。其实，算法思想体现的是一种数学思想。在数学中蕴涵了大量的算法内容和思想，比如《高等数学》《概率论》《离散数学》等。下面就先讲解下算法的作用。
1.2.1 算法的作用
算法有什么作用？或者说通过学习算法，对读者有什么用处？
其实，在现实生活中解决任何一个实际问题，都不可避免地会涉及算法问题，例如本章开头提到的存钱问题，再如节假日公司值班人员的排班问题等，都需要通过一定的算法，得到一个最优（或较优）的解决方案。
再具体到计算机程序设计范畴，算法的设计就显得更重要了。
编程体会 现在的程序设计语言非常多，无论是学VB、C、C++、C#，还是Java、Python等语言，都只是一种工具的使用，很容易上手。真正核心的东西还是算法的设计，这是最能体现知识产权的核心。
因此，通过对算法的学习，可提高读者的逻辑思维能力，做到有条理的思考，并把它表达出来，最终提高解决问题的能力。
1.2.2 实例：看商品猜价格
下面看一个游戏，从该游戏中读者可了解到通过一个好的算法，可在游戏中快速制胜。
中央电视台有一档娱乐节目“幸运52”，该节目中有一个看商品猜价格的游戏。游戏的具体过程是：首先出示一件价格在999元以内的商品，参与者要猜出这件商品的价格。在猜价格的过程中，主持人会根据参与者给出的价格，相应地给出“高了”或“低了”的提示。如果一分钟内猜中了商品的价格，将可以得到这件商品，并且可以继续猜下一件商品。
例如，假设有一辆实际价格为640元的自行车要参与者猜价格，提示是该自行车的价格在1000元以下，则一般参与者可能会按以下方式竞猜：
参与者：900
主持人：高了
参与者：850
主持人：高了
参与者：800
主持人：高了
参与者：750
主持人：高了
参与者：700
主持人：高了
参与者：650
主持人：高了
参与者：600
主持人：低了
参与者：610
主持人：低了
参与者：620
主持人：低了
参与者：630
主持人：低了
参与者：640
主持人：恭喜你，答对了，该商品属于你了！
说明 参与者在完成这次自行车价格竞猜的过程中，就体现了算法的思想，从最初的900猜到了640，在这个过程中，主持人对他的结果进行了多次判断，并给出提示。
该游戏参与者的算法思想是：商品价格在999元以下，自行车的价格应该不会太低，因此从900元开始竞猜，然后以50为单位递减，逐步向商品实际价格靠近，当所猜价格低于商品实际价格时，再以10为单位递增，即可快速猜中商品的价格（为简化以上的竞猜过程，假设商品的价格是10的倍数）。
这是一种算法，该算法不算坏，游戏参与者试猜了11次，就猜出了商品的实际价格。一分钟之内试猜11次应该是能完成的。
注意 如果商品实际价格更低，使用这种算法将需要更多的试猜次数。
那么，还有没有更好的算法？答案是肯定的。如果游戏参与者学习了算法设计中的二分法，肯定能用更少的次数猜到商品的价格（本书将在第5章介绍二分法）。使用二分法具体的竞猜过程如下：
参与者：500
主持人：低了
参与者：750
主持人：高了
参与者：620
主持人：低了
参与者：680
主持人：高了
参与者：650
主持人：高了
参与者：630
主持人：低了
参与者：640
主持人：恭喜你，答对了，该商品属于你了！
该游戏参与者的算法思想是：首先根据商品价格在0~999元，得出中间价500元（二分法的关键就是通过比较指定区间的中间值，将区间逐步缩小），如果实际价格比500元高，再调整价格区间为500~999元，然后取其中间值（这里约为500+250）750元，各次竞猜的过程如表1-1所示。
表1-1 二分法猜商品价格
提示 在用二分法猜商品价格时，中间值不要求非常准确，取近似值就可以。通过中间值的不断改变，可逐步缩小价格的范围，最终猜中实际价格。
使用这种算法，游戏参与者试猜了7次就猜出了商品的实际价格。
两种算法的比较：第1种算法试猜了11次（如果商品实际价格更低，可能还需要增加试猜次数）；第2种算法试猜了7次，比第1种算法少猜了4次（效率提高近40%）。
提示 由此可以看出，在日常生活、游戏中，如果善于合理选择有效的算法，可显著提高我们解决问题的效率。
使用C语言编写这个游戏的竞猜过程，具体代码如下：
【程序1-1】看商品猜价格程序源代码
1 #include <stdio.h> //函数头
2 int main() //主函数
3 {
4 int oldprice,price=0,i=0; //输入商品的真实价格
5 printf("请首先设置商品的真实价格:");
6 scanf("%d",&oldprice);
7 system("cls"); //清屏，隐藏输入的商品真实价格
8 printf("请输入试猜的价格:\n");
9 while(oldprice!=price) //循环判断输入的试猜价格
10 {
11 i++; //循环一次，变量i加1
12 printf("参与者:");
13 scanf("%d",&price);
14 printf("主持人:") ;
15 if(price>oldprice) //如果试猜价格高于实际价格
16 {
17 printf("高了\n"); //输出“高了”
18 }
19 else if(price<oldprice) //如果试猜价格低于实际价格
20 {
21 printf("低了\n"); //输出“低了”
22 }
23 else //如果猜中实际价格
24 {
25 printf("恭喜你, 答对了, 该商品属于你了!\n\n你一共试猜了%d次.\n",i);
26 }
27 }
28 getch(); //实现程序运行完了暂不退出的效果，等你按任意键继续
29 return 0;
30 }
【程序说明】
为了让计算机自动判断参与者的试猜是否正确，首先需要由主持人输入商品的真实价格（程序第5~7行完成该功能，也可从一个文件中读入商品价格，这里为了简化程序，就使用直接输入的方法），如图1-1所示。当主持人输入价格后，执行第7行进行清屏操作，接下来就可由参与者输入试猜的价格，由计算机代替主持人自动判断输入价格的高低（程序第9~27行完成该功能），执行效果如图1-2所示。
图1-1 输入商品真实价格
图1-2 试猜过程
说明 以上C语言程序在命令模式下执行，为了节省印刷油墨，也为了不使图的大部分看起来一团黑，所以将Windows XP的命令窗口设置为白色背景，黑色文字。本书后面的程序执行结果截图都使用这种方式。