無聊PO個猜數字程式(C++,電腦猜)~~ [論壇 - Ubuntu 程式設計]


正在瀏覽:   1 名遊客


 到底部   前一個主題   下一個主題  [無發表權] 請登錄或者註冊



nobody
無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
  1 #include <iostream>
  2 #include <iomanip>
  3 #include <vector>
  4 #include <string>
  5 #include <iterator>
  6 #include <algorithm>
  7 #include <stdexcept>
  8 #include <ctime>
  9
 10 using namespace std;
 11 //------------------------------------------------------------------------------
 12 class ItemAB
 13 {
 14 public:
 15     ItemAB( unsigned int correctCnt, unsigned int wrongPosCnt )
 16         : A(correctCnt), B(wrongPosCnt)
 17             {};
 18     unsigned int A, B;
 19
 20     bool operator==( const ItemAB & rhs ) { return A == rhs.A && B == rhs.B; };
 21     bool operator!=( const ItemAB & rhs ) { return A != rhs.A || B != rhs.B; };
 22 };
 23 ItemAB CheckAB( const vector<char> & guess, const vector<char> & quiz )
 24 {
 25     typedef vector<char>::size_type size_type;
 26     ItemAB result( 0, 0 );
 27     for( size_type i = 0; i < guess.size(); ++i )
 28         if( find( quiz.begin(), quiz.end(), guess[i] ) != quiz.end() )
 29             guess[i] == quiz[i] ? ++result.A : ++result.B;
 30     return result;
 31 }
 32 //------------------------------------------------------------------------------
 33 class HistoryItem
 34 {
 35 public:
 36     HistoryItem( const vector<char> & guessItem,
 37                   unsigned int correctCnt,
 38                    unsigned int wrongPosCnt )
 39         : guess(guessItem), result(correctCnt, wrongPosCnt)
 40             {};
 41     HistoryItem( const vector<char> & guessItem,
 42                   const ItemAB & itemAB )
 43         : guess(guessItem), result(itemAB)
 44             {};
 45     vector<char> guess;
 46     ItemAB result;
 47 };
 48 //------------------------------------------------------------------------------
 49 class GuessAI
 50 {
 51 public:
 52     GuessAI( const vector<char> & charSet, unsigned int nChars )
 53         : _n_chars(nChars), _begin_set(charSet)
 54             {
 55                 random_shuffle( _begin_set.begin(), _begin_set.end() );
 56                 _guess_set = _begin_set;
 57             };
 58
 59     vector<char> guess() const
 60         { return vector<char>( _guess_set.begin(), _guess_set.begin() + _n_chars ); };
 61
 62     void history( const HistoryItem & htyItem )
 63         {
 64             if( htyItem.result.A == _n_chars )
 65                 return; // bingo...
 66             
 67             const unsigned int totalAB = htyItem.result.A + htyItem.result.B;
 68             if( totalAB == 0 )
 69             {   // remove impassible chars...
 70                 _guess_set.erase( _guess_set.begin(), _guess_set.begin() + _n_chars );
 71                 _begin_set = _guess_set;
 72                 return;
 73             }
 74             if( totalAB == _n_chars )
 75             {   // remove impassible chars...
 76                 _guess_set.erase( _guess_set.begin() + _n_chars, _guess_set.end() );
 77                 _begin_set = _guess_set;
 78             }
 79             _history.push_back( htyItem );
 80             thinkNext();
 81         };
 82 private:
 83     bool isPassibleQuiz()
 84         {
 85             typedef vector<HistoryItem>::const_iterator cIter;
 86             for( cIter iter = _history.begin(); iter != _history.end(); ++iter )
 87                 if( CheckAB( (*iter).guess, guess() ) != (*iter).result )
 88                     return false;
 89             return true;
 90         };
 91     void thinkNext()
 92         {
 93             do {
 94                 prev_permutation( _guess_set.rbegin(), _guess_set.rend() );
 95                 if( _guess_set == _begin_set )
 96                     throw logic_error("* out of passible set, are you kidding me?!");
 97             } while( !isPassibleQuiz() );
 98         };
 99
100     unsigned int _n_chars;
101     vector<char> _begin_set;
102     vector<char> _guess_set;
103     vector<HistoryItem> _history;
104 };
105 //------------------------------------------------------------------------------
106 template<typename _Ty>
107 inline void show( const _Ty & char_set )
108 {
109     typedef typename _Ty::value_type value_type;
110     copy( char_set.begin(), char_set.end(), ostream_iterator<value_type>( cout, " " ) );
111 }
112 //------------------------------------------------------------------------------
113 int main()
114 {
115     srand( time(0) );
116     try
117     {
118         string char_set( "0123456789" );
119         string quiz_str( "7319" );
120
121         cout << endl << " chars: "; show( char_set ); cout << ", input quiz: " << flush;
122         cin >> quiz_str;
123         // TODO: check quiz_str's correctness ...
124         vector<char> quiz( quiz_str.begin(), quiz_str.end() );
125         cout << endl << " quiz: "; show( quiz ); cout << endl;
126
127         clock_t clk_start = clock();
128         GuessAI guessAI( vector<char>( char_set.begin(), char_set.end() ), quiz.size() );
129         for( int i = 1, max_cnts = 20; i <= max_cnts; ++i )
130         {
131             vector<char> guess( guessAI.guess() );
132             cout << setw(4) << i << ".  "; show( guess );
133             ItemAB result( CheckAB( guess, quiz ) );
134             cout << " ... " << result.A << " A " << result.B << " B" << endl;
135             guessAI.history( HistoryItem( guess, result ) );
136             if( result.A == quiz.size() )
137                 break;
138             if( i >= max_cnts )
139                 cout << " * no chance to guess...(max:" << max_cnts << ")" << endl;
140         }
141         double spent_time = double( clock() - clk_start ) / CLOCKS_PER_SEC;
142         cout << endl << " spent time: " 
143              << setprecision(3) << spent_time << " sec(s)" << endl;
144     }
145     catch( const exception & ex )
146     {
147         cout << endl << "exception: " << ex.what() << endl;
148     }
149     catch(...) { cout << endl << "* unknown exception *" << endl; }
150     cout << endl;
151     return 0;
152 }
153 //------------------------------------------------------------------------------
154

2009/6/28 19:24 | 0847e ea5bb 7bab3 ba081
應用擴展 工具箱
Mozzenior
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:Mozzenior
Perl 版。趕睡覺時間,所以亂寫一通。不過可以跑耶…XD
==

1 #!/us/bin/perl
2 use strict;
3 use warnings;
4
5 my $possibles = InitPossibles();
6 while (1) {
7 my $guess = Guess($possibles);
8
9 print "我猜是 $guess,您說呢?\n";
10
11 my ($a, $b) = ReadCheck();
12 if (4 == $a and 0 == $b) {
13 print "我猜中啦\n";
14 last;
15 }
16
17 UpdatePossibles($possibles, $guess, $a, $b);
18
19 if (0 == @$possibles) {
20 print "投降\n";
21 last;
22 }
23 }
24
25 sub InitPossibles
26 {
27 my $grep = sub {
28 for (my $i = 0 ; $i < 4 ; ++$i) {
29 for (my $j = $i + 1 ; $j < 4 ; ++$j) {
30 return 0 if substr($_, $i, 1) eq substr($_, $j, 1);
31 }
32 }
33 return 1;
34 };
35 return [grep { &$grep($_) } ('0000'..'9999')];
36 }
37
38 sub Guess
39 {
40 my $possibles = shift;
41 return $possibles->[int rand @$possibles];
42 }
43
44 sub ReadCheck
45 {
46 do {
47 print "給個提示吧: ";
48 my $check = ;
49 chomp $check;
50 return (substr($check, 0, 1), substr($check, 2, 1)) if
51 $check =~ /^(\d)(?:A|a)(\d)(?:B|b)$/ and
52 4 >= $1 + $2;
53 } while (1);
54 }
55
56 sub CountA
57 {
58 my $correct = shift;
59 my $guess = shift;
60 my $a = 0;
61
62 for (my $i = 0 ; $i < 4 ; ++$i) {
63 ++$a if substr($correct, $i, 1) eq substr($guess, $i, 1);
64 }
65 return $a;
66 }
67
68 sub CountB
69 {
70 my $correct = shift;
71 my $guess = shift;
72 my $b = 0;
73
74 for (my $i = 0 ; $i < 4 ; ++$i) {
75 for (my $j = 0 ; $j < 4 ; ++$j) {
76 next if $i == $j;
77 ++$b if substr($correct, $i, 1) eq substr($guess, $j, 1);
78 }
79 }
80 return $b;
81 }
82
83 sub UpdatePossibles
84 {
85 my $possibles = shift;
86 my $guess = shift;
87 my $a = shift;
88 my $b = shift;
89
90 @$possibles = grep {
91 my $j = ($a == CountA($_, $guess) and $b == CountB($_, $guess));
92 } @$possibles;
93 }

2009/6/29 0:48 | 75878 66430 9b1e1 2165b
應用擴展 工具箱
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
會員五級
註冊日期:
2008/10/7 21:19
所屬群組:
已註冊使用者
等級: 36
HP : 0 / 896
MP : 661 / 32794
EXP: 85
離線
嗚哇,好多OO
還在適應OO中呢,比較熟悉C...

2009/6/29 1:07
I′m UGP
應用擴展 工具箱
nobody
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
...底下我針對語法作一些效率上的修改(有標示2009-06-29的function)
~大致是減少對begin(),end(),size()的呼叫次數...
~另外就是GuessAI::isPassibleQuiz()裡每次呼叫GuessAI::guess()的問題...^^"
(...呵呵 快變教學篇了,但不保證作法是對的喔,畢竟還是沒有工作的菜鳥..(泣)...@#$%...(自言自語))
.../nobody in Taiwan.(fin.=n=)

...話說要怎麼PO成Mozzenior大大那樣?!...我是直接把cpp轉成html,再貼上來地...(虛)...

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <vector>
  4 #include <string>
  5 #include <iterator>
  6 #include <algorithm>
  7 #include <stdexcept>
  8 #include <ctime>
  9
 10 using namespace std;
 11 //------------------------------------------------------------------------------
 12 class ItemAB
 13 {
 14 public:
 15     ItemAB( unsigned int correctCnt, unsigned int wrongPosCnt )
 16         : A(correctCnt), B(wrongPosCnt)
 17             {};
 18     unsigned int A, B;
 19
 20     bool operator==( const ItemAB & rhs ) { return A == rhs.A && B == rhs.B; };
 21     bool operator!=( const ItemAB & rhs ) { return A != rhs.A || B != rhs.B; };
 22 };
 23 ItemAB CheckAB( const vector<char> & guess, const vector<char> & quiz ) // 2009-06-29
 24 {
 25     typedef vector<char>::size_type size_type;
 26     typedef vector<char>::const_iterator cIter;
 27     ItemAB result( 0, 0 );
 28     cIter quiz_begin( quiz.begin() ), quiz_end( quiz.end() );
 29     for( size_type i = 0, size = guess.size(); i < size; ++i )
 30         if( find( quiz_begin, quiz_end, guess[i] ) != quiz_end )
 31             guess[i] == quiz[i] ? ++result.A : ++result.B;
 32     return result;
 33 }
 34 //------------------------------------------------------------------------------
 35 class HistoryItem
 36 {
 37 public:
 38     HistoryItem( const vector<char> & guessItem,
 39                   unsigned int correctCnt,
 40                    unsigned int wrongPosCnt )
 41         : guess(guessItem), result(correctCnt, wrongPosCnt)
 42             {};
 43     HistoryItem( const vector<char> & guessItem,
 44                   const ItemAB & itemAB )
 45         : guess(guessItem), result(itemAB)
 46             {};
 47     vector<char> guess;
 48     ItemAB result;
 49 };
 50 //------------------------------------------------------------------------------
 51 class GuessAI
 52 {
 53 public:
 54     GuessAI( const vector<char> & charSet, unsigned int nChars )
 55         : _n_chars(nChars), _begin_set(charSet)
 56             {
 57                 random_shuffle( _begin_set.begin(), _begin_set.end() );
 58                 _guess_set = _begin_set;
 59             };
 60
 61     vector<char> guess() const // 2009-06-29
 62         {
 63             vector<char>::const_iterator guess_begin( _guess_set.begin() );
 64             return vector<char>( guess_begin, guess_begin + _n_chars );
 65         };
 66
 67     void history( const HistoryItem & htyItem ) // 2009-06-29
 68         {
 69             if( htyItem.result.A == _n_chars )
 70                 return; // bingo...
 71             
 72             const unsigned int totalAB = htyItem.result.A + htyItem.result.B;
 73             if( totalAB == 0 )
 74             {   // remove impassible chars...
 75                 vector<char>::iterator guess_begin( _guess_set.begin() );
 76                 _guess_set.erase( guess_begin, guess_begin + _n_chars );
 77                 _begin_set = _guess_set;
 78                 return;
 79             }
 80             if( totalAB == _n_chars )
 81             {   // remove impassible chars...
 82                 _guess_set.erase( _guess_set.begin() + _n_chars, _guess_set.end() );
 83                 _begin_set = _guess_set;
 84             }
 85             _history.push_back( htyItem );
 86             thinkNext();
 87         };
 88 private:
 89     bool isPassibleQuiz( const vector<char> & quiz ) // 2009-06-29
 90         {
 91             typedef vector<HistoryItem>::const_iterator cIter;
 92             for( cIter iter( _history.begin() ), end( _history.end() ); iter != end; ++iter )
 93                 if( CheckAB( (*iter).guess, quiz ) != (*iter).result )
 94                     return false;
 95             return true;
 96         };
 97     void thinkNext() // 2009-06-29
 98         {
 99             do {
100                 prev_permutation( _guess_set.rbegin(), _guess_set.rend() );
101                 if( _guess_set == _begin_set )
102                     throw logic_error("* out of passible set, are you kidding me?!");
103             } while( !isPassibleQuiz( guess() ) );
104         };
105
106     unsigned int _n_chars;
107     vector<char> _begin_set;
108     vector<char> _guess_set;
109     vector<HistoryItem> _history;
110 };
111 //------------------------------------------------------------------------------
112 template<typename _Ty>
113 inline void show( const _Ty & char_set )
114 {
115     typedef typename _Ty::value_type value_type;
116     copy( char_set.begin(), char_set.end(), ostream_iterator<value_type>( cout, " " ) );
117 }
118 //------------------------------------------------------------------------------
119 int main()
120 {
121     srand( time(0) );
122     try
123     {
124         string char_set( "0123456789" );
125         string quiz_str( "7319" );
126
127         cout << endl << " chars: "; show( char_set ); cout << ", input quiz: " << flush;
128         cin >> quiz_str;
129         // TODO: check quiz_str's correctness ...
130         vector<char> quiz( quiz_str.begin(), quiz_str.end() );
131         cout << endl << " quiz: "; show( quiz ); cout << endl;
132
133         clock_t clk_start = clock();
134         GuessAI guessAI( vector<char>( char_set.begin(), char_set.end() ), quiz.size() );
135         for( int i = 1, max_cnts = 20; i <= max_cnts; ++i )
136         {
137             vector<char> guess( guessAI.guess() );
138             cout << setw(4) << i << ".  "; show( guess );
139             ItemAB result( CheckAB( guess, quiz ) );
140             cout << " ... " << result.A << " A " << result.B << " B" << endl;
141             guessAI.history( HistoryItem( guess, result ) );
142             if( result.A == quiz.size() )
143                 break;
144             if( i >= max_cnts )
145                 cout << " * no chance to guess...(max:" << max_cnts << ")" << endl;
146         }
147         double spent_time = double( clock() - clk_start ) / CLOCKS_PER_SEC;
148         cout << endl << " spent time: " 
149              << setprecision(3) << spent_time << " sec(s)" << endl;
150     }
151     catch( const exception & ex )
152     {
153         cout << endl << "exception: " << ex.what() << endl;
154     }
155     catch(...) { cout << endl << "* unknown exception *" << endl; }
156     cout << endl;
157     return 0;
158 }
159 //------------------------------------------------------------------------------
160

2009/6/29 15:15 | 2a9cf 04316 bef90 cbe00
應用擴展 工具箱
nobody
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
...不過我這程式在ubuntu-64bit跑蠻快的,
但是在XP-32bit下就慢很多,
有沒有大大可以解釋一下?!
=XP=
VC++2008Express
=ubuntu=
使用內建 specs。
目的:x86_64-linux-gnu
配置為:../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
執行緒模型:posix
gcc 版本 4.2.4 (Ubuntu 4.2.4-1ubuntu4)

2009/6/29 15:25 | 2a9cf 04316 bef90 cbe00
應用擴展 工具箱
Mozzenior
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:Mozzenior
我是在 gnome terminal 下,用 vim 編輯好,以 set nu 開啟
行號後,拷貝貼上的。使用了 HTML 標籤 <pre> 和 </pre>。不
過缺點是所有在大於小於符號之間的文字都被視作 HTML 標籤了。所
以 <STDIN> 就無法正確顯示。

2009/6/29 19:35 | 75878 66430 9b1e1 2165b
應用擴展 工具箱
Mozzenior
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:Mozzenior
認為執行速度不佳的話,用 profiler 看看哪個函數吃得時間最
多,會比自己猜測來得好。作最佳化時,要把時間花在刀口上~

2009/6/29 19:37 | 75878 66430 9b1e1 2165b
應用擴展 工具箱
nobody
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
Mozzenior 寫到:
我是在 gnome terminal 下,用 vim 編輯好,以 set nu 開啟
行號後,拷貝貼上的。使用了 HTML 標籤
。不
過缺點是所有在大於小於符號之間的文字都被視作 HTML 標籤了。所
就無法正確顯示。

喔~~我是用Gvim打開語法效果,
之後將cpp轉成html格式,
再把...貼上來的...(汗)
優點就是有色彩顯示
而且#include可正常顯示
(^^^但用預覽觀看後必須在將內容重貼回去,不然第二次預覽就無法正常,原因不明^^^)
不過要是能合併你的方法應該更好看...^i^)

2009/6/29 20:35 | a3a79 ebc24 e1580 3b4b6
應用擴展 工具箱
nobody
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
Mozzenior 寫到:
認為執行速度不佳的話,用 profiler 看看哪個函數吃得時間最
多,會比自己猜測來得好。作最佳化時,要把時間花在刀口上~

有聽過但沒用過profiler...(虛)
...
不過問題是 同樣source code在不同的OS和compiler下
最後執行效率居然有這樣的差別...
到底該說linux比window好,還是g++比vc++好...??
(不曉得有沒有人作過比較...^^|||)

2009/6/29 20:47 | a3a79 ebc24 e1580 3b4b6
應用擴展 工具箱
nobody
回覆: 無聊PO個猜數字程式(C++,電腦猜)~~
Anon:nobody
1 #include <iostream>
2 using namespace std;
3 
4 int main()
5 {
6     cout << "Hello World!" << endl;
7     return 0;
8 }

喔~~我會用了!! *v* ...(汗)

2009/6/29 21:59 | a3a79 ebc24 e1580 3b4b6
應用擴展 工具箱


 [無發表權] 請登錄或者註冊


可以查看帖子.
不可發帖.
不可回覆.
不可編輯自己的帖子.
不可刪除自己的帖子.
不可發起投票調查.
不可在投票調查中投票.
不可上傳附件.
不可不經審核直接發帖.