希尔法排序.doc

希尔法排序 1、输入n个数到a(n)，用希尔法对a(n)进行从大到小的排序。算法：(1) 建立数组a(n)(2) 取初始增量d=int(n/2);(3) 从第一个数开始，把相隔为d的数分为一组，对每一组用插入法排序(4) 取增量为上一个增量的一半d=int(d/2);(5) 判断:若d0则完成排序，输出结果；否则转(3)。CLSDATA 48,36,65,99,74,42,48,31,92,5INPUT n=; nDIM a(n)FOR i = 1 TO n: READ a(i): NEXT iPRINT paixuqian:;FOR i = : NEXT i: PRINTd = INT(n / 2)WHILE d = 1FOR i = d + 1 TO n STEP da(0) = a(i): j = i - dWHILE a(0) a(j)a(j + d) = a(j): j = j - dIF j 30 THEN flag1 = 1FOR i = 1 TO ly$ = MID$(x$, i, 1)IF y$ 9 THEN flag2 = 1NEXT iLOOP UNTIL flag1 = 0 AND flag2 = 0FOR i = 1 TO ly$ = MID$(x$, i, 1): a(VAL(y$) = a(VAL(y$) + 1NEXT ii = 1WHILE a(i) = 0i = i + 1WENDPRINT LTRIM$(STR$(i); : a(i) = a(i) - 1FOR j = 0 TO 9IF a(j) 0 THEN FOR k = : NEXT kNEXT jPRINTEND灵活的字符串3、第十三界世界杯足球赛进入前八名的国家有： ARGENTINE(阿根廷) ENGLAND(英格兰) SPAIN(西班牙) BELGIUM(比利时) GERMANY(德国) MEXICO(墨西哥) FRANCE(法国) BRAZIL(巴西)这八个国家的英文名称藏在如下一个字块中： A M U I G L E B P P R W Y U V W R Q W V G S T E X A R Q N Q E C Y M Z Y H O R N N Z E I N W P A G L T X L A 需要设计一个程序查找这八个国名的第一个字 J R M L K J I L M 母所在的行、列号以及字母走向。字母走向规定为 F S P A I N C N R 八个方向，分别用八个字符串加以标注，如下图1， A K W N G F O I E 在打印查找结果时，需按国名字符串的先后顺序来 B P J D C D E H G 输出查找结果。输出格式规定为： NAME(国名) ROW(行) COL(列) DIRECTION(走向) ARGENTINE 1 1 DOWNRIGHT BELGIUM 1 8 LEFT. . . . . . .算法分析: (1) 建立数组a$(8)，b$(11), c$(8)，m1(8), m2(8)。(2) 对数组s$进行从小到大的排序。(3) 循环:k从1到8，反复执行:循环:从字块的(i,j+1)对应位置上查找第k个国家的字符；(i=1,2,10；j=1,2,9)若mid$(b$(i),j+1,1)=mid$(a$(k),l,1)则循环:从八个方向(l1,2,8)，搜索a$(k)h记录搜索的字符串长度,i1和j1记录在某一搜索方向的下标若hlen(a$(k)则匹配成功，输出首字符位置(i,j)和字母走向c$(k).否则，若mid$(b$(i1),j1,1)mid$(a$(k),h,1)则跳出循环，表示该方向匹配不成功。CLSDIM a$(10), b$(11), c$(8), m1(8), m2(8)DATA *amuiglebp*,*prwyuvwrq*,*wvgstexar*,*qnqecymzy*,*hornnzein*DATA *wpagltxla*,*jrmlkjilm*,*fspaincnr*,*akwngfoie*,*bpjdcdehg*DATAargentine,england,spain,belgium,germany,mexico,france,braziDATA 1,0,-1,-1,-1,0,1,1DATA -1,-1,-1,0,1,1,1,0DATA upright,up,upleft,left,dowmleft,down,downright,rightb$(0) = STRING$(11, *): b$(11) = b$(0)FOR i = 1 TO 10: READ b$(i): NEXTFOR i = 1 TO 8: READ a$(i): NEXTFOR i = 1 TO 8: READ m2(i): NEXTFOR i = 1 TO 8: READ m1(i): NEXTFOR i = 1 TO 8: READ c$(i): NEXTPRINT name; TAB(15); row; TAB(20); col; TAB(25); directionFOR i = 1 TO 7FOR j = i + 1 TO 8IF a$(i) a$(j) THEN SWAP a$(i), a$(j)NEXT j, iFOR k = 1 TO 8FOR i = 1 TO 10FOR j = 1 TO 9IF MID$(b$(i), j + 1, 1) = MID$(a$(k), 1, 1) THENFOR l = 1 TO 8h = 1: i1 = i: j1 = j + 1WHILE h LEN(a$(k) THENPRINT a$(k); TAB(15); i; TAB(20); j; TAB(25); c$(l)END IFNEXT lEND IFNEXT jNEXT iNEXT kEND一题多解4、这里有21张卡片，其上的号码是1-21，它们的位置是以特殊位置围成一圈，如图所示：这些卡片代表老鼠，你从任何一张卡片开始，并把这张开始的卡片作为“1”，按顺时针方向数1，2，3,等等。当你数到某张卡片上的号数与你数的数一致，就算你捉到一只老鼠，然后拿走这张卡片，再从紧接着的下一张卡片开始数1，2，3,试着再一次捉到一只。比如你从18开始，数1，2，3,你首先捉到的是19张卡片，拿走19张卡片，接着下一张卡片是21，从21开始数1，2，3,逮住的是10，拿走10号卡片，接着再次捉到的是1，拿走1，再如此捉下去，如果有一次你数到21还捉不到任何一只时，你就算失败了，因为卡片上最大的数不可能是22。现在，理想结果是逮住所有这21只老鼠，如果求得2次实验就得成功，按上图的顺序是不可能的。必须改变次序，既在开始前改变某二张卡片的位置。请找出几种卡片互换的位置的方法，使你仅捉21次，便逮住所有21只老鼠。当然还必须找到正确的开始点。(注意:必须在开始前交换一次二张卡片的位置)。解法(1):CLSDIM a(21), b(21)FOR n = 1 TO 21READ a(n)NEXT nFOR i = 1 TO 20FOR j = i TO 21FOR n = 1 TO 21b(n) = a(n)NEXT nm = b(i): b(i) = b(j): b(j) = mGOSUB 100NEXT jNEXT iEND100 k = 0: d = 0105 FOR l = 1 TO 21IF b(l) = 0 THEN 155k = k + 1IF k = 22 THEN 165IF k = b(l) THEN 135GOTO 155135 b(l) = 0k = 0: d = d + 1IF d = 21 THEN 200155 NEXT lGOTO 105165 RETURN200 PRINT a (; i; ) =; a(i), a (; j; ) =; a(j)ENDDATA 19,21,5,18,8,11,16,9,12,4,10,1,14,15,17,3,7,13,6,20,2解法(2):CLSDIM a(21), b(21)FOR i = 1 TO 21: READ a(i): b(i) = a(i): NEXT iDATA 19,21,5,18,8,11,16,9,12,4,10,1,14,15,17,3,7,13,6,20,2FOR a = 2 TO 20FOR b = 1 + a TO 21FOR i = 1 TO 21: b(i) = a(i): NEXT iSWAP b(a), b(b)n = 0: s = 02 FOR i = 1 TO 21IF b(i) = 0 THEN 1n = n + 1IF b(i) = n THEN b(i) = 0: n = 0: s = s + 1IF s = 21 THEN PRINT a(; a; )=; a(a), b(; b; )=; a(b): ENDIF n = 22 THEN 31 NEXT iIF s 21 THEN 23 NEXT b, a解法(3):CLSDIM a(21), b(21)FOR i = 1 TO 21READ a(i)NEXT iDATA 19,21,5,18,8,11,16,9,12,4,10,1,14,15,17,3,7,13,6,20,2FOR i = 1 TO 20FOR j = i + 1 TO 21FOR o = 1 TO 21b(o) = a(o)NEXT oSWAP b(i), b(j): GOSUB 3NEXT j, iEND3 k = 0: w = 06 FOR q = 1 TO 21IF b(q) = 0 THEN 2k = k + 1: IF b(q) = k THEN b(q) = 0: k = 0: w = w + 1IF k = 22 THEN 4IF w = 21 THEN PRINT i; a(i), j; a(j): GOTO 42 NEXT qIF w 21 THEN 64 RETURN解法(4):CLSDIM a(20), b(20)DATA 19,21,5,18,8,11,16,9,12,4,10,1,14,15,17,3,7,13,6,20,2FOR i = 0 TO 20: READ a(i): NEXT iFOR i = 0 TO 19FOR j = i + 1 TO 20s = 0: m = 0SWAP a(i), a(j)GOSUB 1NEXT jNEXT iEND1 FOR k = 0 TO 20IF a(k) = 0 THEN 4m = m + 1IF m = a(k) THEN a(k) = 0: m = 0: s = s + 1IF m = 21 THEN GOTO 2IF s = 21 THEN PRINT (; i + 1; ), (; j + 1; ): END4 NEXT kIF s 21 THEN 12 RESTOREFOR n = 0 TO 20: READ a(n): NEXT nRETURN5、输入三个自然数N，I，J（1=