回 帖 发 新 帖 刷新版面

主题:求助啊!

输入一任意长度的整数,找出其中所有回文数(不含回文数中的子回文数),并输出个数。
答出来的分不是问题。

回复列表 (共2个回复)

沙发

我的算法:(不知道对不对)
由于不含回文数中的子回文数,因此以同一位置开头的回文数中,最多只有一个是符合要求的,并且这个回文数是最长的。
(举个例子:“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个。

板凳

程序:
{$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.

我来回复

您尚未登录,请登录后再回复。点此登录或注册