2010年4月15日 星期四

猜數字遊戲 (電腦猜人)

前幾天午睡時突然被告知要參加公司內部的程式設計比賽,題目是用C寫一支文字模式的4位數字猜數字遊戲,由使用者來猜電腦的數字。在上星期時其實就已經有公佈了,但我沒有注意到所以是臨時加入,還好這是個簡單的題目,不用花多少時間就可以寫出來。

規則:

- 這是一對一比賽,雙方各選擇一4位數字,不讓對方知道。
- 4位數字由數字0至9組成,每位數不得重複。
- 雙方輪流猜對方的數字,直到一方猜中為止。
- A方猜B方的數字後,B方根據A方的猜測回答幾A幾B。
- 一個A表示猜中一個數字且位置正確,一個B表示猜中一個數字但位置不正確。
- 當一方猜中4A0B時即表示猜中對方全部4個數字且位置正確,贏得比賽。
- 例:B的謎底是4208,底下箭頭左測是A的猜測,箭頭右測是B的回答。
   1234 ==> 1A1B
   5678 ==> 1A0B
   2406 ==> 1A2B
   ...
   4208 ==> 4A0B

;

寫個程式讓玩家來猜電腦的數字不難,不過我從來沒有寫過讓電腦來猜玩家數字的版本,所以花了點時間想想怎麼寫。

研究後歸納出二個點。

1, 使用窮舉法將所有可能數字組合列出。
2, 每次猜測後根據結果排除不可能是答案的組合,重複這個動作直到猜中答案為止。

第1點只是實作問題,第2點概念也很簡單,但要過濾不是答案的組合根據的是什麼?乍看之下沒什麼頭緒,不過想通之後就非常簡單了。

它的基本原理如下:假如謎底是4561,如果猜1524則會得到1A2B。從相反的角度來看,如果謎底是1524,則猜4561時也會得到1A2B的回答。

利用這個方法,每一次猜測一個數字X後,再以這個數字當作答案,來和所有剩下來的候選答案作比對,如果得到的結果(幾A幾B)和數字X是一樣的話,就把這個數字保留下來繼續作為候選答案,否則就過把這個數字過濾掉。下一把,繼續從候選答案裡選一個出來猜,重複上面的動作,直到猜中為止。

;

C++ STL的algorithm裡有個叫作next_permutation的函數,可以用來生成排列。
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  sort(myints, myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while (next_permutation(myints, myints+3));

  return 0;
}
執行結果如下:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
不過因為我們是要產生4位數字的組合,而這4個數字是由0~9裡選出來的,也就是要作m取n的排列,但是next_permutation只能作n位數排列,所以需要另想辨法。

稍微設計一下之後,把這個操作分為二部份。第一部份首先選擇4位數數組,例如1234或2345等,接著再以next_permutation產生這些數組的所有排列,最後把所有這些數組的排列合拼,就能得到所有可能答案的排列組合。

那麼要怎麼挑出數組?也就是作出10取4的組合。

首先我把每一個數字當作一個位元來看,0x3ff這個數由十個位元1組成,可以表示為0~9十個數字全選。我只需要簡單跑個迴圈,從0開始找到0x3ff,如果找到的數是包含4個為1的位元的話,那就表示找到了一個我要的數組,接著把對應位元為1的位置轉換為數字就可以了。然後再拿它來透過next_permutation產生所有排列。

例:

9876543210
----------
0000001111 ==> 3210
0000010111 ==> 4210
1001001100 ==> 9632
依此類推..

如此就能產生所有可能的排列組合,完成第一部份的工作。至於第二部份就沒什麼好說的了,重點是在於一開始如何想通怎麼作,實作就更簡單了。

8 則留言:

  1. 這個不錯,寫一個互猜的來和人腦比看看吧

    回覆刪除
  2. 用以上的演算寫了一支小程式請電腦來猜4位數字,平均4~6把就能猜中答案

    回覆刪除
  3. 那個,你舉的例子:
    假如謎底是4561,如果猜1524則會得到1A1B

    應該是1A2B才對,A是5,然後2B是1跟4

    回覆刪除
  4. 哎呀,這是個BUG,被眼尖的你發現了!

    回覆刪除
  5. 我是大一生 因為我們要利用C語言寫這份作業 請問可以提供我方向或是做法

    回覆刪除
  6. 我大一時老師也出過這樣的作業, 不過那時我還不會程式, 是用抄的...

    這篇文章寫的是電腦猜人的原理, 只差把它轉變成code, 語法的部份書上或網路上有許多資料

    如果不是電腦猜人的話更簡單, 主要程式部份是電腦產生一個4位數字, 這可以用一個array或字串來存, 用rand來產生, 怎麼產生一個不重複的數字. 再來是判斷幾A幾B, 主要是要透過二層迴圈一個一個字去比對. 這需要你們自行研究一下, 弄出來後相信對你們的理解會有很大的進步幫助

    回覆刪除
  7. 我是用appinventor2寫,請問大大如果今天我輸入:0000、1111、2222......0001、0002、0003......以上這些來一ㄍㄧㄍ猜答案,要如何避免這ㄍ問題呢?

    回覆刪除
  8. 你的意思是要怎麼排除不合法的輸入嗎?如果是的話,最簡單的方式是用兩個迴圈對輸入的資料兩兩比對

    回覆刪除

Related Posts Plugin for WordPress, Blogger...