8分

樓主

個人積分：8分

文章編號：4152965

數學遊戲+程式設計（最近遇到的比賽題目）

小弟昨天去參加個比賽
被一題程式考到了
好久沒這樣了說..哈

題目是這樣的：
畫出如下方格，並由程式產生在方格內填入數字，每執行一次程式，
可得到不同的數字排列，但是需符合下列要求。
要求：1.每行、每列及斜對角和皆為相等
2.每隔數字在0~9的範圍，不得重複

0	3	6
1	4	7
2	5	8

有人解得出來嗎？我重比賽玩到現在，我只產生了不可重複
剩下的第一個需求我怎麼做出來都是無窮迴圈
（本來想用數學原理的，想了想還想不出來...暈倒）
如果有大大有想法，請支援小弟或者跟小弟討論一下
謝謝大大

2007-11-20 23:48 #1

文章關鍵字

數學遊戲程式設計比賽題目

todau

50分

2樓

todau

個人積分：50分

文章編號：4153667

google 魔方陣

ahong001

29分

3樓

ahong001

個人積分：29分

文章編號：4154050

獻醜一下, 也是第一次看到這種題目.

1. 從 0~9 挑出9個數字且可以符合3行的行總和其值相等
=> 這9個數字的總和必為3的倍數
=> (0+9)x10/2 = 45
=> 任意去掉0..9其中一數N, 餘下9個數的總和為(45-N)必為3的倍數
=> N只能為0, 3, 6, 9
=> 可能之數列為
0...8 總和為36
1...9 總和為45
0..2, 4..9 總和為42
0..5, 7..9 總和為39

2. 填入九宮格後, 縱/橫/斜之單行和值須相等
=> 假設正中間數字為N, 其餘為A B C D E F G H

A B C
D N E
F G H

=> (A+N+H) = (B+N+G) = (C+N+F) = (D+N+E) = (A+B+C+D+N+E+F+G+H) / 3
=> A+B+C+D+E+F+G+H+4xN = ((A+B+C+D+N+E+F+G+H) / 3) x 4
=> 3xN = (A+B+C+D+N+E+F+G+H) / 3
=> N = (A+B+C+D+N+E+F+G+H) / 9
=> 9個數字總和需為9的倍數
=> 只剩總和為36 或45符合條件

==> 第一階段可用程式先求得N (只有4或5能成立) 並決定數字集合(0..8 或 1..9)

3. 排除無法擺在角落的數字

A B C
D N E
F G H

=> (A+B+C) + (A+N+H) + (A+D+F) = A+B+C+D+E+F+G+H+N
=> 2xA = E+G
=> A不可為最大數 (若E<A, G<A, 則E+G < 2xA) 亦不可為最小數 (若E>A, G>A, 則E+G > 2xA)
=> 最大數與最小數只能在B, D, E, G位置出現

==> 第二階段可先決定最大數位置(4種可能), 其對面的數字也就決定(例如最大數放在B, 則G就只有一種選擇). 剩下的6個位置可用窮舉法只需P(6,6) = 6x5x4x3x2x1 = 720 即可全部找出. 其實改變最大數的位置就相當於"旋轉"的效果, 亦即在第一種組合中找到的解(應有2組)直接旋轉即可得其他6組.

4. 總和為36
=> N = 4
=> 若以最上列中間為 8 可得下列兩組結果

1 8 3 3 8 1
6 4 2 2 4 6
5 0 7 7 0 5

=> 再加以旋轉, 可得共8種解答

5. 總和為45
=> N = 5
=> 若以最上列中間為 9 可得下列結果

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

=> 再加以旋轉, 可得共8種解答

可能有錯, 歡迎指正.

elase

0分

4樓

elase

個人積分：0分

文章編號：4154320

Zx s wrote:
小弟昨天去參加個比賽...(恕刪)

比賽用暴力法去解就可以了..
用迴圈把九官格的每種組合做出來
判斷符合條件就輸出答案
提示:
宣告一個10個元素的一維陣列
值填入[0,1,2,3,4,5,6,7,8,9]
之後去排列它

Zx s

8分

樓主

Zx s

個人積分：8分

文章編號：4156048

elase wrote:
比賽用暴力法去解就可...(恕刪)

小弟當初就是使用這種方法，但是就是解不出來
形成了無窮迴圈....

打雜小瑋云：『金錢誠可貴，職銜價更高，若為生命故，兩者皆可』

Surhoff

188分

6樓

Surhoff

個人積分：188分

文章編號：4156505

Zx s wrote:
小弟當初就是使用這種...(恕刪)

我記得解這種題目有一個公式
正在努力的回想中...
想起來再PM給你

之前有寫過

馬克蘇

785分

7樓

馬克蘇

個人積分：785分

文章編號：4156530

Zx s wrote:
小弟當初就是使用這種...(恕刪)

光排九宮格就不可能是無窮回圈，你程式寫錯了

敗家真是無底洞阿～

Kinomoto

0分

8樓

Kinomoto

個人積分：0分

文章編號：4156532

Zx s wrote:
小弟當初就是使用這種...(恕刪)

那就是你程式效率可能有點問題
這問題的暴力法就是10個不同號碼的球取9個出來排列的問題
總共的組合為P(10,9) = 10! = 3628800種組合
每種組合最多要驗證8次才能確定其合乎規定
所以著眼點為
1. 列出組合 <-- 寫程式在畫面上秀出進度比較能確定你的程式沒問題
2. 驗證組合 <-- 這一段應該還好

A	B	C
D	E	F
G	H	I

先把八行全加起來看的話
A,C,G,I被加了3次
B,D,F,H被加了4次
E被加了一次
所以先驗證3*(A+C+G+I) + 2*(B+D+F+H) + 4*E是否能被8整除
如果成立再去驗證其他

--
你的無窮迴圈的問題很有可能是你產生排列的方法是從頭到尾隨機取數列
而沒驗證是否之前取過此數列
感覺就變成亂開槍，但總是有些組合打不到

Jungchu Hsu

11分

9樓

Jungchu Hsu

個人積分：11分

文章編號：4156681

我想可以由另一邊去去除一些可能性吧...
如果是九宮格....應該是1~9 (不然就0~8)~
中間數必然在中間..... 5
在中間數兩邊的是互補的數...所以可以確定...在同一直線上...
這樣子應該就可以把可能性下降很多了....
像以下的

8 1 6
3 5 7
4 9 2

好像有啥麼規則性....不過要在找一下~^^""""~
就算要用暴力法也要先去除一點可能性@@~

Zx s

8分

樓主

Zx s

個人積分：8分

文章編號：4157077

代替changdean發言一下

changdean wrote:
Hi 由於權限不足無法版面回覆，我有一點問題可否請你再次補充
1.每行、每列及斜對角和皆為相等
每行: 請問是每行的值加總嗎 ?
Line1 : 1 2 3
Line2 : 4 5 6
Line3 : 7 8 9
1 + 2 + 3 = 4 + 5 + 6 = 7 + 8 + 9

2.每行、每列及斜對角和皆為相等
每列: 請問是每列的值加總嗎 ?
Line1 : 1 2 3
Line2 : 4 5 6
Line3 : 7 8 9
1 + 2 + 3 = 4 + 5 + 6 = 7 + 8 + 9

3.每行、每列及斜對角和皆為相等
斜對角: 請問是僅針對斜對角的值加總嗎 ?
Line1 : 1 2 3
Line2 : 4 5 6
Line3 : 7 8 9
1 + 9 = 3 + 7

麻煩你可以回覆在版面上，這題目很有趣呦 ^^

是全部通通都相等
也就是
1 + 2 + 3 = 4 + 5 + 6 = 7 + 8 + 9
=1 + 4 + 7 = 2 + 5 + 8 = 3 + 6 + 9
= 1 + 5 + 9 = 3 + 5 + 7

感謝各位... 小弟還是無解= =

打雜小瑋云：『金錢誠可貴，職銜價更高，若為生命故，兩者皆可』

數學遊戲+程式設計（最近遇到的比賽題目）

小惡魔新聞台

小惡魔廣編特輯

數學遊戲+程式設計（最近遇到的比賽題目）

小惡魔新聞台

小惡魔廣編特輯

今日熱門文章 網友點擊推薦！

今日熱門文章　網友點擊推薦！