主题:求助啊!
剑圣风暴
[专家分:450] 发布于 2008-07-16 20:17:00
输入一任意长度的整数,找出其中所有回文数(不含回文数中的子回文数),并输出个数。
答出来的分不是问题。
回复列表 (共2个回复)
沙发
Mato完整版 [专家分:1270] 发布于 2008-07-16 21:19:00
我的算法:(不知道对不对)
由于不含回文数中的子回文数,因此以同一位置开头的回文数中,最多只有一个是符合要求的,并且这个回文数是最长的。
(举个例子:“122332222332212”这个整数中,以第二个数“2”开头的回文数有2、22、223322、223322223322,其中只有最后一个是符合要求的,前三个都是它的子回文数)
只要对整数中以任一位置开头的最长的回文数全部找出来就行了。不过要注意一点,假设以第N-1位开头的最长回文数的终止位置是第K位(N<=K),则在找以第N位开头的回文数中,对它的终止位置只需从K+1位开始找,因为以第N位开头、在第K位或以前终止的回文数,全部是以第N-1位开头的最长回文数的子回文数。
如果在搜索过程中已经到了末尾(K+1>总长度),或者从第K+1位一直到末尾都找不到回文数的,就认为以这一位开头没有符合要求的回文数。一开始N:=1,K:=0。
如“12332331”中查找回文数的过程:
(1)N:=1,K从1开始,最终K=1,回文数为“1”。
(2)N:=2,K从2开始,最终K=5,回文数为“2332”。
(3)N:=3,K从6开始,最终K=7,回文数为“33233”。
(4)N:=4,K从8开始,找不到回文数。
(5)N:=5,K从8开始,找不到回文数。
(6)N:=6,K从8开始,找不到回文数。
(7)N:=7,K从8开始,找不到回文数。
(8)N:=8,K从8开始,最终K=8,回文数为“1”。
查找结束。符合要求的回文数共有4个。
板凳
Mato完整版 [专家分:1270] 发布于 2008-07-16 23:00:00
程序:
{$H+}
VAR
s: STRING;
l: INTEGER;
total: LONGINT;
FUNCTION hw(ss: STRING): BOOLEAN;
VAR
i, lss: INTEGER;
BEGIN
lss := LENGTH(ss);
FOR i:=1 TO lss DIV 2 DO
IF ss[i] <> ss[lss - i + 1] THEN EXIT(FALSE);
EXIT(TRUE);
END;
PROCEDURE xxx;
VAR
n, k, j: INTEGER;
t, fonm: STRING;
f: BOOLEAN;
BEGIN
k := 0;
FOR n:=1 TO l DO BEGIN
IF k + 1 > l THEN BREAK;
t := ''; f := FALSE;
FOR j:=n TO k DO t := t + s[j];
FOR j:=k + 1 TO l DO BEGIN
t := t + s[j];
IF hw(t) THEN BEGIN k := j; f := TRUE; END;
END;
IF f THEN BEGIN
FOR j:=n TO k DO WRITE(s[j]);
WRITELN;
INC(total);
END;
END;
END;
BEGIN
READLN(s);
WRITELN;
l := LENGTH(s);
xxx;
WRITE('total= ', total);
END.
我来回复