免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 6639 | 回复: 7

猜数字问题的简单解法 [复制链接]

论坛徽章:
0
发表于 2013-10-28 14:09 |显示全部楼层
本帖最后由 iamlimeng 于 2013-10-28 14:10 编辑

猜数字游戏是一个比较老的智力游戏,较早出现在文曲星上,曾经流行过,规则如下:

由电脑随机生成一个由0-9组成的四位数(规则:可以由0开头,不能有重复数字,比如1123就不符合规则,0123符合规则),每猜一个数字,电脑就根据这个数字给出几A几B,其中A前面的数字表示数字和位置均正确的数的个数,而B前的数字表示数字正确而位置不对的数的个数。如正确答案为5234 而猜的人猜 5346,则是 1A2B,其中有一个5的位置对了,记为1A,而3和4这两个数字对了,而位置没对,因此记为 2B,合起来就是 1A2B。接着猜的人再根据出题者的几A几B继续猜,直到猜中(即 4A0B)为止。

步数计算规则:程序提示4A0B为最后一步,而不是以已经知道答案那一步为最后一步。

到目前为止,已知的解法是最多猜7步全中,平均5.213步。这种解法不是通过算法实现的,而是统计得来的,个人认为如果算法优秀,还有提升空间。

已知的算法比较多,比如可能集递归法,最大信息量法、最坏情况指标法等。本人实现的最佳算法:最多猜8步全中,平均5.295步。可能集递归法速度最快,最多猜8步全中,平均5.442步。统计方式为:把所有可能的5040个数字循环猜一遍,然后进行统计。

游戏见附件。Perl实现的代码我也有,但由于不是本人所写,故不公布。将我下面求解的代码修改即可轻松实现。

可能集递归法代码:
  1. #!/usr/bin/perl -w

  2. use strict;
  3. use warnings;

  4. #生成有效数字集
  5. my $number = '0123';
  6. my @valid;  #5040个有效数字
  7. while (length($number) == 4) {
  8.         my $valid = 1;
  9.         foreach (split('',$number)) {
  10.                  my $counts = () = ($number =~ /$_/g);
  11.                  if ($counts > 1) {
  12.                          $valid = 0;
  13.                          last;
  14.                  }
  15.          }
  16.          push(@valid,"$number") if ($valid);
  17.          $number++;
  18. }

  19. #求解,并进行统计输出
  20. my @valid_temp = @valid;
  21. my %count_guess = ();
  22. open(FH,">count_guess.xls");
  23. print FH "Answer Number\tGuess Times";
  24. foreach (1..8) { print FH "\tStep $_"; }
  25. print FH "\n";

  26. foreach my $answer(@valid) {
  27.          my $n = 1;
  28.          my $steps = '';
  29.         while (1) {
  30.                  my $number;
  31.                   if ($n == 1) { $number = $valid[0]; }
  32.                   else { $number = $valid_temp[int(@valid_temp/2)]; }
  33.                   #每次取可能集中居中的数字为下一次猜的数字
  34.                   #若随机取,最多步数为9步,个别情况为10步
  35.                  my $judge = judge($number,$answer);
  36.                  guess($number,$judge);
  37.                   $steps .= "\t$number:$judge";
  38.                   if ($judge eq '4A0B') {
  39.                          $count_guess{$n}++;
  40.                         print FH "$answer\t$n$steps\n";
  41.                         last;
  42.                   }
  43.                   $n++;
  44.         }
  45.          print "$answer\t$n\n";
  46.          @valid_temp = @valid;
  47. }
  48. my ($guess_times,$guess_values) = (0,0);
  49. print FH "\n";
  50. foreach my $n (sort keys %count_guess) {
  51.         $guess_times += $count_guess{$n};
  52.         $guess_values += $n * $count_guess{$n};
  53.         print FH "$n\t$count_guess{$n}\n";
  54. }
  55. print FH "Total\t$guess_times\n";
  56. print FH "Average\t",sprintf("%.3f",$guess_values/$guess_times),"\n";
  57. close FH;


  58. sub guess {   #求可能集
  59.         my ($number,$judge) = @_;
  60.          my @valid_search = @valid_temp;
  61.          @valid_temp = ();
  62.          foreach my $no (@valid_search) {
  63.                  push(@valid_temp,$no) if (judge($no,$number) eq $judge);
  64.          }
  65. }

  66. sub judge {  #求判断码
  67.          my($n,$g) = @_;
  68.          my ($a,$b)=(0,0);
  69.          foreach (0..3) {
  70.                  my $str_n = substr($n,$_,1);
  71.                  if ($str_n eq substr($g,$_,1)) { $a++; }
  72.                  elsif ($g =~ /$str_n/) { $b++; }
  73.          }
  74.          return ($a.'A'.$b.'B');
  75. }
复制代码
个人以为,通过优秀算法,有望将最大猜测步数减少到6步以内,若大家有更好的算法,希望共同探讨。
Guess_Number.rar (9.73 KB, 下载次数: 78)

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2013-10-28 16:17 |显示全部楼层
very good!

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-10-31 01:56 |显示全部楼层
本帖最后由 rubyish 于 2013-10-30 23:21 编辑

谢谢 lz ,学习了。来个山寨版~
  1. #!/usr/bin/perl
  2. use 5.018;
  3. my @gather = grep !/(\d).*\1/, '0123' .. '9876';
  4. my $score = -1;
  5. sub correct { @gather <= 1 }
  6. sub get {
  7.     my $num = shift;
  8.     while (1) {
  9.         $_ = do { print "$score | $num | AB = "; <> };
  10.         /^\s*(\d)\s*(\d)\s*$/ && $1 + $2 <= 4 && return $1, $2;
  11.         say "$score | wrong  AB !!";
  12.     }
  13. }

  14. sub pick {
  15.     my ( $pick, @pick ) = @gather[ rand @gather ];
  16.     my ( $A, $B ) = get $pick, $score++;
  17.     $score-- if $A == 4 and $B == 0;
  18.     for my $ok (@gather ){
  19.         my $a =
  20.           grep substr( $ok, $_, 1 ) eq substr( $pick, $_, 1 ), 0 .. 3;
  21.         $A == $a or next;
  22.         my $ab = () = $ok =~ /[$pick]/g;
  23.         $B == $ab - $a and push @pick, $ok;
  24.     }
  25.     @gather = @pick;
  26. }

  27. pick until correct;

  28. say $/, @gather ? ++$score . " [ @gather ] score: $score" : 'you liar';

复制代码
play 法:
  1. 0 | 9340 | AB = 02
  2. 1 | 3164 | AB = 12
  3. 2 | 3691 | AB = 02
  4. 3 | 4563 | AB = 02
  5. 4 | 1734 | AB = 30
  6. 5 | 1834 | AB = 30

  7. 6 [ 1234 ] score: 6
复制代码

论坛徽章:
0
发表于 2013-10-31 08:42 |显示全部楼层
回复 3# rubyish

实现得真不错,很简洁,赞!

按标准规则,计次应该从1开始,而不是0.

论坛徽章:
3
CU十二周年纪念徽章
日期:2013-10-24 15:41:34子鼠
日期:2013-12-14 14:57:19射手座
日期:2014-04-25 21:23:23
发表于 2013-10-31 09:06 |显示全部楼层
学习了~~~~

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2013-10-31 15:04 |显示全部楼层
学习了

论坛徽章:
0
发表于 2013-10-31 17:34 |显示全部楼层
有没有不学习的,提供个好算法!

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2013-11-01 13:32 |显示全部楼层
大牛,请写个
最大信息量法
最坏情况指标法
谢谢
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

基于案例的 SQL 优化实战训练营

讲师:中电福富特级专家梁敬彬,参与本次课程培训,你将收获:
1. 能编写出较为高效的 SQL;
2. 能解决70%以上的数据库常见优化问题;
3. 能得到老师提供的高效的相关工具和解决方案;
4. 能举一反三,收获不仅仅是 SQL 优化。
现在购票享受8.8折优惠!
----------------------------------------
优惠时间:2019年3月20日前

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP