发表回复 
ahk有奖竞答活动开始了,快来看啊-1-12.10.29
2012-10-29, 15 : 43
ahk有奖竞答活动开始了,快来看啊-1-12.10.29
为了活跃论坛氛围,我每周会放出两道算法题和两道应用题。只要回帖提供解决方案就有奖励,质量高,回帖早的还有特别奖励等着你,机会有限不容错过哦。

答题有累计效应,两题都答的,奖励翻倍,答的越多加成越多哦。水平高,有热情,积极参与的童鞋更有机会参与论坛管理来,一同为论坛添砖加瓦。

答题只能用autohotkey哦,谢绝其他辅助软件,答题尽量简明扼要。


算法题1

得到小于N的所有质数。


应用题1

根据附件的拼音字典,得到任意中文的拼音,比如“论坛”得到“lun tan”。


附件
.txt  pinyin.txt (大小: 94.95 KB / 下载: 10)
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-10-30, 02 : 26
 
代码: (全选)
SetBatchLines -1
;1、哈哈,拙劣的算法
n:=20
Loop,% n
{
    count:=0
    index:=a_Index
    Loop,% index
    {
        if(mod(index,a_Index)=0)
            count++
    }
    if (count=2)
        msgbox % index
}

;2、用正则表达式配的
msgbox % getPinYin("ahk有奖竞答活动开始了")
getPinYin(ch)
{
    stringSplit,chArray,ch
    fileread,source,pinyin.txt
    pinyin:=""
    ;多音字啥的不考虑了
    Loop,% chArray0
    {
        ;拼音字典里有乱码导致正则可能失效,故加了这个判断
        if(asc(chArray%a_Index%)>=65&&asc(chArray%a_Index%)<=122)
        {
            pinyin:=pinyin . "" . chArray%a_Index%
            continue
        }
        pos:=regexMatch(source,"([a-z]+)\d.*" . chArray%a_Index%,outvar,1)
        ;无匹配项用原字符
        outvar1:=pos=0?chArray%a_Index%:outvar1
        pinyin:=pinyin . " " . outvar1
    }
    return pinyin
}
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-10-31, 17 : 16
 
第一题,速度更快的代码
代码: (全选)
prime(n)
{
        p := [],k=0
        Loop
        {
                i := A_Index
                if (i > n)
                        break
                if (i = 1)
                        continue
                isPrime := 1 , t := Floor(Sqrt(i))
                loop
                {
                        if !p[A_Index] or p[A_Index]>t
                                break
                        if !mod(i,p[A_Index])
                        {
                                isPrime := 0
                                break
                        }
                }
                if isPrime
                        p.Insert(++k,i)
        }
        return k ; k为质数个数
}
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-10-31, 23 : 21
 
都忘了因式分解要用質數了! :P
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-11-03, 22 : 40
 
[i=s] 本帖最后由 jony.tw 于 2012-11-6 00:43 编辑 [/i]

一直在想nepter若真的給的解已是最有效率的那麼質數這題就不需多想了
但是腦海中一直記得當初學質數時思考過的一些東西
用平方根方式抓出可能最大需測試的因數固然減少了多餘的IF測試

但在排除2,5兩個因數之後 大於10的數 只有尾數是 1 3 7 9 的數字可能是質數,
所以用一一測試的方式絕不是效率最高的方式,因為得到2這個質因數後,偶數就被完全排除在外了,而在排除3這個因數後...9抓掉了
就從21開始抓吧...21, 27, 33, 39,...51,57,63,69....81,87,93,99....被排除而且有循環性 間隔是6

而且奇數一定是奇數乘奇數,在排除7這個因數後,7的平方49這個數前面的質數就定出來了
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
也就是說11的平方121前可能不是質數的1379序列...可以自49後開始檢查排除到最大極限值...7之前的都排除了..就只要排除11這個質因數排除到最大極限值​. ...同樣的13的平方169從127開始排除到最大極限值 ...只要再排除13這個質因數
-----------------------------------------------------------------------------
另一個思惟是來自公式X^2 - A^2=(X-A)*(X+A) ^代表乘幂
而平方數的序列其實是2N+1(奇數序列的累加) 1 4 9 16 25 之間的差是 3 5 7 9
-----------------------------------------------------------------------------
尚未把思考的變成腳本......先分享觀點,朋友們有興趣再試做更有效率的吧!
卻看到老外用別的程式寫成的....很頭痛沒看懂他為何要那麼寫...但他真的也是用奇數陣列去排除掉非質數,並且快速的在可能質數群中快速的前移處理指標...數值愈大​抓掉的非質數分布愈稀疏
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-11-03, 23 : 20
 
拼音這題...我的思維也是在演算法效率打轉,因為給的表是反函數
即以音尋字快速,以字尋音就要整篇搜尋,所以第一件事是建立字對音的表並予以排序過
對多音字也可以交待...可選擇性的跳出多音提示
之後以字為鍵取值...以二元搜尋判斷快速索引取值
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-11-04, 19 : 44
 
你的字典的编码有问题
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
2012-11-17, 23 : 55
 
[i=s] 本帖最后由 jony.tw 于 2012-11-19 23:42 编辑 [/i]

先把解質數這題呈上....會寫出一個表示質數群的檔...目前計算的最大值<30045
代码: (全选)
SetFormat, Integer, hex
rSp1 := 0
rSp2 := 0
rSp3 := 0
rSp4 := 0
;~ Base_str := "2357" ;小於10的質數 直接列出了
Base_3 := "0a5"   ;排除 2 3 5 之後得到的基礎 PATTERN 用16進位數由左而右順數 4個 bit 表示尾數 1 3 7 9 的數是否質數 (1 非質數 0 是質數)
MsgBox % "去除2 3 5後的可能質數 元`r`n" . Decode_2(Base_3 , "1379", "X")
v := 0
f := "3"
lg := 3
g := "7"
lastg := 3
v := g*g//10-1      ;自下個質數的平方數開始排除有因數的數
lg := lg*g
GoSub PrimerList   ;再排除 7 可整除的數 抓出PATTERN長 21 bytes
lastg := g
f := "7"
g := "11"
lg := lg*g
v := g*g//10-lastg*lastg//10    
GoSub PrimerList  ;再排除 11可整除的數 抓出PATTERN長 231 bytes
lastg := g
f := "11"
g := "13"
lg := lg*g
v := g*g//10-lastg*lastg//10    
GoSub PrimerList  ;再排除 13可整除的數 抓出PATTERN長 3003 bytes


MyBigData := "p"
;~ VarSetCapacity(MyBigData, 30045)  ; 就抓到 300459 以下的所有質數吧!
MyBigData := SubStr(Base_3,1,3) . SubStr(Base_7,1,8) . SubStr(Base_11,1,4) . rept(Base_13, 10)  ;從11開始 .....到 300459的bits代碼群用13的PATTERN建立
Base_3 := ""
Base_7 := ""
Base_11:= ""
Base_13:= ""
;~ msgBox MyBigData is Exists
Max_g := ceil(sqrt(300459)) ; 要排除的最大質因數大小
while (g <= Max_g){
bas ++
ListVars
AAA := substr(MyBigData,bas,1)
bitstr := Decode_2(AAA)
loop 4 {
if (substr(bitstr,A_index,1) = "0"){  
      g := bas*10 + A_index*2-1+((A_index+1)//4)*2
      if (g <=13)
            continue
gosub PrimerList2
}
}
}


FileAppend,  %MyBigData% , C:\Users\J\Desktop\MyBigData.txt
FileAppend,  % Decode_2(MyBigData,"1379", "X") . "`r`n`r`n`r`n" , C:\Users\J\Desktop\MyBigData1379.txt

return


;基礎pattern的建立副程式
PrimerList:
Filter%g% := Filter(g,Ceil((14+g)/g)+1)
Base_%f% := Rept(Base_%f%,Ceil((lg+14)/f))
i := 0
Loop % Ceil(lg/15) {
var1 := "0x1" .  subStr(Base_%f% ,i+v+1,15)
var2  := "0x" .  subStr(Filter%g%, mod(i,g)+1,15)
;~ MsgBox % var1  .  "    "  . var2
if (var2 <>0)
Base_%g% .=  var1  |  var2
i += 15
}
StringReplace,  Base_%g%,  Base_%g% , 0x1,,A
Base_%g% := SubStr(Base_%g% , 1 , lg)
MsgBox % "去除2 3 5....到" .  g  . "後的可能質數 元`n`r" .  Decode_2(Base_%g% , "1379", "X",g*g//10)
Filter%g% := ""
return

;排除非質數的副程式
PrimerList2:
FilterX := subStr(Filter(g,Ceil((14+g)/g)+1),1,14+g)
v := g*g//10
i := 0
While (i+v+14 <= 30045) {
var1 := "0x1" .  subStr(MyBigData ,i+v,15)
var2  := "0x" .  subStr(FilterX, mod(i,g)+1,15)
;~ MsgBox % var1  .  "    "  . var2
if (var2 != 0) {
var3 :=  var1  |  var2
var3 := var3 . ""
StringReplace var3 , var3 , 0x1
ListVars
BaseX .= var3
}else{
      var1 := var1 . ""
      StringReplace var1 , var1 , 0x1
BaseX .= var1
}
i += 15
}
MyBigData := SubStr(MyBigData,1,v-1) . BaseX
BaseX :=""
FilterX := ""
return





Filter(Prim, n=1) {
global rSp1 , rSp2 , rSp3, rSp4 , L1
Sp0 := Prim*1//10
Sp1 := Prim*3//10 - Prim*1//10
Sp2 := Prim*7//10 - Prim*3//10
Sp3 := Prim*9//10 - Prim*7//10
Sp4:= Prim*11//10 - Prim*9//10
L1 := Mod(Prim ,10)

    if (L1 = 9) {
          retStr := "8" . Rept("0",Sp4-1) . "1" . Rept("0",Sp1-1) . "2" . Rept("0",Sp2-1) . "4" . Rept("0",Sp3-1)
      rSp1 := sp4
      rSp2 := sp1
      rSp3 := sp2
      rSp4 := sp3
    }else if (L1 = 7 ) {
          retStr := "1" . Rept("0",Sp3-1) . "4" . Rept("0",Sp4-1) . "2" . Rept("0",Sp1-1) . "8" . Rept("0",Sp2-1)
     rSp1 := sp3
      rSp2 := sp4
      rSp3 := sp1
      rSp4 := sp2
}else if (L1 = 3 ) {
          retStr := "1" . Rept("0",Sp2-1) . "8" . Rept("0",Sp3-1) . "2" . Rept("0",Sp4-1) . "4" . Rept("0",Sp1-1)
      rSp1 := sp2
      rSp2 := sp3
      rSp3 := sp4
      rSp4 := sp1
      }else{
          retStr := "8" . Rept("0",Sp1-1) . "4" . Rept("0",Sp2-1) . "2" . Rept("0",Sp3-1) . "1" . Rept("0",Sp4-1)
      rSp1 := sp1
      rSp2 := sp2
      rSp3 := sp3
      rSp4 := sp4
      }
  return Rept(retStr,n)
}

Rept(String,Times)
{
  Loop, %Times%
    Output .= String
  Return Output
}

_Hex(A)
{
  return (A=1)?8:(A=3)?4:(A=7)?2:1
}

Decode_2(HexStr , Code = 1, Splitchar = "", startnum = 1) {
DeCodeStr := (Code = 1379)?"1379 1370 1309 1300 1079 1070 1009 1000 0379 0370 0309 0300 0079 0070 0009 0000 "
:(Code = 15)?"0000 000F 00F0 00FF 0F00 0F0F 0FF0 0FFF F000 F00F F0F0 F0FF FF00 FF0F FFF0 FFFF "
:"0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 "
loop % Strlen(HexStr)  {
num2 := "0x" . SubStr(HexStr,A_index ,1)
SetFormat, IntegerFast, D
if  (Splitchar = "X") {
BitStr .= A_Index+startnum-1 . "_"  . SubStr(DeCodeStr ,num2*5+1,4) . "  "
if mod(A_Index,10) = 0
BitStr .= "`r"    
      } else {
BitStr .= SubStr(DeCodeStr ,num2*5+1,4) . Splitchar
}
SetFormat, IntegerFast, hex
}
return BitStr
}

Encode_h(BitStr,Code = 1) {
        DeCodeStr := (Code = 1379)?"1379 1370 1309 1300 1079 1070 1009 1000 0379 0370 0309 0300 0079 0070 0009 0000 "
        :(Code = 15)?"0000 000F 00F0 00FF 0F00 0F0F 0FF0 0FFF F000 F00F F0F0 F0FF FF00 FF0F FFF0 FFFF "
        :"0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 "

SetFormat, IntegerFast, hex
  loop % Strlen(BitStr)//4  {
num2 .= (InStr(DeCodeStr, SubStr(BitStr,A_index*4-3,4) . " ")-1)//5
StringReplace, HexStr, num2 ,0x, ,A
}
SetFormat, IntegerFast, D
return HexStr
}
已自力除錯三回...希望可以改得更有效率..
查找这个用户的全部帖子
表示感谢 引用并回复 移动视图置页面顶端
发表回复 


论坛跳转:


联系我们 | Autohotkey 中文站 | 回到顶部 | 回到正文区 | 精简(归档)模式 | RSS 聚合