小学一年级数学题 - 系列-3

田小江

首先说我的答案，有八种。下面说说我的思路，大家看对不对。

第一步：九宫格的中心必须是5。因为中间的数字的两边与对角必须是四对加起来和一致的数。只有取5才能有四对。

到处为止，问题转化成了，四对数加起来等于十的排列组合有多少种？很容易知道是四对数，19，28，37，46

第二步：分析四个角的位置。我分析结论是四个角必须是偶数。因为边之和必须是15，三个数之和是奇数，则必定是俩偶一奇。假定一个角的数是奇数，那么它的对角必定是奇数。同时边的另外两个数就必须得是偶数。也就是边上除了这俩奇数，其他位置必须是偶数。就得有六个偶数，但我们只有四个偶数，所以不可能。

结论一，这时候我们知道四条边中心都是奇数，它们的不同排列组合就是一层运算情况。那么现在来分析下偶数位置会变么？

答案是不会。因为在偶数对中，28，46拆分配对的对所有情况只有两种，一种是24，68。一种是26，48。这两种情况的四个和分别是6，8，12，14。分别对应了四个奇数需要的值。所以每个奇数两边的偶数是固定。并且两个不相对的俩奇数必定需要同样的一个偶数。比如，1需要的组合是68里面有6，7需要的组合是26里面有6。其他情况一样。

所以，问题最终就转化成了转化成了，1、3、5、7四个奇数在四条边中心的位置组合，且要分离相对。

代码表示的话就是，把四条边线中心位，表示位数组的四个索引0，1，2，3。19和37在数组中的位置交叉即可。

很容易看出有8种：1397、1793、9317、9713、3179、3971、7139、7931

奇数组合出来后，偶数排列组合就不说了。找出俩奇数的共同偶数放夹角即可。

纯分析手打，就不上代码了（说不定代码我也不会写）

田小江

田小江 发表于 2017-06-25 08:41
首先说我的答案，有八种。&#19 ...

最后我想补充的就是，分析完后，用最优的或者你会的数据结构和算法。把各种组合算出来即可。

sunzhiguolu

回复 11# 田小江
首先一点 非常感谢您的精彩分析。将本来一团乱麻的思路 变得清晰了起来。
就是不知道 如果将心中所想落实到代码会是怎样。(按照您的分析，代码一定非常精彩)

523066680

1. =info
   
2.     Code by 523066680
   
3.     2017-06
   
4.     排列元素的方案参考自 http://stackoverflow.com/questions/9122315/permutations-using-perl
   
5. =cut
   
6. 
   
7. use List::Util qw/sum/;
   
8. 
   
9. our @a = (1..9);
   
10. 
    
11. #分组，校验的下标顺序
    
12. our @chk =
    
13.     (
    
14.         [1,2,3], [4,5,6], [7,8,9],
    
15.         [1,4,7], [2,5,8], [3,6,9],
    
16.         [1,5,9], [3,5,7],
    
17.     );
    
18. 
    
19. #纯属冗余操作（为了前面直观）。统一 -1
    
20. grep { $_ = [map { $_-1 } @$_] } @chk;  #全体 -1
    
21. 
    
22. #开始迭代
    
23. for ( &permute( @a ) )
    
24. {
    
25.     if (check($_) == 1)
    
26.     {
    
27.         print join(",", @{$_}[0,1,2]),"\n";
    
28.         print join(",", @{$_}[3,4,5]),"\n";
    
29.         print join(",", @{$_}[6,7,8]),"\n\n";
    
30.     }
    
31. }
    
32. 
    
33. sub permute
    
34. {
    
35.     return ([]) unless (@_);
    
36.     return map
    
37.     {
    
38.         my @cdr = @_;
    
39.         my $car = splice @cdr, $_, 1;
    
40.         map { [$car, @$_] } &permute(@cdr);
    
41.     } 0 .. $#_;
    
42. }
    
43. 
    
44. sub check
    
45. {
    
46.     my $a_ref = shift;
    
47.     my $result = 1;
    
48. 
    
49.     for my $ref (@chk)
    
50.     {
    
51.         if ( sum( map { $a_ref->[$_] } @$ref ) != 15 )
    
52.         {
    
53.             $result = 0;
    
54.             last;
    
55.         }
    
56. 
    
57.     }
    
58.     return $result;
    
59. }
    

复制代码

2,7,6
9,5,1
4,3,8

2,9,4
7,5,3
6,1,8

4,3,8
9,5,1
2,7,6

4,9,2
3,5,7
8,1,6

6,1,8
7,5,3
2,9,4

6,7,2
1,5,9
8,3,4

8,1,6
3,5,7
4,9,2

8,3,4
1,5,9
6,7,2

[Finished in 7.2s]

优化肯定是有的优化的，只是想看看暴力跑法。（我的strawberry perl 安装  Algorithm:ermute 失败了，所以先借用一下别人写好的排列方案）

rubyish

回复 9# jason680

穷举法 再优化 改良...
填入[0,1]立即检查[0] + [1] > 5 , [2] = 15 -( [0] + [1] )

3 Q ~~

rubyish

回复 14# 523066680

[Finished in 7.2s]

good machine ~~
wode:
real        0m22.694s
user        0m22.413s
sys        0m0.167s

rubyish

回复 11# 田小江

下面说说我的思路

3Q ~ zhege youyisi. XXle.

1. #!/usr/bin/perl
   
2. # (v5.26.0)
   
3. use 5.010;
   
4. 
   
5. make();
   
6. 
   
7. # _____________________SUB____________________
   
8. 
   
9. sub make {
   
10.     my @abcd = ( 2, 4, 6, 8 );
    
11. 
    
12.     for my $a (@abcd) {
    
13.         my $b = 10 - $a;
    
14.         my @cd = grep { $_ != $a and $_ != $b } @abcd;
    
15.         for my $cd ( [@cd], [ reverse @cd ] ) {
    
16.             my ( $c, $d ) = @$cd;
    
17.             my @X = ( 15 - $a - $c, 15 - $a - $d, 15 - $c - $b, 15 - $d - $b );
    
18. 
    
19.             # a  X0 c
    
20.             # X1 5  X2
    
21.             # d  X3 b
    
22. 
    
23.             say join ' ', $a, $X[0], $c;
    
24.             say join ' ', $X[1], 5, $X[2];
    
25.             say join ' ', $d, $X[3], $b;
    
26.             say '------';
    
27.         }
    
28.     }
    
29. }
    
30. 
    
31. __DATA__
    
32. $_
    

复制代码

sunzhiguolu

回复 7# rubyish
大神知道你厉害，有个地方不是很懂。
如果代码 添加了 use warnings; 该怎样改动一下？

sunzhiguolu

另外， 7楼代码 利用递归的方式求解 我不是很理解。
不知哪位大神 有时间帮忙 解释一下，最好详细一点。
如果能让我从中有所受益 本人愿出 (1000 积分作为回报, 视情形可提高积分比重 另外再加 +5000 积分作为感谢)

523066680

回复 19# sunzhiguolu

这个递归写的非常精简，我以前也用类似的方案写排列，不过代码比较长。
将 E_ 函数单独提取出来，把 “语法糖” 之类的东西采用更明确的方式去书写，思路就看得清楚了。
为了方便把元素 1到9 改成了a,b,c。

my @elements = qw/a b c/; my @container = (); #传入数组引用，左边是可选元素，右边是容器 func( \@elements, \@container ); sub func {     #引用分别传递到 $a，$b     my ( $a, $b ) = (shift, shift);     my $last = $#$a;     #如果 @$a 的元素已经清空，打印 @$b 的内容     print join(",", @{$b}), "\n" if ( $last < 0 );         #遍历选取 @$a 的元素     for my $idx ( 0 .. $last )     {         #从 @$a 副本取出元素，添加到 @$b，进入下一层选取         func( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ] );     } }

输出：

a,b,c a,c,b b,a,c b,c,a c,a,b c,b,a

这个过程可以参考高中的排列组合/概率知识，
第一层，先从 [a,b,c] 中选1个，假设是选 b
第二层，从 剩下的 [a,c] 中选取1个，假设是 a
第三层，从 剩下的 [c] 中选取1个，即 c
最后得到 b,a,c

第一层有3个选项，第二层有2个选项，最后一层1个，共有 3x2x1 种排列顺序。

然后是校验的部分，

if    ( @$b == 3 ) { sum( @$b[ 0, 1, 2 ] ) != 15 and return }     elsif ( @$b == 6 ) { sum( @$b[ 3, 4, 5 ] ) != 15 and return }     elsif ( @$b == 7 ) { sum( @$b[ 0, 3, 6 ] ) != 15                        || sum( @$b[ 2, 4, 6 ] ) != 15 and return }     elsif ( @$b == 8 ) { sum( @$b[ 1, 4, 7 ] ) != 15 and return }     elsif ( @$b == 9 ) { sum( @$b[ 0, 4, 8 ] ) != 15 and return;         print "@$b[0,1,2]\n@$b[3,4,5]\n@$b[6,7,8]\n";         print "-----\n";     }

多个层次的判断可以减少大量冗余的排列过程，例如第一个判断：
当容器数组达到3个元素，可以计算第一行是否和为15，不是的话可以提前退回，节省后面6个元素的排列过程。
后面的判断与此类似。
最后当容器数组的元素达到9个，且最后斜线合计也为15，对符合要求的排列顺序进行输出。