今天花了一下午的時間學習李老師新寫的智能猜數字程序,從執行效率上來看,在取值范圍比我做的大1萬倍的情況下,計算次數幾乎相同。所以我學習的重點集中在,算法是如何優化的。
首先回憶我自己的程序算法,是先創造一個結果全集(在取四位的情況下全集是1萬),在根據提示逐步篩選出正確的答案。但是這種算法在全集總數巨大的時候(李老師的程序取8位,全集為1億),那么程序的執行效率必然是大打折扣的。
智能猜數字游戲中最關鍵的就是計算機產生假設的那個函數,李老師的相關函數是
char * generate_new_answer (RECORD * ar, OPTIONS * opt)
我的疑問也主要集中在這部分,先說說我看明白的部分。
上面這一段是當還未進行猜測的時候觸發的一段函數。
5-9行是計算一下整個集合的數量,10選8的結果應該是10的8次方,1億。其中變量i在之前靜態聲明。
11-15行是生成第一次和第二次要猜測的answer。至于為什么要固定第一次和第二次的猜測答案。在我的程序中也有類似的設定,我的全集是(0000-9999)規定第一次猜測9876,第二次猜測2345。這樣做的好處是可以最大限度的加速猜測速度。如果第一次猜0000,而第二次猜1111的話,排除掉的結果比較少。
最后函數返回第一次的猜測結果。
for (; i; i--)

{

}
上面這個循環是當有了猜測數后,開始進行排除工作,最后產生一個有效的新的答案。i是集合中剩余結果的數量。
上面這段是進入循環之后的第一段代碼,
1行,猜測次數加1.
2-13行從注釋來看這是生成一個新的答案系列,
可是我只能看出這是對本次對比篩選的答案的檢查,看是否超出全集中的范圍。
上面這段是進入循環之后的第二段代碼,
將這個結果和前幾次的猜測做“猜數字判斷”,如果和之前的猜測結果不完全相同的,則跳出。
這一點不太明白。首先為什么要和之前的結果做比對。之前的結果是猜數和答案的關系。而新猜數和舊猜數之間的關系能說明什么呢?這不是慣常的思路。
當上一個循環沒有break時,也就是(當前數字和之前猜數)的比對結果和(之前猜數和答案)的比對結果都不一樣的時候。這該數字為新的猜數。返回。
首先回憶我自己的程序算法,是先創造一個結果全集(在取四位的情況下全集是1萬),在根據提示逐步篩選出正確的答案。但是這種算法在全集總數巨大的時候(李老師的程序取8位,全集為1億),那么程序的執行效率必然是大打折扣的。
智能猜數字游戲中最關鍵的就是計算機產生假設的那個函數,李老師的相關函數是
char * generate_new_answer (RECORD * ar, OPTIONS * opt)我的疑問也主要集中在這部分,先說說我看明白的部分。
1
if (!ar->count)
2
{ // First step work
3
// i = size = (unsigned long) pow (opt->total_num, opt->select_num)+2;
4
5
for (i=0, size = 1; i<opt->select_num;i++)//計算集合的總數
6
{
7
size *= opt->total_num;
8
}
9
i = size = size + 2;
10
11
for (j=0; j<opt->select_num; j++)
12
{
13
ar->answer[ar->count ][opt->select_num-j-1] = opt->resource [(opt->total_num*10-j-1)%opt->total_num];
14
ar->answer[ar->count+1][j] = opt->resource [opt->total_num-1];
15
}
16
return (ar->answer[ar->count]);
17
}
if (!ar->count)2

{ // First step work3
// i = size = (unsigned long) pow (opt->total_num, opt->select_num)+2;4
5
for (i=0, size = 1; i<opt->select_num;i++)//計算集合的總數 6

{7
size *= opt->total_num;8
}9
i = size = size + 2; 10
11
for (j=0; j<opt->select_num; j++)12

{13
ar->answer[ar->count ][opt->select_num-j-1] = opt->resource [(opt->total_num*10-j-1)%opt->total_num];14
ar->answer[ar->count+1][j] = opt->resource [opt->total_num-1];15
}16
return (ar->answer[ar->count]);17
}上面這一段是當還未進行猜測的時候觸發的一段函數。
5-9行是計算一下整個集合的數量,10選8的結果應該是10的8次方,1億。其中變量i在之前靜態聲明。
11-15行是生成第一次和第二次要猜測的answer。至于為什么要固定第一次和第二次的猜測答案。在我的程序中也有類似的設定,我的全集是(0000-9999)規定第一次猜測9876,第二次猜測2345。這樣做的好處是可以最大限度的加速猜測速度。如果第一次猜0000,而第二次猜1111的話,排除掉的結果比較少。
最后函數返回第一次的猜測結果。
for (; i; i--)
{
}上面這個循環是當有了猜測數后,開始進行排除工作,最后產生一個有效的新的答案。i是集合中剩余結果的數量。
1
ar->answer[ar->count][0] ++;
2
for (j=0; j<opt->select_num; j++)
3
{
4
if (ar->answer[ar->count][j] > opt->resource [opt->total_num-1])
5
{
6
ar->answer[ar->count][j] = opt->resource [0];
7
ar->answer[ar->count][j+1]++;
8
ar->answer[ar->count][opt->select_num] = 0;
9
} else
10
{
11
break;
12
}
13
}
ar->answer[ar->count][0] ++;2
for (j=0; j<opt->select_num; j++)3

{4
if (ar->answer[ar->count][j] > opt->resource [opt->total_num-1])5

{6
ar->answer[ar->count][j] = opt->resource [0];7
ar->answer[ar->count][j+1]++;8
ar->answer[ar->count][opt->select_num] = 0;9
} else10

{11
break;12
}13
}上面這段是進入循環之后的第一段代碼,
1行,猜測次數加1.
2-13行從注釋來看這是生成一個新的答案系列,
可是我只能看出這是對本次對比篩選的答案的檢查,看是否超出全集中的范圍。1
for (j=0; j<ar->count; j++)
2
{ // compare with all records
3
give_answer_tip (tip, ar->answer[j], ar->answer[ar->count], opt->select_num);
4
if (tip[0] != ar->tip[j][0] || tip[1] != ar->tip[j][1])
5
{
6
break;
7
}
8
}
for (j=0; j<ar->count; j++)2

{ // compare with all records3
give_answer_tip (tip, ar->answer[j], ar->answer[ar->count], opt->select_num);4
if (tip[0] != ar->tip[j][0] || tip[1] != ar->tip[j][1])5

{6
break;7
}8
}上面這段是進入循環之后的第二段代碼,
將這個結果和前幾次的猜測做“猜數字判斷”,如果和之前的猜測結果不完全相同的,則跳出。
這一點不太明白。首先為什么要和之前的結果做比對。之前的結果是猜數和答案的關系。而新猜數和舊猜數之間的關系能說明什么呢?這不是慣常的思路。
1
if (j == ar->count)
2
{ // pass all records check, record new answer
3
memcpy (ar->answer[ar->count+1], ar->answer[ar->count], opt->select_num);
4
return (ar->answer[ar->count]);
5
}
if (j == ar->count)2

{ // pass all records check, record new answer3
memcpy (ar->answer[ar->count+1], ar->answer[ar->count], opt->select_num);4
return (ar->answer[ar->count]);5
}當上一個循環沒有break時,也就是(當前數字和之前猜數)的比對結果和(之前猜數和答案)的比對結果都不一樣的時候。這該數字為新的猜數。返回。


