用4GL写常用算法程序 – 汉诺塔、八皇后、走迷宫
只为练代码而代码,一般这些在TIPTOP开发中用不到这些妹的^_^
–兜兜里全是糖——————————————————–
–幼儿园按如下方法依次给A，B，C，D，E五个小孩发糖果。
–将全部糖果的一半再加二分之一块糖果发给第一个小孩；
–将剩下糖果的三分之一再加三分之一块糖果发给第二个小孩；
–将剩下糖果的四分之一再加四分之一块糖果发给第三个小孩；
–将剩下糖果的五分之一再加五分之一块糖果发给第四个小孩；
–将最后剩下的11块糖果发给第五个小孩。每个小孩得到的糖果数均为整数。
–试确定原来共有多少块糖果？每个小孩各得到多少块糖果？
— 要求结果的输出格式为
— xsum＝糖果总数
— xa＝A得到的糖果数
— xb＝B得到的糖果数
— xc＝C得到的糖果数
— xd＝D得到的糖果数
— xe＝E得到的糖果数
MAIN
DEFINE xsum,xa,xb,xc,xd,xe INTEGER
LET xsum = 0
WHILE TRUE
#穷举法
#判断式(60*E的糖果数11=60*(总数-A的糖果数-B的糖果数-C的糖果数-D的糖果数))
#判别式两边同乘以最小公倍数60
IF(660=60*xsum-((xsum+1)*30+(xsum+1)*10+(xsum+1)*5+(xsum+1)*3)) THEN
EXIT WHILE
END IF
LET xsum = xsum + 1
END WHILE
LET xa = (xsum+1)/2
LET xb = ((xsum-xa)+1)/3
LET xc = ((xsum-xa-xb)+1)/4
LET xd = ((xsum-xa-xb-xc)+1)/5
LET xe = xsum-xa-xb-xc-xd
DISPLAY "xsm=",xsum USING "###"
DISPLAY "xa =",xa USING "###"
DISPLAY "xb =",xb USING "###"
DISPLAY "xc =",xc USING "###"
DISPLAY "xd =",xd USING "###"
DISPLAY "xe =",xe USING "###"
END MAIN
–10个小P孩分糖果———————————————–
— 十个小孩依次站立成一圈，手中分别有糖果数：10，2，8，22，16，4，10，6，14，20
— 然后所有的小孩将手中的糖果数1半分给右边的小孩，手中糖果数是奇数的可以向老师再要一个糖果
— 问经过几次这样的调整，每个小孩手中的糖果数一样
— 要求输出格式遵循一下格式
— 0 | 10 2 8 22 16 4 10 6 14 20 孩子手中原有的糖果数
— 1 | xx xx xx xx xx xx xx xx xx xx 第1轮各孩子手中的糖果数
— 2 | xx xx xx xx xx xx xx xx xx xx 第2轮各孩子手中的糖果数
— | ……
— n | xx xx xx xx xx xx xx xx xx xx 最后一轮各孩子手中的糖果数（应相等）
MAIN
DEFINE sweet ARRAY[10] OF INTEGER
DEFINE sweetTemp ARRAY[10] OF INTEGER
DEFINE index INTEGER
DEFINE equFlag INTEGER
DEFINE i INTEGER
DEFINE j INTEGER
LET sweet[1] = 10
LET sweet[2] = 2
LET sweet[3] = 8
LET sweet[4] = 22
LET sweet[5] = 16
LET sweet[6] = 4
LET sweet[7] = 10
LET sweet[8] = 6
LET sweet[9] = 14
LET sweet[10]= 20
LET index = -1
LET equFlag = TRUE
DISPLAY " child postion "
DISPLAY "round | P1 P2 P3 P4 P5 P6 P7 P8 P9 P10"
WHILE(equFlag)
LET index = index + 1
IF index = 0 THEN
DISPLAY "start |",
sweet[1] USING "####",sweet[2] USING "####",sweet[3] USING "####",sweet[4] USING "####",sweet[5] USING "####",
sweet[6] USING "####",sweet[7] USING "####",sweet[8] USING "####",sweet[9] USING "####",sweet[10] USING "####"
ELSE
DISPLAY " ",index USING "##"," |",
sweet[1] USING "####",sweet[2] USING "####",sweet[3] USING "####",sweet[4] USING "####",sweet[5] USING "####",
sweet[6] USING "####",sweet[7] USING "####",sweet[8] USING "####",sweet[9] USING "####",sweet[10] USING "####"
END IF
FOR i=1 TO sweet.getLength() STEP+1
IF sweet[i] MOD 2=0 THEN
LET sweet[i]=sweet[i]/2
LET sweetTemp[i]=sweet[i]
ELSE
LET sweet[i]=(sweet[i]+1)/2
LET sweetTemp[i]=sweet[i]
END IF
END FOR
FOR j=2 TO sweet.getLength() STEP+1
LET sweet[j]=sweet[j]+sweetTemp[j-1]
END FOR
LET sweet[1]=sweet[1]+sweetTemp[10]
CALL judgeEqu(sweet) RETURNING equFlag
END WHILE
LET index = index + 1
DISPLAY " ",index USING "##"," |",
sweet[1] USING "####",sweet[2] USING "####",sweet[3] USING "####",sweet[4] USING "####",sweet[5] USING "####",
sweet[6] USING "####",sweet[7] USING "####",sweet[8] USING "####",sweet[9] USING "####",sweet[10] USING "####"
END MAIN
FUNCTION judgeEqu(sweet)
DEFINE sweet ARRAY[10] OF INTEGER
DEFINE k INTEGER
FOR k=2 TO sweet.getLength() STEP+1
IF sweet[1]<>sweet[k] THEN
RETURN TRUE
END IF
END FOR
RETURN FALSE
END FUNCTION
—汉诺塔————————————————
— 将N个塔从a全部移动到c可采用递归算法实现：
— 1、 将a竿最上面的n-1个塔借助c竿从a竿移动到b竿
— 2、 将a竿最下面的最大的1个塔从a竿直接移动到c竿
— 3、 将b竿上的n-1个塔全部移动到c竿上
GLOBALS
DEFINE stepIndex INTEGER
END GLOBALS
MAIN
DEFINE n INTEGER
LET stepIndex = 0
LET n = 4 #如图此处做4个塔的移动
DISPLAY "Neddle :From_A Temp_B To_C"
#将n个塔藉助B从A移动到C
CALL moveDisc(n,'A','C','B')
DISPLAY "Step Total:",stepIndex USING "<<<<<<<<"
END MAIN
FUNCTION moveDisc(n,fromNeedle,toNeedle,tempNeedle)
DEFINE n INTEGER
DEFINE fromNeedle VARCHAR(1)
DEFINE toNeedle VARCHAR(1)
DEFINE tempNeedle VARCHAR(1)
IF n>=1 THEN
#将n-1个塔藉助toNeedle从fromNeddle移动到tempNeedle
CALL moveDisc(n-1,fromNeedle,tempNeedle,toNeedle)
LET stepIndex = stepIndex + 1
#一下CASE处理将fromNeddl上的最后一个大塔从fromNeddle直接移动到toNeedle
CASE fromNeedle
WHEN 'A'
CASE toNeedle
WHEN 'B'
DISPLAY "step:",stepIndex USING "###",n USING "#####"," -->",n USING "####"
WHEN 'C'
DISPLAY "step:",stepIndex USING "###",n USING "#####"," ----------->",n USING "####"
OTHERWISE EXIT CASE
END CASE
WHEN 'B'
CASE toNeedle
WHEN 'A'
DISPLAY "step:",stepIndex USING "###",n USING "#####"," <--",n USING "####"
WHEN 'C'
DISPLAY "step:",stepIndex USING "###"," ",n USING "#####"," -->",n USING "####"
OTHERWISE EXIT CASE
END CASE
WHEN 'C'
CASE toNeedle
WHEN 'A'
DISPLAY "step:",stepIndex USING "###",n USING "#####"," <-----------",n USING "####"
WHEN 'B'
DISPLAY "step:",stepIndex USING "###"," ",n USING "#####"," <--",n USING "####"
OTHERWISE EXIT CASE
END CASE
OTHERWISE EXIT CASE
END CASE
#将n-1个塔藉助fromNeddle从tempNeedle移动到toNeedle
CALL moveDisc(n-1,tempNeedle,toNeedle,fromNeedle)
END IF
END FUNCTION
— 八皇后问题——————————————————–
— 在一个8×8的国际棋盘上有8个皇后，每个皇后占一个棋格
— 要求皇后间不可以出现互相攻击的行为，即任两个皇后不可处在同一列或同一行或对角在线
— 求出所有8个皇后可能的位置
— 利用递归处理
— 1列 2列 3列 4列 5列 6列 7列 8列
–第1行| Ω | | | | | | | |
–第2行| | | | | | | Ω | |
–第3行| | | | | Ω | | | |
–第4行| | | | | | | | Ω |
–第5行| | Ω | | | | | | |
–第6行| | | | Ω | | | | |
–第7行| | | | | | Ω | | |
–第8行| | | Ω | | | | | |
–上面Ω表示皇后所在的位置,解可表示为queens[]={1,7,5,8,2,4,6,3},即第1行皇后的位置在1列,第2行皇后的位置在7列…
GLOBALS
DEFINE queens ARRAY[8] OF INTEGER #8个皇后的位置
DEFINE totalSolution INTEGER #解的个数
END GLOBALS
MAIN
LET totalSolution = 0
CALL searchLocation(1)
DISPLAY "8×8 Queens totalSolution:",totalSolution USING "<<<<<"
END MAIN
#递归寻找8个皇后不同的符合要求的位置
FUNCTION searchLocation(startLocation)
DEFINE startLocation INTEGER
DEFINE colIndex INTEGER
DEFINE searchIndex INTEGER
DEFINE absResult INTEGER
IF startLocation=9 THEN
LET totalSolution = totalSolution + 1
DISPLAY "queensSolution ",totalSolution USING "###",":",queens[1] USING "##",queens[2] USING "##",queens[3] USING "##",
queens[4] USING "##",queens[5] USING "##",queens[6] USING "##",queens[7] USING "##",queens[8] USING "##"
ELSE
FOR colIndex=1 TO 8 STEP + 1
LET queens[startLocation] = colIndex
FOR searchIndex=1 TO startLocation-1 STEP + 1
CALL Abs(colIndex,queens[searchIndex]) RETURNING absResult
IF(colIndex=queens[searchIndex] OR absResult=startLocation-searchIndex) THEN
LET queens[startLocation] = 0
EXIT FOR
END IF
END FOR
IF queens[startLocation]>0 THEN
CALL searchLocation(startLocation+1)
END IF
END FOR
END IF
END FUNCTION
#求两数的绝对值
FUNCTION Abs(iNum,jNum)
DEFINE iNum INTEGER
DEFINE jNum INTEGER
DEFINE result INTEGER
LET result = iNum - jNum
IF (result >= 0) THEN
RETURN result
ELSE
RETURN 0-result
END IF
END FUNCTION
–打印9×9乘法表————————————————–
MAIN
DEFINE rowIndex INTEGER
DEFINE colIndex INTEGER
DEFINE displayStr STRING
FOR rowIndex=1 TO 9 STEP+1
FOR colIndex=1 TO rowIndex STEP+1
LET displayStr = displayStr,colIndex USING "#","×",rowIndex USING "#","=",colIndex*rowIndex USING "##"," "
END FOR
DISPLAY displayStr
LET displayStr = ""
END FOR
END MAIN
–打印杨辉三角————————————–
MAIN
DEFINE level SMALLINT
DEFINE levelIndex SMALLINT
DEFINE index SMALLINT
DEFINE angleValue DYNAMIC ARRAY WITH DIMENSION 2 OF SMALLINT
DEFINE levelBlank STRING
DEFINE preBlank STRING
DEFINE disString STRING
#输入要打印的杨辉三角的行数
PROMPT "Enter YanHuiAngle Level:" FOR level
ON ACTION SHOW
DISPLAY "Show Press!"
END PROMPT
#求杨辉三角的值
FOR levelIndex=1 TO level STEP + 1
LET angleValue[levelIndex,1] = 1 #每行的第一个数值为1
LET angleValue[levelIndex,levelIndex] = 1 #每行的最后一个数值为1
IF levelIndex >2 THEN
FOR index=2 TO levelIndex-1 STEP + 1
LET angleValue[levelIndex,index] = angleValue[levelIndex-1,index-1] + angleValue[levelIndex-1,index]
END FOR
END IF
LET levelBlank = levelBlank," "
END FOR
#打印杨辉三角
FOR levelIndex=1 TO level STEP + 1
LET disString = ""
LET preBlank = levelBlank.substring(1,level-levelIndex)
LET disString = disString,preBlank
FOR index=1 TO levelIndex STEP + 1
LET disString = disString,angleValue[levelIndex,index] USING "###"
END FOR
DISPLAY disString
END FOR
END MAIN
–走迷宫——————————————————-
— 给定一个可以走通的迷宫数组图,%表示入口,@表示出口,#表示墙壁,空白的地方表示此路可以通入
— 找出走出迷宫的所有路径及最短路劲
— 迷宫数组如下,共计10行51列
GLOBALS
DEFINE mazeString STRING #迷宫图字符串
DEFINE mazeArray DYNAMIC ARRAY WITH DIMENSION 2 OF CHAR #迷宫数组图
DEFINE mazeFlag DYNAMIC ARRAY WITH DIMENSION 2 OF CHAR #迷宫是否走过的标志
DEFINE mazeMinFlag DYNAMIC ARRAY WITH DIMENSION 2 OF CHAR #迷宫最优解标志
DEFINE mazeSolution INTEGER #走出迷宫解的个数
DEFINE mazeWalkLen INTEGER #走出迷宫最短路劲长度
END GLOBALS
MAIN
DEFINE mazeIndex SMALLINT #迷宫阵字符串索引
DEFINE mazeRowIndex SMALLINT #迷宫数组图行索引
DEFINE mazeColIndex SMALLINT #迷宫数组图列索引
DEFINE inLocationRow SMALLINT #迷宫入口行位置
DEFINE inLocationCol SMALLINT #迷宫入口列位置
DEFINE bestDisplay STRING #打印最优解
LET mazeWalkLen = 2147483647 #最短路劲初始为INTEGER的最大值
LET mazeSolution = 0
LET mazeString = "###################################################",
"% ## #### ### ### # ####",
"# ## # ### ### ###### ### ############ # # #",
"# ## ## ### ## ## # # ## # # ####",
"# # # ## ## ### # # ######### # # # ##",
"# # # # ## ########## #### ## # #",
"# ## ### ## ## ### #### ## ## # # ######### #",
"# # # ## ## # ## #### # # ## ####",
"#### ## #### #### ## # ### ## ## @",
"###################################################"
#生成迷宫数组图,并找出迷宫入口位置
FOR mazeIndex=1 TO mazeString.getLength() STEP + 1
IF mazeIndex MOD 51 = 0 THEN
LET mazeRowIndex = mazeIndex/51
LET mazeColIndex = 51
ELSE
LET mazeRowIndex = mazeIndex/51+1
LET mazeColIndex = mazeIndex MOD 51
END IF
LET mazeArray[mazeRowIndex,mazeColIndex]=mazeString.getCharAt(mazeIndex)
IF mazeString.getCharAt(mazeIndex) = '%' THEN
LET inLocationRow = mazeRowIndex #保存迷宫的入口行位置
LET inLocationCol = mazeColIndex #保存迷宫的入口列位置
END IF
END FOR
#迷宫是否走过的标志初始为' ',即全都没有走过
FOR mazeRowIndex=1 TO 10 STEP + 1
FOR mazeColIndex=1 TO 51 STEP + 1
LET mazeFlag[mazeRowIndex,mazeColIndex]=' '
END FOR
END FOR
#从入口位置开始搜索路径
CALL walkSearch(inLocationRow,inLocationCol)
#打印最优解
DISPLAY "The Best mazeSolution Using Step:",mazeWalkLen USING "<<<<<<<<<<"
FOR mazeRowIndex=1 TO 10 STEP + 1
LET bestDisplay = ""
FOR mazeColIndex=1 TO 51 STEP + 1
IF(mazeArray[mazeRowIndex,mazeColIndex]='#')THEN
LET bestDisplay = bestDisplay,'#'
ELSE
IF(mazeMinFlag[mazeRowIndex,mazeColIndex]=' ')THEN
LET bestDisplay = bestDisplay,' '
ELSE
CASE mazeMinFlag[mazeRowIndex,mazeColIndex]
WHEN 'U'
LET bestDisplay = bestDisplay,'↑'
WHEN 'D'
LET bestDisplay = bestDisplay,'↓'
WHEN 'L'
LET bestDisplay = bestDisplay,'←'
WHEN 'R'
LET bestDisplay = bestDisplay,'→'
OTHERWISE EXIT CASE
END CASE
END IF
END IF
END FOR
DISPLAY bestDisplay
END FOR
END MAIN
#判断迷宫数组图当前位置是否已经走出迷宫,如果没有则继续寻走
FUNCTION walkSearch(mazeRowIndex,mazeColIndex)
DEFINE mazeRowIndex SMALLINT #迷宫数组图当前行
DEFINE mazeColIndex SMALLINT #迷宫数组图当前列
DEFINE dircString STRING #搜索方向
DEFINE dircIndex SMALLINT #搜索方向索引
DEFINE mazeUDLRFlag SMALLINT #返回值:TRUE-->可以走,FALSE-->不可以走
LET dircString = "UDLR" #定义 U上D下L左R右 搜索方向
#如果找到出口标志@,则遍历的结果已经走出迷宫,打印出走迷宫的路线图
IF(mazeArray[mazeRowIndex,mazeColIndex]='@')THEN
CALL displayMaze()
#否则递推遍历当前位置的U上D下L左R右方向可行的通路
ELSE
FOR dircIndex=1 TO dircString.getLength() STEP + 1
CALL judgeFlag(mazeRowIndex,mazeColIndex,dircString.getCharAt(dircIndex)) RETURNING mazeUDLRFlag
IF(mazeUDLRFlag)THEN
LET mazeFlag[mazeRowIndex,mazeColIndex]=dircString.getCharAt(dircIndex)
CASE dircString.getCharAt(dircIndex)
WHEN 'U'
CALL walkSearch(mazeRowIndex-1,mazeColIndex)
WHEN 'D'
CALL walkSearch(mazeRowIndex+1,mazeColIndex)
WHEN 'L'
CALL walkSearch(mazeRowIndex,mazeColIndex-1)
WHEN 'R'
CALL walkSearch(mazeRowIndex,mazeColIndex+1)
OTHERWISE EXIT CASE
END CASE
END IF
END FOR
#如果当前的位置没有被遍历过
#或是当前位置曾今被遍历过但是之后的路线是死路则回溯
#则将该位置重置为' ',表示该位置目前还没有被遍历搜索过
LET mazeFlag[mazeRowIndex,mazeColIndex]=' '
END IF
END FUNCTION
#判断迷宫数组图当前位置朝上下左右方向是否可走
FUNCTION judgeFlag(mazeRowIndex,mazeColIndex,mazeDirction)
DEFINE mazeRowIndex SMALLINT #迷宫数组图当前行
DEFINE mazeColIndex SMALLINT #迷宫数组图当前列
DEFINE mazeDirction CHAR #迷宫当前位置向mazeDirction(U:上,D:下,L:左,R:右)方向是否可通入
DEFINE mazeUDLRFlag SMALLINT #返回值:TRUE-->可以走,FALSE-->不可以走
CASE mazeDirction
WHEN 'U' #判断当前位置朝上是否可走
IF(mazeRowIndex>=2)THEN
IF(mazeFlag[mazeRowIndex-1,mazeColIndex]=' '
AND(mazeArray[mazeRowIndex-1,mazeColIndex]=' ' OR mazeArray[mazeRowIndex-1,mazeColIndex]='@')
)THEN LET mazeUDLRFlag = TRUE
ELSE LET mazeUDLRFlag = FALSE
END IF
ELSE LET mazeUDLRFlag = FALSE
END IF
WHEN 'D' #判断当前位置朝下是否可走
IF(mazeRowIndex<=9)THEN
IF(mazeFlag[mazeRowIndex+1,mazeColIndex]=' '
AND(mazeArray[mazeRowIndex+1,mazeColIndex]=' ' OR mazeArray[mazeRowIndex+1,mazeColIndex]='@')
)THEN LET mazeUDLRFlag = TRUE
ELSE LET mazeUDLRFlag = FALSE
END IF
ELSE LET mazeUDLRFlag = FALSE
END IF
WHEN 'L' #判断当前位置朝左是否可走
IF(mazeColIndex>=2)THEN
IF(mazeFlag[mazeRowIndex,mazeColIndex-1]=' '
AND(mazeArray[mazeRowIndex,mazeColIndex-1]=' ' OR mazeArray[mazeRowIndex,mazeColIndex-1]='@')
)THEN LET mazeUDLRFlag = TRUE
ELSE LET mazeUDLRFlag = FALSE
END IF
ELSE LET mazeUDLRFlag = FALSE
END IF
WHEN 'R' #判断当前位置朝右是否可走
IF(mazeColIndex<=50)THEN
IF(mazeFlag[mazeRowIndex,mazeColIndex+1]=' '
AND(mazeArray[mazeRowIndex,mazeColIndex+1]=' ' OR mazeArray[mazeRowIndex,mazeColIndex+1]='@')
)THEN LET mazeUDLRFlag = TRUE
ELSE LET mazeUDLRFlag = FALSE
END IF
ELSE LET mazeUDLRFlag = FALSE
END IF
OTHERWISE EXIT CASE
END CASE
RETURN mazeUDLRFlag
END FUNCTION
#打印迷宫通路
FUNCTION displayMaze()
DEFINE displayString STRING
DEFINE mazeRowIndex SMALLINT #迷宫数组图行索引
DEFINE mazeColIndex SMALLINT #迷宫数组图列索引
DEFINE mazeStep INTEGER #搜索迷宫走了多少步
LET mazeStep = 0
LET mazeSolution = mazeSolution + 1
#DISPLAY "mazeSolution:",mazeSolution USING "<<<<<<<<<<"
FOR mazeRowIndex=1 TO 10 STEP + 1
LET displayString = ""
FOR mazeColIndex=1 TO 51 STEP + 1
IF(mazeArray[mazeRowIndex,mazeColIndex]='#')THEN
LET displayString = displayString,'#'
ELSE
IF(mazeFlag[mazeRowIndex,mazeColIndex]=' ')THEN
LET displayString = displayString,' '
ELSE
LET mazeStep = mazeStep + 1 #记录当前走了多少步
CASE mazeFlag[mazeRowIndex,mazeColIndex]
WHEN 'U'
LET displayString = displayString,'↑'
WHEN 'D'
LET displayString = displayString,'↓'
WHEN 'L'
LET displayString = displayString,'←'
WHEN 'R'
LET displayString = displayString,'→'
OTHERWISE EXIT CASE
END CASE
END IF
END IF
END FOR
DISPLAY displayString
END FOR
DISPLAY "This ",mazeSolution USING "<<<<"," mazeSolution Using Step:",mazeStep USING "<<<<<<<<<<"
#记录最优解
IF(mazeStep<mazeWalkLen)THEN
LET mazeWalkLen = mazeStep
FOR mazeRowIndex=1 TO 10 STEP + 1
FOR mazeColIndex=1 TO 51 STEP + 1
LET mazeMinFlag[mazeRowIndex,mazeColIndex] = mazeFlag[mazeRowIndex,mazeColIndex]
END FOR
END FOR
END IF
END FUNCTION
转载请注明：赫非域 » 用4GL写常用算法程序 – 汉诺塔、八皇后、走迷宫