编程算法之二分法

yaoyuan0701

http://blog.csdn.net/yaoyuan0701/article/details/44985667


最近读了一本编程算法的书，里面有些案例很有意思，所以分享给大家，其中会夹杂我自己的想法，希望大家也能学到一些东西！

我们经常从一些娱乐节目看见有种猜商品价格的游戏，例如：假设有一辆价格为640块钱的自行车要参与者猜价格，提示是该自行车的价格在1000元以下，一般参与者可以会按照以下方式竞猜：


参与者：900
主持人：高了
参与者：850
主持人：高了
参与者：800
主持人：高了参与者：750
主持人：高了参与者：700
主持人：高了参与者：650
主持人：高了参与者：600
主持人：高了参与者：610
主持人：低了参与者：620
主持人：低了参与者：630
主持人：低了参与者：640
主持人：恭喜你，答对了。
该参与者的算法思想是：商品价格在1000以下 自行车价格应该不会太低，因此从900开始猜，依次递减50，当低于价格时再以10递增，直到猜出准确价格。这是一种算法，参与者猜了11次 猜出了实际价格

但如果答题者是一名程序员的话，那可不会用上面的方法，太low了。
程序员：500
主持人：低了
程序员：750
主持人：高了
程序员：620
主持人：低了
程序员：680
主持人：高了
程序员：650
主持人：高了
程序员：630
主持人：低了
程序员：640
主持人：恭喜你 答对了
程序员用的算法逻辑就是二分法，首先得出中间价500，如果比500高 那么再取500-1000的中间值，依次类推 直到最后的结果，只用了7步。
此算法可以运用于生活各个领域里面，生生处处有算法啊。 附上此游戏的源码

1. // 算法之二分法.cpp : 定义控制台应用程序的入口点。
   
2. //
   
3. 
   
4. #include "stdafx.h"
   
5. 
   
6. 
   
7. int _tmain(int argc, _TCHAR* argv[])
   
8. {
   
9. 
   
10.         int price = 0;
    
11.         int guessPrice = 0;
    
12. 
    
13.         printf("请输入商品的价格");
    
14.         scanf_s("%d",&price);
    
15.         system("cls");
    
16.         while (price!=guessPrice)
    
17.         {
    
18.                 printf("请输入试猜的价格:\n");
    
19.                 scanf_s("%d",&guessPrice);
    
20.                 if(price>guessPrice)
    
21.                 {
    
22.                         printf("猜低了\n");
    
23.                 }
    
24.                 else if(price<guessPrice)
    
25.                 {
    
26.                         printf("猜高了\n");
    
27.                 }
    
28.                 else
    
29.                 {
    
30.                         printf("猜对了\n");
    
31.                 }
    
32.         }
    
33.         system("pause");
    
34.         return 0;
    
35. }
    
36. 
    

复制代码