本帖最后由 523066680 于 2017-09-08 22:45 编辑
回复 30# rubyish
是一样的。
在用指针数组/数组指针的时候有 char (*str)和 char *(str) 之分，有时记不住，
习惯每次都加上括号试一下看看。对于明确的二维数组，并没有这样的用法区别，还是不要加的好。
速度变快的原因是搜索树省去了冗余的筛选过程。
bullscows函数和之前的guess_s函数是一样的，strchr我用的不妥，可以改成这样，效率无明显变化：
void bullscows( char target, char guess, AB *res )
{
static int idx;
static int chr;
res->a = 0;
res->b = 0;
for ( idx = 0; idx < 4; idx++ )
{
if ( guess == target )
res->a++;
else
for ( chr = 0; chr < 4; chr++ )
if ( guess == target )
{
res->b++;
break;
}
}
}
现在我放出最后的资料/参考网站：
这个网站给出了两种优化方案的搜索树，可以在线浏览
crushBullsCows
http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,crushBullsCows
avgBullsCows
http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,avgBullsCows
avgBullsCows 方案平均回合数 5.213 次
文档
http://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf
源码
bcAll28mar2013ver201.zip
这个实现就相当折腾了，里面好几个方案混合切换着用，特别是3.1节提到的 exact algorithm，时间消耗非常大，实现也相当费脑，等以后再尝试。
本帖最后由 523066680 于 2017-09-08 22:41 编辑
bcAll28mar2013ver201.zip - bcw/treeAvg5.txt 搜索树转Perl结构 以及 遍历测试
http://ys-i.ys168.com/205774990/p4J4U5J368NI5VUSMhV/treeAvg5_to_PerlStruct.zip
http://523066680.ys168.com/
位置：Perl/猜数字游戏BullsCows/treeAvg5_to_PerlStruct.zip
回复 31# 523066680
avgBullsCows 方案平均回合数 5.213 次yinxiangzhong haoxiang zuixin de shijie jilu shi 5.1X?
# (X keneng shi 6) :dizzy:
回复 32# 523066680
yanjiu le 1 tian, shouhuo bushao. 3Q ~~
faxian 1 chu:
memset(subset, 0, SIZE);
=> memset(subset, 0, SIZE * sizeof(int));
and this:
typedef struct node {
char ges;
int count;
struct node *ab; // move it to END
} Node;
int USEFUL = sizeof(Node) - 13 * sizeof(Node *);
void dump (Node *node, FILE *file) {
fwrite (node, USEFUL, 1, file);
...
void load (Node *node, FILE *file) {
fread (node, USEFUL, 1, file);
...
tree.dat de size keyi you 1.X M suoxiao dao 342 K
本帖最后由 523066680 于 2017-09-09 18:44 编辑
回复 34# rubyish
看明白了，省去了指针数据的导出。
那句 memset 可以去掉，因为nsize和子集合是由递归层重新赋值的。
//LinkedList
struct node
{
char guess;
char count;
struct node *res;
};
count 取值范围 0-13，改用 char 可以把体积缩小到 171kb
本帖最后由 rubyish 于 2017-09-11 22:26 编辑
回复 35# 523066680
Zai xuehuile maketree de jiqiao zhihou
Shishi perl:
ganxie 523066680. zhidao!! 3Q ~~
update:time: 0m1.166s
final version:
bull.pl
#!/usr/bin/perl
# version 26, subversion 0 (v5.26.0)
use 5.016; # >= 5.016
sub NUMBER() { 0 }
sub AGAIN(){ 1 }
sub OK() { 13 }
__INIT__:
print STDERR 'INIT...';
my @NUMBER = collect();
my $GUESS= guess();
__TEST__:
print STDERR "\rTEST";
my $TEST = 5040;
my @COUNT;
=IF_WANT_PRINT
my @AB = (
0x00, 0x01, 0x02, 0x03, 0x04, 0x10, 0x11,
0x12, 0x13, 0x20, 0x21, 0x22, 0x30, 0x40,
);
=cut
for my $ans ( 0 .. $TEST - 1 ) {
my $guess = $GUESS;
#say "\nA [@{$NUMBER[$ans]}] TEST ", $ans + 1;
for ( my $telle = 1 ; ; $telle++ ) {
my $num = $guess->;
my $that = AB( $ans, $num );
#printf "$telle [@{$NUMBER[$num]}] AB %02x\n", $AB[$that];
$COUNT[$telle]++, last if $that == OK;
$guess = $guess->[$that];
}
}
print STDERR "\rFINISH\n";
my $TOTO;
for my $i ( 1 .. $#COUNT ) {
next unless $COUNT[$i];
say "$i\t$COUNT[$i]";
$TOTO += $i * $COUNT[$i];
}
say "\nTEST\t= $TEST";
say "GUESS\t= $TOTO ";
printf "AVE\t= %.3f\n", $TOTO / $TEST;
# ____________________SUB____________________
sub guess {
my $guess = [];
my $fun = sub {
my ( $guess, $maybe ) = @_;
my $num = $maybe->;
$guess-> = $num;
my @next;
for my $may (@$maybe) {
my $ab = AB( $num, $may );
push @{ $next[$ab] }, $may;
}
for my $ab ( 0 .. 12 ) {
next unless $next[$ab];
__SUB__->( $guess->[$ab] = [], $next[$ab] );
}
};
$fun->( $guess, [ 0 .. 5040 - 1 ] );
return $guess;
}
sub AB {
state $val = [ 0, 5, 9, 12, 13 ];
my ( $N1, $N2 ) = @NUMBER[@_];
my ( $A, $B ) = ( 0, 0 );
for my $i ( 0 .. 3 ) {
$A++, next if $N1->[$i] == $N2->[$i];
for my $j ( 0 .. 3 ) {
$B++, last if $N1->[$i] == $N2->[$j];
}
}
$val->[$A] + $B;
}
sub collect {
sub {
my ( $a, $b ) = @_;
return $b if @$b == 4;
map __SUB__->( [ @$a[ 0 .. $_ - 1, $_ + 1 .. $#$a ] ],
[ @$b, $a->[$_] ] ), 0 .. $#$a;
} ->( [ 0 .. 9 ], [] );
}
__DATA__
$_