碩一已經修過高演，不過還是要寫作業XD～因為被老師委任為助教，而作業多為開放式題目，有標準答案的部份我要自己生出來，還好高演的作業都相當有趣，在作業剛發佈出來的時候就想來寫程式，哈～不過人性本惰(誤)，到要改作業的時候才趕緊寫出來……
題目是大家都會玩的「猜數字 (Guess Number)」，所需要用到的演算法也相當簡單，流程是這樣：設計一個「亂猜法」，若已知(0<x< n-1)，則就用亂數產生器產生一個介於0 到 n-1之間的數k，第一次就猜k，接下來，若數字x的範圍縮小在p到q之間，則亂數的範圍也跟著縮小在p到q之間去做猜測。
為了方便測試起見，範圍0-15共16個數字，分別對0-15個別猜測10000次，所以一共要猜160000次。不過為了看見效果，我個別猜測1000000次，以下是程式碼：
/**
Theme: Guess Number
Compiler: Dev C++ 4.9.9.2
Date: 100/11/01
Author: HappyMan
Blog: https://cg2010studio.wordpress.com/
*/
#include<iostream>
using namespace std;
const int CASE=1000000;
const int NUMBER=16;
int top;
int buttom;
int target;
int match;
int local_count;
int global_count[NUMBER+1];
int total_guess;
double average_guess;
int main(){
srand(time(NULL));
for(int i=0; i<NUMBER-1; i++)
global_count[i]=0;
for(int casex=1; casex<=CASE; casex++){
for(int targetx=0; targetx<NUMBER; targetx++){
top=NUMBER-1;
buttom=0;
//target=rand()%NUMBER;//隨意目標
target=targetx;//特定目標
//cout<<"targett: "<<target<<endl;
local_count=0;
while(true){
//match=rand()%(top-buttom+1)+buttom;//任意猜法
match=(top+buttom)/2;//最佳猜法
//cout<<"match: "<<match<<endl;
local_count++;
//cout<<"top: "<<top<<", "<<"buttom: "<<buttom<<endl;
if(target==match)
break;
if(target>match){
buttom=match+1;
}
if(target<match){
top=match-1;
}
}
//cout<<"local_count: "<<local_count<<endl;
global_count[local_count]++;
}
}
for(int i=1; i<=NUMBER; i++)
total_guess+=i*global_count[i];
average_guess=(double)total_guess/(CASE*NUMBER);
cout<<"CASE*NUMBER: "<<CASE*NUMBER<<endl;
cout<<"total_guess: "<<total_guess<<endl;
cout<<"average_guess: "<<average_guess<<endl;
for(int i=1; i<=NUMBER; i++)
cout<<"i: "<<i<<" = "<<global_count[i]<<endl;
system("pause");
return 0;
}
我用四個模式去跑：//隨意目標//任意猜法、//特定目標//任意猜法、//特定目標//最佳猜法、//隨意目標//最佳猜法。
//隨意目標//任意猜法結果：
CASE*NUMBER: 16000000 total_guess: 66956778 average_guess: 4.1848 i: 1 = 1001344 i: 2 = 1871983 i: 3 = 2919733 i: 4 = 3485361 i: 5 = 3096905 i: 6 = 2059363 i: 7 = 1030221 i: 8 = 392174 i: 9 = 113265 i: 10 = 25005 i: 11 = 4065 i: 12 = 523 i: 13 = 55 i: 14 = 3 i: 15 = 0 i: 16 = 0
//特定目標//任意猜法結果：
CASE*NUMBER: 16000000 total_guess: 66910574 average_guess: 4.18191 i: 1 = 1003117 i: 2 = 1877342 i: 3 = 2920539 i: 4 = 3484933 i: 5 = 3097290 i: 6 = 2057947 i: 7 = 1028801 i: 8 = 389154 i: 9 = 111625 i: 10 = 24531 i: 11 = 4178 i: 12 = 501 i: 13 = 40 i: 14 = 2 i: 15 = 0 i: 16 = 0
//特定目標//最佳猜法結果：
CASE*NUMBER: 16000000 total_guess: 54000000 average_guess: 3.375 i: 1 = 1000000 i: 2 = 2000000 i: 3 = 4000000 i: 4 = 8000000 i: 5 = 1000000 i: 6 = 0 i: 7 = 0 i: 8 = 0 i: 9 = 0 i: 10 = 0 i: 11 = 0 i: 12 = 0 i: 13 = 0 i: 14 = 0 i: 15 = 0 i: 16 = 0
//隨意目標//最佳猜法結果：
CASE*NUMBER: 16000000 total_guess: 53999750 average_guess: 3.37498 i: 1 = 999858 i: 2 = 2000275 i: 3 = 3999963 i: 4 = 8000067 i: 5 = 999837 i: 6 = 0 i: 7 = 0 i: 8 = 0 i: 9 = 0 i: 10 = 0 i: 11 = 0 i: 12 = 0 i: 13 = 0 i: 14 = 0 i: 15 = 0 i: 16 = 0
可以發現不管是隨意目標或特定目標，任意猜法的平均猜測數約為4.18；同樣的不管是隨意目標或特定目標，最佳猜法的平均猜測數約為3.375。
試著去推導期望值，可以看遊戲樹，期望值：T(16)/16 = (1*1+2*2+3*4+4*8+5*1)/16 =3.375，其中T(n)= 遊戲樹的外部路徑長度合。
結論：若是聰明人玩「猜數字」遊戲，一定會從區間一半的那個數字開始猜起，就算運氣很差還是可以在第5次猜到答案！若給很笨的電腦去猜，說真的～看到最差的結果並不是第16次才猜中，實驗結果是最差是第14次才猜中，這表示想要猜到第16次才猜中，機率可能比中樂透還要低，有興趣的人可以算算看：Ｐ提示：16!=20,922,789,888,000，而且要從0開始循序往15猜，或恰好反方向15往0猜。
逍遙文工作室 
隨意留個言吧：）～