找回密码
 加入
搜索
AUTOIT CN»论坛 › AU3交流 › 『 提问交流 』 › ACM竞赛问题——九宫格问题，元素距离问题，扑克算24问 ...
123下一页
返回列表 发新帖
楼主: kenan

[效率算法] ACM竞赛问题——九宫格问题，元素距离问题，扑克算24问题（13L）

 火... [复制链接]
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[4];
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[0];
                                        if(p[i]=='+')
                                                sum+=a[1];
                                        if(p[i]=='-')
                                                sum-=a[1];
                                        if(p[i]=='*')
                                                sum*=a[1];
                                        if(p[i]=='/')
                                                sum/=a[1];
                                        if(p[j]=='+')
                                                sum+=a[2];
                                        if(p[j]=='-')
                                                sum-=a[2];
                                        if(p[j]=='*')
                                                sum*=a[2];
                                        if(p[j]=='/')
                                                sum/=a[2];
                                        if(p[k]=='+')
                                                sum+=a[3];
                                        if(p[k]=='-')
                                                sum-=a[3];
                                        if(p[k]=='*')
                                                sum*=a[3];
                                        if(p[k]=='/')
                                                sum/=a[3];
                                        if(sum==24) {flag=1;return;}


                                        sum=a[1];
                                        if(p[j]=='+')
                                                sum+=a[2];
                                        if(p[j]=='-')
                                                sum-=a[2];
                                        if(p[j]=='*')
                                                sum*=a[2];
                                        if(p[j]=='/')
                                                sum/=a[2];
                                        if(p[i]=='+')
                                                sum+=a[0];
                                        if(p[i]=='-')
                                                sum-=a[0];
                                        if(p[i]=='*')
                                                sum*=a[0];
                                        if(p[i]=='/')
                                                sum/=a[0];
                                        if(p[k]=='+')
                                                sum+=a[3];
                                        if(p[k]=='-')
                                                sum-=a[3];
                                        if(p[k]=='*')
                                                sum*=a[3];
                                        if(p[k]=='/')
                                                sum/=a[3];
                                        if(sum==24) {flag=1;return;}


                                        sum=a[1];
                                        if(p[j]=='+')
                                                sum+=a[2];
                                        if(p[j]=='-')
                                                sum-=a[2];
                                        if(p[j]=='*')
                                                sum*=a[2];
                                        if(p[j]=='/')
                                                sum/=a[2];
                                        if(p[k]=='+')
                                                sum+=a[3];
                                        if(p[k]=='-')
                                                sum-=a[3];
                                        if(p[k]=='*')
                                                sum*=a[3];
                                        if(p[k]=='/')
                                                sum/=a[3];
                                        if(p[i]=='+')
                                                sum+=a[0];
                                        if(p[i]=='-')
                                                sum-=a[0];
                                        if(p[i]=='*')
                                                sum*=a[0];
                                        if(p[i]=='/')
                                                sum/=a[0];
                                        if(sum==24) {flag=1;return;}


                                        sum=a[0];
                                        if(p[i]=='+')
                                                sum+=a[1];
                                        if(p[i]=='-')
                                                sum-=a[1];
                                        if(p[i]=='*')
                                                sum*=a[1];
                                        if(p[i]=='/')
                                                sum/=a[1];
                                        if(p[j]=='+'){
                                                if (p[k]=='+') sum=sum+(a[2]+a[3]);
                                                if (p[k]=='-') sum=sum+(a[2]-a[3]);
                                                if (p[k]=='*') sum=sum+(a[2]*a[3]);
                                                if (p[k]=='/') sum=sum+(a[2]/a[3]);
                                        }
                                        if(p[j]=='-'){
                                                if (p[k]=='+') sum=sum-(a[2]+a[3]);
                                                if (p[k]=='-') sum=sum-(a[2]-a[3]);
                                                if (p[k]=='*') sum=sum-(a[2]*a[3]);
                                                if (p[k]=='/') sum=sum-(a[2]/a[3]);
                                        }
                                        if(p[j]=='*'){
                                                if (p[k]=='+') sum=sum*(a[2]+a[3]);
                                                if (p[k]=='-') sum=sum*(a[2]-a[3]);
                                                if (p[k]=='*') sum=sum*(a[2]*a[3]);
                                                if (p[k]=='/') sum=sum*(a[2]/a[3]);
                                        }
                                        if(p[j]=='/'){
                                                if (p[k]=='+') sum=sum/(a[2]+a[3]);
                                                if (p[k]=='-') {if(a[2]-a[3]!=0) sum=sum/(a[2]-a[3]);}
                                                if (p[k]=='*') sum=sum/(a[2]*a[3]);
                                                if (p[k]=='/') sum=sum/(a[2]/a[3]);
                                        }
                                        if(sum==24) {flag=1;return;}


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

举报

Au3代码高亮发贴标签： [AU3] 你的代码 [/AU3]                   支持论坛的发展，请添加此》》网址导航《《为您的主页          
3mile
发表于 2012-4-16 19:29:23 | 显示全部楼层
回复 16# kenan
还要加括号？
抓狂中。。。
先不管了，先上15楼的修正代码，支持形如1-1+3*8 = 24之类可以重复的数。
#include <array.au3>

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

Local $fin[10001],$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[0]=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[0]&$run[$k]&$aa[1]&$run[$j]&$aa[2]&$run[$i]&$aa[3]
                                If Execute($msg)=24 Then _ArrayAdd($msg1,$msg&" = 24")                                
                        Next
                Next
        Next        
Next
_ArrayDisplay($msg1,TimerDiff($begin))

评分

参与人数 1金钱 +20 收起 理由
afan + 20

查看全部评分

回复

举报

user3000
发表于 2012-4-16 19:33:31 | 显示全部楼层
本帖最后由 user3000 于 2012-4-17 16:47 编辑

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

评分

参与人数 1金钱 +20 收起 理由
afan + 20

查看全部评分

回复

举报

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[1]
Local $run[4]=["+","-","*","/"]

Local $fin[10001],$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[0]=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[6]
                                $msg[0]=$aa[0]&$run[$k]&$aa[1]&$run[$j]&$aa[2]&$run[$i]&$aa[3]
                                                                $msg[1]="("&$aa[0]&$run[$k]&$aa[1]&")"&$run[$j]&$aa[2]&$run[$i]&$aa[3]
                                                                $msg[2]=$aa[0]&$run[$k]&"("&$aa[1]&$run[$j]&$aa[2]&")"&$run[$i]&$aa[3]
                                                                $msg[3]=$aa[0]&$run[$k]&$aa[1]&$run[$j]&"("&$aa[2]&$run[$i]&$aa[3]&")"
                                                                $msg[4]="("&$aa[0]&$run[$k]&$aa[1]&$run[$j]&$aa[2]&")"&$run[$i]&$aa[3]
                                                                $msg[5]=$aa[0]&$run[$k]&"("&$aa[1]&$run[$j]&$aa[2]&$run[$i]&$aa[3]&")"
                                                                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 | 显示全部楼层
我是来看大虾们的作品的
回复

举报

兔子先生
发表于 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的代码来了
回复

举报

happytc
发表于 2012-4-17 06:25:40 | 显示全部楼层
本帖最后由 happytc 于 2012-4-17 09:05 编辑
问题很好玩,试下
为了不影响他人思路,隐藏了
**** 本内容被作者隐藏 ****
3mile 发表于 2012-4-16 15:53


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

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

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

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


#include <Array.au3>

Opt("MustDeclareVars", 1)

;#cs
Global $aSudoku[9][9] = [[0, 6, 1, 0, 3, 0, 0, 2, 0], _
                                                [0, 5, 0, 0, 0, 8, 1, 0, 7], _
                                                [0, 0, 0, 0, 0, 7, 0, 3, 4], _
                                                [0, 0, 9, 0, 0, 6, 0, 7, 8], _
                                                [0, 0, 3, 2, 0, 9, 5, 0, 0], _
                                                [5, 7, 0, 3, 0, 0, 9, 0, 0], _
                                                [1, 9, 0, 7, 0, 0, 0, 0, 0], _
                                                [8, 0, 2, 4, 0, 0, 0, 6, 0], _
                                                [0, 4, 0, 0, 1, 0, 2, 5, 0]]
;#ce

#cs
Global $aSudoku[9][9] = [[0, 0, 3, 8, 1, 0, 0, 0, 9], _
                                                [5, 0, 0, 4, 0, 0, 0, 8, 0], _
                                                [0, 6, 0, 9, 0, 0, 1, 0, 0], _
                                                [0, 0, 8, 0, 3, 0, 0, 0, 6], _
                                                [0, 0, 0, 0, 0, 0, 0, 0, 0], _
                                                [9, 0, 0, 6, 0, 0, 5, 0, 0], _
                                                [0, 0, 6, 0, 0, 9, 0, 1, 0], _
                                                [0, 1, 0, 0, 0, 5, 0, 0, 4], _
                                                [2, 0, 0, 0, 4, 8, 7, 0, 0]]

#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[10], $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

评分

参与人数 2金钱 +60 收起 理由
afan + 30
3mile + 30 精彩，学习了

查看全部评分

回复

举报

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[9][9] = [[7, 6, 1, 9, 3, 4, 8, 2, 5], _
                                                        [3, 5, 4, 6, 2, 8, 1, 9, 7], _
                                                        [9, 2, 8, 1, 5, 7, 6, 3, 4], _
                                                        [2, 1, 9, 5, 4, 6, 3, 7, 8], _
                                                        [4, 8, 3, 2, 7, 9, 5, 1, 6], _
                                                        [5, 7, 6, 3, 8, 1, 9, 4, 2], _
                                                        [1, 9, 5, 7, 6, 2, 4, 8, 3], _
                                                        [8, 3, 2, 4, 9, 5, 7, 6, 1], _
                                                        [6, 4, 7, 8, 1, 3, 2, 5, 9]]
                                                        
        Local $aRandom[9]


        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

评分

参与人数 2金钱 +20 贡献 +2 收起 理由
afan + 2
3mile + 20

查看全部评分

回复

举报

pusofalse
发表于 2012-4-17 09:15:02 | 显示全部楼层
时间复杂度、空间复杂度均为o(1)的数独代码：
#include <Array.au3>

Local $sInit = "123456789", $aNumberX[9]

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

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

$aNumberX[7] = StringRegExpReplace($aNumberX[6], "(...)(...)(...)", "\2\3\1")
$aNumberX[8] = StringRegExpReplace($aNumberX[7], "(...)(...)(...)", "\2\3\1")

_Arraydisplay($aNumberX)


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

评分

参与人数 5金钱 +150 贡献 +5 收起 理由
haijie1223 + 30 + 5 今天才明白什么叫数独！
zch11230 + 10 加入书签收藏了 太精彩了
user3000 + 50 感觉自己脑子不够用!
afan + 30
3mile + 30 精彩,学习了

查看全部评分

回复

举报

下一页 »
123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 加入

本版积分规则

QQ|手机版|小黑屋|AUTOIT CN ( 鲁ICP备19019924号-1 )谷歌 百度

GMT+8, 2024-5-3 15:18 , Processed in 0.075858 second(s), 15 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表