Just My Life & My Work

猜數字 (Guess Number)

碩一已經修過高演,不過還是要寫作業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次才猜中,機率可能比中樂透還要低,有興趣的人可以算算看:P提示:16!=20,922,789,888,000,而且要從0開始循序往15猜,或恰好反方向15往0猜

隨意留個言吧:)~

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

標籤雲

%d 位部落客按了讚: