ACM竞赛问题——九宫格问题，元素距离问题，扑克算24问题（13L）-『提问交流』-AUTOIT CN

kenan 发表于 2012-4-16 19:27:23

回复 15# 3mile

我的算法是：4的数字中间有三个运算符，进行穷举，就有4^3=64中情况，然后不过三七二十一都加括号，就有5种情况，然后这4的数字还要进行全排列
表达不好，不知能否听懂。。。。
这是c++代码#include <iostream>
using namespace std;
bool flag=0;
int sum=0;
char p[]={'+','-','*','/'};
int a;
void perm(int a[],int k){
if(flag==1) return;
if(k==4){
flag=0;
int i, j ,k;
for(i=0;i<4;i++){
for(j=0;j<4; j++){
for(k=0;k<4;k++){
sum=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(sum==24) {flag=1;return;}

sum=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(sum==24) {flag=1;return;}

sum=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(sum==24) {flag=1;return;}

sum=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+'){
if (p=='+') sum=sum+(a+a);
if (p=='-') sum=sum+(a-a);
if (p=='*') sum=sum+(a*a);
if (p=='/') sum=sum+(a/a);
}
if(p=='-'){
if (p=='+') sum=sum-(a+a);
if (p=='-') sum=sum-(a-a);
if (p=='*') sum=sum-(a*a);
if (p=='/') sum=sum-(a/a);
}
if(p=='*'){
if (p=='+') sum=sum*(a+a);
if (p=='-') sum=sum*(a-a);
if (p=='*') sum=sum*(a*a);
if (p=='/') sum=sum*(a/a);
}
if(p=='/'){
if (p=='+') sum=sum/(a+a);
if (p=='-') {if(a-a!=0) sum=sum/(a-a);}
if (p=='*') sum=sum/(a*a);
if (p=='/') sum=sum/(a/a);
}
if(sum==24) {flag=1;return;}

sum=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(p=='+')
sum+=a;
if(p=='-')
sum-=a;
if(p=='*')
sum*=a;
if(p=='/')
sum/=a;
if(sum==24) {flag=1;return;}
}
}
}
return;
}
for(int i=k;i<4;i++){
swap(a,a);
perm(a,k+1);
swap(a,a);
}
}
int main(){
cin>>a>>a>>a>>a;
perm(a,0);
cout<<(flag==1?"YES":"NO")<<endl;
return 0;
}

3mile 发表于 2012-4-16 19:29:23

回复 16# kenan
还要加括号？
抓狂中。。。
先不管了，先上15楼的修正代码，支持形如1-1+3*8 = 24之类可以重复的数。
#include <array.au3>

Dim $begin = TimerInit()
Local $str,$msg1
Local $run=["+","-","*","/"]

Local $fin,$z=1
for $i=1 to 10
For $n=1 to 10
For $k=1 to 10
For $p=1 to 10
$fin[$z]=$i&","&$n&","&$k&","&$p
$z+=1
Next
Next
Next
Next
$fin=UBound($fin)-1

For $b=1 To UBound($fin)-1
   $aa=StringSplit($fin[$b],",",2)
   For $i=0 To 3
            For $j=0 To 3
                     For $k=0 To 3
                           $msg=$aa&$run[$k]&$aa&$run[$j]&$aa&$run[$i]&$aa
                           If Execute($msg)=24 Then _ArrayAdd($msg1,$msg&" = 24")
                     Next
            Next
   Next
Next
_ArrayDisplay($msg1,TimerDiff($begin))

user3000 发表于 2012-4-16 19:33:31

本帖最后由 user3000 于 2012-4-17 16:47 编辑

竟然隔了一天才发现看错了此九宫格的题意!
A 大竟然还给我评分, 真是'汗颜'至极!
已编辑删掉自己错误的见解!

kenan 发表于 2012-4-16 19:41:22

回复 18# 3mile

好像不全啊
7 2 3 4就没有枚举出来

3mile 发表于 2012-4-16 19:45:22

回复 20# kenan
不知道全不全，算法太肉了。
#include <array.au3>

Dim $begin = TimerInit()
Local $str,$msg1
Local $run=["+","-","*","/"]

Local $fin,$z=1
for $i=1 to 10
For $n=1 to 10
For $k=1 to 10
For $p=1 to 10
$fin[$z]=$i&","&$n&","&$k&","&$p
$z+=1
Next
Next
Next
Next
$fin=UBound($fin)-1

For $b=1 To UBound($fin)-1
   $aa=StringSplit($fin[$b],",",2)
   For $i=0 To 3
            For $j=0 To 3
                     For $k=0 To 3
Local $msg
                           $msg=$aa&$run[$k]&$aa&$run[$j]&$aa&$run[$i]&$aa
$msg="("&$aa&$run[$k]&$aa&")"&$run[$j]&$aa&$run[$i]&$aa
$msg=$aa&$run[$k]&"("&$aa&$run[$j]&$aa&")"&$run[$i]&$aa
$msg=$aa&$run[$k]&$aa&$run[$j]&"("&$aa&$run[$i]&$aa&")"
$msg="("&$aa&$run[$k]&$aa&$run[$j]&$aa&")"&$run[$i]&$aa
$msg=$aa&$run[$k]&"("&$aa&$run[$j]&$aa&$run[$i]&$aa&")"
For $z=0 to 5
If Execute($msg[$z])=24 Then _ArrayAdd($msg1,$msg[$z]&" = 24")
Next
                     Next
            Next
   Next
Next
_ArrayDisplay($msg1,TimerDiff($begin))

whitehead 发表于 2012-4-16 20:00:16

那么快，太牛了

sunafter 发表于 2012-4-16 20:15:12

我是来看大虾们的作品的{:face (411):}

兔子先生 发表于 2012-4-16 20:42:23

这。。。算法。。。

502762378 发表于 2012-4-16 22:03:47

回复 15# 3mile

看了你写的，我顿时决定把我以前写的删除

xx44t10 发表于 2012-4-16 23:41:18

厉害啊。。我是来学习的

shuangsexing 发表于 2012-4-17 00:23:33

好东西，我也来看看

Ycxw2008 发表于 2012-4-17 04:44:01

学习3mile的代码来了 {:1_494:}

happytc 发表于 2012-4-17 06:25:40

本帖最后由 happytc 于 2012-4-17 09:05 编辑

问题很好玩,试下
为了不影响他人思路,隐藏了
**** 本内容被作者隐藏 ****
3mile 发表于 2012-4-16 15:53 http://www.autoitx.com/images/common/back.gif

大清早起来，花上点时间做下这个题

三笑，你的代码可能有问题的或效率低，当把数字多挖几个出去，就计算好久也得不到结果的
比如下面的九宫：
Local $array = [, _
      , _
                  , _
                  , _
                  , _
                  , _
                  , _
                  , _
                  ]

或者把一楼楼主给的九宫数字多挖一个，也就是把N=6也换成0，就死在循环里出不来了
Local $array = [, _
   , _
   , _
   , _
   , _
   , _
   , _
   , _
   ]

我也给个代码，方法是‘基于候选树的可能求解回溯法’：

#include <Array.au3>

Opt("MustDeclareVars", 1)

;#cs
Global $aSudoku = [, _
, _
, _
, _
, _
, _
, _
, _
]
;#ce

#cs
Global $aSudoku = [, _
, _
, _
, _
, _
, _
, _
, _
]

#ce

CoreSudoku()

Func CandidateNumber($iX, $iY, ByRef $aFlag)
Local $gi, $gj, $iCount = 0

For $i = 1 To 9
$aFlag[$i] = 0
Next

For $i = 0 To 8
$aFlag[$aSudoku[$iX][$i]] = 1
$aFlag[$aSudoku[$i][$iY]] = 1
Next

$gi = Floor($iX / 3) * 3
$gj = Floor($iY / 3) * 3

For $i = 0 To 2
For $j = 0 To 2
$aFlag[$aSudoku[$gi + $i][$gj + $j]] = 1
Next
Next

For $i = 1 To 9
If 0 == $aFlag[$i] Then $iCount += 1
Next

Return $iCount
EndFunc

Func CoreSudoku()
Local $aFlag, $iMinNum = 10, $iMinNumRow = -1, $iMinNumColumn

For $i = 0 To 8
For $j = 0 To 8
If $aSudoku[$i][$j] Then ContinueLoop
Local $iCandidateNum = CandidateNumber($i, $j, $aFlag)

If 0 == $iCandidateNum Then Return

If $iCandidateNum < $iMinNum Then
$iMinNumRow = $i
$iMinNumColumn = $j
$iMinNum = $iCandidateNum
EndIf
Next
Next

If -1 == $iMinNumRow Then
_ArrayDisplay($aSudoku, "Answer of sudoku is: ")
Return
EndIf

CandidateNumber($iMinNumRow, $iMinNumColumn, $aFlag)

For $i = 1 To 9
If $aFlag[$i] == 0 Then
$aSudoku[$iMinNumRow][$iMinNumColumn] = $i
CoreSudoku()
EndIf
$aSudoku[$iMinNumRow][$iMinNumColumn] = 0
Next
EndFunc

happytc 发表于 2012-4-17 08:34:47

本帖最后由 happytc 于 2012-4-17 08:43 编辑

回复 19# user3000

产生新的九宫图的一个猥琐方法

其实对于这种数独矩阵，由矩阵知识可知，对于已存在一个数独矩阵a，满足以下三点：

① 对a进行数字轮换群操作，产生的新矩阵是数独矩阵
② 对a的任意行内，对任意两个数字之间交换，产生的新矩阵是数独矩阵
③ 对a的任意列内，对任意两个数字之间交换，产生的新矩阵是数独矩阵

根据以上三点，对已存在的数独矩阵进行变化，就可以产生新的数独矩阵了。然后对新的数独矩阵随便挖掉些数字，就是新的一个九宫图了

以下代码以一楼给的数独矩阵作为已存在的数独矩阵，用①种方法产生新的数独矩阵：

#include <Array.au3>

Main()

Func Main()
Local $aSudoku = [, _
, _
, _
, _
, _
, _
, _
, _
]

Local $aRandom

CreateRandom($aRandom)
CreateNewSoduku($aSudoku, $aRandom)
_ArrayDisplay($aSudoku)
EndFunc

Func CreateNewSoduku(ByRef $aSudoku, ByRef $aRandom)
Local $iRandomA, $iRandomB, $iSwapNum

;对每个数字做轮换
For $i = 0 To 8
For $j = 0 To 8
$aSudoku[$i][$j] = $aRandom[$aSudoku[$i][$j] - 1]
Next
Next
EndFunc

;生成一个随机1~9一维数组序列
Func CreateRandom(ByRef $aRandom)
Local $iRandomNum, $iFlag = 0

For $i = 0 To 8
While True
$iRandomNum = Random(1, 9, 1)

For $j = 0 To $i
If $aRandom[$j] = $iRandomNum Then
$iFlag = 1
ExitLoop
EndIf
Next

If $iFlag = 1 Then
$iFlag = 0
ContinueLoop
Else
$aRandom[$i] = $iRandomNum
ExitLoop
EndIf
WEnd
Next
EndFunc

pusofalse 发表于 2012-4-17 09:15:02

时间复杂度、空间复杂度均为o(1)的数独代码：
#include <Array.au3>

Local $sInit = "123456789", $aNumberX

$aNumberX = $sInit
$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")
$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")
$aNumberX = StringRegExpReplace($aNumberX, "(..)(.)(..)(.)(..)(.)", "\2\1\4\3\6\5")

$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")
$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")
$aNumberX = StringRegExpReplace($aNumberX, "(..)(.)(..)(.)(..)(.)", "\2\1\4\3\6\5")

$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")
$aNumberX = StringRegExpReplace($aNumberX, "(...)(...)(...)", "\2\3\1")

_Arraydisplay($aNumberX)

初始序列直接用了123456789，没有先乱序排列。换成别的初始序列也是可以的。

页: 1 [2] 3

AUTOIT CN's Archiver