{VERSION 2 3 "DEC ALPHA UNIX" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "On reprend la version de l 'exercice precedent, a titre de comparaison." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 97 "L2:=[1, 2, 3, 7, 12, 21, 29, 38, 43, 47, 48, 49, 51, 52, 53, 57, 62, 71, 79, 88, 93, 97, 98, 99];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#L2G7:\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#H\"#Q\"#V\"#Z\" #[\"#\\\"#^\"#_\"#`\"#d\"#i\"#r\"#z\"#))\"#$*\"#(*\"#)*\"#**" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 235 "is149_2:=proc(n)\n local r ,s;\n r:=n;\n while r<>0 do\n s:=irem(r,100,'r');\n if not (me mber(s,\{11,14,19,41,44,49,91,94,99\})\n or \n ( member(s,\{1,4,9\}) and r=0)) then\n RETURN(false)\n fi\n od; \n true\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 232 "tricol_2 :=proc(N)\n local k,res,q,r,n,i;\n global L2;\n k:=0;\n for q from 0 by 100 while k " 0 "" {MPLTEXT 1 0 42 "start:=time():\ntricol_2(12);\ntime()-start;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q\"$2\"\"$7#\"&)[J\"& 2,(\"')G(Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&Ol'!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Ensuite, c'est trop long." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "On ameliore. On met la largeur de la tran che en parametre." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "slices ize:=4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*slicesizeG\"\"%" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "On construit les mots de longueur \+ inferieure ou egale a slicesize sur l'alphabet \{1,4,9\}." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 "QQ contient les mots de longueur stricte ment plus petite que slicesize.\nQ contient les mots de longueur exact ement slicesize." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "WW0:=\{ []\}:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 344 "for s to slicesiz e do \n WW.s:=map(proc(L)\n local s,i;\n \+ s:=op(L);\n [s,1],[s,4],[s,9]\n end,WW.(s-1)) ;\n LL.s:=map(proc(l) \n local i;\n add(l[i ]*10^(i-1),i=1..nops(l))\n end,WW.s)\nod:\nQQ.slicesize:=\{ seq(op(LL.s),s=1..slicesize-1)\};\nQ.slicesize:=LL.slicesize;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%$QQ4G \"#T\"#W\"#\\\"#\"*\"#%*\"#**\"$6\"\"$9\"\"$>\"\"$T\"\"$W\"\"$\\\"\"$9 %\"$W%\"$%\\\"$9*\"$%**\"$>%\"$>*\"$\">\"$6%\"$\"\\\"$6*\"$T*\"$\"**\" $\\%\"$W*\"$***\"$\\*\"$T%\"$%>\"$*>\"$*\\" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#Q4G<]p\"%\\9\"%\">\"\"%\"\\\"\"%\"*>\"%\">%\"%\"\\% \"%\"*\\\"%\">*\"%\"\\*\"%\"***\"%%>\"\"%%\\\"\"%%*>\"%%>%\"%%\\%\"%%* \\\"%%>*\"%%\\*\"%%***\"%9W\"%9\\\"%9\"*\"%9%*\"%9**\"%>6\"%>9\"%>>\"% >T\"%>W\"%>\\\"%>\"*\"%>%*\"%>**\"%T6\"%T>\"%TT\"%T\\\"%T\"*\"%T**\"%W 6\"%W>\"%WW\"%W\"*\"%W**\"%9>\"%9T\"%66\"%69\"%6>\"%6T\"%6W\"%6\\\"%6 \"*\"%6%*\"%6**\"%96\"%99\"%TW\"%WT\"%*>\"\"%\\6\"%*\\\"\"%**>\"%\\>\" %\\%*\"%W9\"%*\\%\"%*>%\"%\\T\"%****\"%\\W\"%**\\\"%\\\\\"%T%*\"%T9\"% W%*\"%\\\"*\"%*\\*\"%*>*\"%\\**\"%W\\" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 104 "On cherche les residus modulo 10^slicesize des motifs pr ecedents; on les ordonne et on les range dans L." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 116 "L.slicesize:=sort(map2(op,2,map(op,\n [seq( msolve(r^2=d,10^slicesize),\n d=QQ.slicesize union Q.slicesize)] )));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#L4G7dt\"\"\"\"\"#\"\"$\"\"( \"#7\"#@\"#Q\"$2\"\"$V\"\"$7#\"$$R\"$z%\"$@&\"$Q&\"$H(\"$r(\"$)y\"$d) \"%75\"%z6\"%H7\"%\\7\"%`7\"%d7\"%d8\"%$R\"\"%)[\"\"%V;\"%7<\"%H<\"%i> \"%@?\"%2@\"%)G#\"%HC\"%iC\"%)[#\"%)\\#\"%-D\"%7D\"%QD\"%rD\"%7F\"%$*G \"%zH\"%QI\"%rK\"%)G$\"%dL\"%7N\"%2O\"%VO\"%VP\"%ZP\"%^P\"%rP\"%@Q\"%) )R\"%VT\"%7U\"%HU\"%rU\"%iW\"%zW\"%@X\"%2Y\"%)y%\"%d[\"%$*[\"%i\\\"%z \\\"%))\\\"%$*\\\"%(*\\\"%)*\\\"%**\\\"%,]\"%-]\"%.]\"%2]\"%7]\"%@]\"% Q]\"%2^\"%V^\"%7_\"%$R&\"%za\"%@b\"%Qb\"%Hd\"%rd\"%)y&\"%de\"%7g\"%zh \"%Hi\"%\\i\"%`i\"%di\"%dj\"%$R'\"%)['\"%Vm\"%7n\"%Hn\"%ip\"%@q\"%2r\" %)G(\"%Hu\"%iu\"%)[(\"%)\\(\"%-v\"%7v\"%Qv\"%rv\"%7x\"%$*y\"%zz\"%Q!) \"%r#)\"%)G)\"%d$)\"%7&)\"%2')\"%V')\"%V()\"%Z()\"%^()\"%r()\"%@))\"%) )*)\"%V\"*\"%7#*\"%H#*\"%r#*\"%i%*\"%z%*\"%@&*\"%2'*\"%)y*\"%d)*\"%$*) *\"%i**\"%z**\"%))**\"%$***\"%(***\"%)***\"%****" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 69 "On ecrit une procedure de selection dependant du p arametre slicesize." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 310 "is1 49_.slicesize:=eval(subs(_Q=Q.slicesize,_QQ=QQ.slicesize,_slicesize=sl icesize,\nproc(n::posint)\n local r,s;\n r:=n;\n while r<>0 do\n \+ s:=irem(r,10^_slicesize,'r');\n if not (member(s,_Q)\n \+ or \n (member(s,_QQ) and r=0)\n ) then\n RET URN(false)\n fi\n od;\n true\nend));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(is149_4G:6#'%\"nG%'posintG6$%\"rG%\"sG6\"F-C%>8$9$?( F-\"\"\"F3F-0F0\"\"!C$>8%-%%iremG6%F0\"&++\".F0@$45-%'memberG6$F8<]p\" %\\9\"%\">\"\"%\"\\\"\"%\"*>\"%\">%\"%\"\\%\"%\"*\\\"%\">*\"%\"\\*\"% \"***\"%%>\"\"%%\\\"\"%%*>\"%%>%\"%%\\%\"%%*\\\"%%>*\"%%\\*\"%%***\"%9 W\"%9\\\"%9\"*\"%9%*\"%9**\"%>6\"%>9\"%>>\"%>T\"%>W\"%>\\\"%>\"*\"%>%* \"%>**\"%T6\"%T>\"%TT\"%T\\\"%T\"*\"%T**\"%W6\"%W>\"%WW\"%W\"*\"%W**\" %9>\"%9T\"%66\"%69\"%6>\"%6T\"%6W\"%6\\\"%6\"*\"%6%*\"%6**\"%96\"%99\" %TW\"%WT\"%*>\"\"%\\6\"%*\\\"\"%**>\"%\\>\"%\\%*\"%W9\"%*\\%\"%*>%\"% \\T\"%****\"%\\W\"%**\\\"%\\\\\"%T%*\"%T9\"%W%*\"%\\\"*\"%*\\*\"%*>*\" %\\**\"%W\\3-FB6$F8\"#T\"#W\"#\\\"#\"*\"#%* \"#**\"$6\"\"$9\"\"$>\"\"$T\"\"$W\"\"$\\\"\"$9%\"$W%\"$%\\\"$9*\"$%** \"$>%\"$>*\"$\">\"$6%\"$\"\\\"$6*\"$T*\"$\"**\"$\\%\"$W*\"$***\"$\\*\" $T%\"$%>\"$*>\"$*\\/F0F5-%'RETURNG6#%&falseG%%trueGF-F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "On ecrit la procedure de generation des \+ mots tricolores ou le test est base sur les motifs de taille slicesize pour les poids faibles." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 440 "tricol_.slicesize:=subs(_L=L.slicesize,\n \+ _slicesize=slicesize,\n _is149=is149_.slicesize ,\nproc(N::posint)\n local k,res,q,r,n,i;\n k:=0;\n for q from 0 by 10^_slicesize while k%)tricol_4G:6#'%\"NG%'posintG6(%\"kG%$resG%\"qG%\"rG% \"nG%\"iG6\"F1C%>8$\"\"!?(8&F5\"&++\"F12F49$C$-%)userinfoG6&\"\"$9!%+t esting~q=GF7?&8'7dt\"\"\"\"\"#F?\"\"(\"#7\"#@\"#Q\"$2\"\"$V\"\"$7#\"$$ R\"$z%\"$@&\"$Q&\"$H(\"$r(\"$)y\"$d)\"%75\"%z6\"%H7\"%\\7\"%`7\"%d7\"% d8\"%$R\"\"%)[\"\"%V;\"%7<\"%H<\"%i>\"%@?\"%2@\"%)G#\"%HC\"%iC\"%)[#\" %)\\#\"%-D\"%7D\"%QD\"%rD\"%7F\"%$*G\"%zH\"%QI\"%rK\"%)G$\"%dL\"%7N\"% 2O\"%VO\"%VP\"%ZP\"%^P\"%rP\"%@Q\"%))R\"%VT\"%7U\"%HU\"%rU\"%iW\"%zW\" %@X\"%2Y\"%)y%\"%d[\"%$*[\"%i\\\"%z\\\"%))\\\"%$*\\\"%(*\\\"%)*\\\"%** \\\"%,]\"%-]\"%.]\"%2]\"%7]\"%@]\"%Q]\"%2^\"%V^\"%7_\"%$R&\"%za\"%@b\" %Qb\"%Hd\"%rd\"%)y&\"%de\"%7g\"%zh\"%Hi\"%\\i\"%`i\"%di\"%dj\"%$R'\"%) ['\"%Vm\"%7n\"%Hn\"%ip\"%@q\"%2r\"%)G(\"%Hu\"%iu\"%)[(\"%)\\(\"%-v\"%7 v\"%Qv\"%rv\"%7x\"%$*y\"%zz\"%Q!)\"%r#)\"%)G)\"%d$)\"%7&)\"%2')\"%V') \"%V()\"%Z()\"%^()\"%r()\"%@))\"%))*)\"%V\"*\"%7#*\"%H#*\"%r#*\"%i%*\" %z%*\"%@&*\"%2'*\"%)y*\"%d)*\"%$*)*\"%i**\"%z**\"%))**\"%$***\"%(***\" %)***\"%****%%trueG@$-%(is149_4G6#*$,&F7FEFCFEFFC%>F4,&F4FEFEFE>&8%6#F 4F\\w-F=6%FFF@Faw7#-%$seqG6$&Fbw6#8)/F\\x;FEF:F1F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "On teste." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "infolevel[tricol_.slicesize]:=3:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "start:=time():\ntricol_.slicesize(10);\ntime()-start; " }}{PARA 6 "" 1 "" {TEXT -1 270 "tricol_4: testing q= 0\ntricol_4 : 1\ntricol_4: 2\ntricol_4: 3\ntricol_4: 7\ntricol_4: 12\ntr icol_4: 21\ntricol_4: 38\ntricol_4: 107\ntricol_4: 212\ntricol _4: testing q= 10000\ntricol_4: testing q= 20000\ntricol_4: \+ testing q= 30000\ntricol_4: 31488" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7,\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q\"$2\"\"$7#\"&)[J" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#$\"$G(!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "infolevel[tricol_.slicesize]:=1:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 13 "slicesize:=6;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*slicesizeG\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 344 "for s to slicesize do \n WW.s:=map(proc(L)\n loc al s,i;\n s:=op(L);\n [s,1],[s,4],[s,9]\n \+ end,WW.(s-1));\n LL.s:=map(proc(l) \n local i; \n add(l[i]*10^(i-1),i=1..nops(l))\n end,WW.s) \nod:\nQQ.slicesize:=\{seq(op(LL.s),s=1..slicesize-1)\}:\nQ.slicesize: =LL.slicesize:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 120 "L.slices ize:=sort(map2(op,2,map(op,\n [seq(msolve(r^2=d,10^slicesize),\n \+ d=QQ.slicesize union Q.slicesize)]))):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 368 "is149_.slicesize:=eval(subs(_Q=Q.slicesize,\n \+ _QQ=QQ.slicesize,\n \+ _slicesize=slicesize,\nproc(n::posint)\n local r,s;\n r:=n;\n wh ile r<>0 do\n s:=irem(r,10^_slicesize,'r');\n if not (member(s,_ Q)\n or \n (member(s,_QQ) and r=0)\n ) then\n RETURN(false)\n fi\n od;\n true\nend)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 440 "tricol_.slicesize:=subs(_L=L.slice size,\n _slicesize=slicesize,\n \+ _is149=is149_.slicesize,\nproc(N::posint)\n local k,res,q,r,n ,i;\n k:=0;\n for q from 0 by 10^_slicesize while k " 0 "" {MPLTEXT 1 0 51 "start:=time():\ntric ol_.slicesize(10);\ntime()-start;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7 ,\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q\"$2\"\"$7#\"&)[J" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#$\"%,K!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "start:=time():\ntricol_.slicesize(12);\ntime()-start;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q\"$2\"\"$7# \"&)[J\"&2,(\"')G(Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%NG!\"$" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Revenons en arriere." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "start:=time():\ntricol_4(12);\ntime ()-start;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"\"\"\"\"#\"\"$\"\"(\" #7\"#@\"#Q\"$2\"\"$7#\"&)[J\"&2,(\"')G(Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%wt!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 150 "Bilan: pour \+ les tailles 2, 4, 6 on a respectivement 66, 7 et 3 secondes pour N=12. \nLe gain est clair, mais le pretraitement est de plus en plus long. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "Pour la taille 6, on n'atte int pas N=14. Si on passe a la taille 8, le pretraitement devient exce ssivement long." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "On passe a une version dynamique." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1603 "tr icol:=proc(N::posint)\n local res,k,A,AA,oldQ,newQ,newL,\n sli cesize,oldL,is149,qq,q,l,r,n,n2,\n tail,newT,i,j,st;\n st:=tim e();\n res[1]:=1;\n res[2]:=2;\n res[3]:=3;\n res[4]:=7;\n res[5] :=12;\n res[6]:=21;\n res[7]:=38;\n k:=7;\n A:=\{1,4,9\};\n AA:= \{11,14,19,41,44,49,91,94,99\};\n oldQ:=A;\n newQ:=AA;\n newL:=[1,2 ,3,7,12,21,29,38,43,47,48,49,51,52,53,\n 57,62,71,79,88,93,97 ,98,99];\n for slicesize from 2 by 2 while k0 do\n s:=irem(r,10^ _slicesize,'r');\n if not (member(s,_newQ)\n or \n (member(s,_oldQ) and r=0)\n ) then\n \+ RETURN(false)\n fi\n od; \n true\n end);\n for \+ qq to 99 while k " 0 "" {MPLTEXT 1 0 21 "infolevel[tricol]:=2:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "start:=time():\ntricol(12); \ntime()-start;" }}{PARA 6 "" 1 "" {TEXT -1 271 "tricol: slicesize= \+ 2\ntricol: 8 107\ntricol: time= .12e-1\ntricol: 9 212\nt ricol: time= .44e-1\ntricol: slicesize= 4\ntricol: 10 3148 8\ntricol: time= 2.031\ntricol: 11 70107\ntricol: time= 2. 635\ntricol: 12 387288\ntricol: time= 5.318" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7.\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q\"$2\"\"$7#\"&)[J \"&2,(\"')G(Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%Ne!\"$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "start:=time():\ntricol(14); \ntime()-start;" }}{PARA 6 "" 1 "" {TEXT -1 422 "tricol: slicesize= \+ 2\ntricol: 8 107\ntricol: time= .12e-1\ntricol: 9 212\nt ricol: time= .39e-1\ntricol: slicesize= 4\ntricol: 10 3148 8\ntricol: time= 1.669\ntricol: 11 70107\ntricol: time= 2. 282\ntricol: 12 387288\ntricol: time= 5.358\ntricol: slicesi ze= 6\ntricol: 13 95610729\ntricol: time= 105.239\ntricol: \+ slicesize= 8\ntricol: 14 446653271\ntricol: time= 654.728" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#70\"\"\"\"\"#\"\"$\"\"(\"#7\"#@\"#Q \"$2\"\"$7#\"&)[J\"&2,(\"')G(Q\")H2h&*\"*rKlY%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"'/rm!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "infolevel[tricol]:=1:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "start:=time():\ntricol(16);\ntime()-start;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "38 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }