小學一年級數學題 - 系列-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，對符合要求的排列順序進行輸出。