回 帖 发 新 帖 刷新版面

主题:我错哪了?

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。例如:给定一个 10进制数 56,将 56加 65(即把56从右向左读),得到 121是一个回文数。又如,对于10进制数87, 
STEPl: 87+78= 165 STEP2: 165+561= 726 
STEP3: 726+627=1353 STEP4:1353+3531=4884 
在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。 
写一个程序,给定一个N(2<=N<=10,N=16)进制数 M,求最少经过几步可以得到回 
文数。如果在30步以内(包含30步)不可能得到回文数,则输出’no’。 
输入文件3.in,一行。第一行,只有一个整数,表示N进制。第二行是一个字符串,表示N进制数 M。 
输出文件3.out,只有一行,为一个整数(表示最少步数)或一个字符串’no’。 
样例: 
输入:9 
87 
输出:6



var    a,b,c:array[1..200] of 0..9;
       n,n1,n2:string;   lena,lenb,lenc,i,x:integer;
begin
     write('Input minuend:'); readln(n1);
     write('Input subtrahend:'); readln(n2);
     if (length(n1)<length(n2)) or (length(n1)=length(n2)) and (n1<n2)
       then begin
            n:=n1;n1:=n2;n2:=n; write('-')
            end;
     lena:=length(n1); lenb:=length(n2);
     for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
     for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
     i:=1;
     while (i<=lena) or(i<=lenb) do
      begin
       if a[i]<b[i]then begin a[i+1]:= a[i+1] -1;a[i]:=a[i]+10; end;
       c[i] := a[i]-b[i] ;
       i := i + 1
      end;
    lenc:=i;
    while (c[lenc]=0) and (lenc>1) do dec(lenc);
    for i:=lenc downto 1 do write(c[i]); writeln
end.


回复列表 (共2个回复)

沙发

你这不是高精度减法的程序吗?

这跟你的题目完全不符合。

板凳

我给你说一下算法。

这题的难点就是怎么实现N进制加法。
可以用10进制高精度加法的思想来实现N进制高精度加法。
由于10进制是逢10进1,而N进制是逢N进1。所以只要把这句:
IF s[i] >= 10 THEN BEGIN
   s[i] := s[i] - 10; s[i + 1] := s[i + 1] + 1;
END;
改成:
IF s[i] >= n THEN BEGIN
   s[i] := s[i] - n; s[i + 1] := s[i + 1] + 1;
END;
就行了。不过如果是16进制还要做好数字与字母的转换。

程序:
TYPE arr = ARRAY[1..1023] OF INTEGER;
FUNCTION n_gjdadd(x, y: STRING; n: INTEGER): STRING;
VAR
   a, b, s: arr; z, zz: STRING;
   lx, ly, l, i, k: INTEGER;
BEGIN
    lx := LENGTH(x); ly := LENGTH(y); z := '';
    IF lx > ly THEN l := lx ELSE l := ly;
    FOR i:=1 TO l + 1 DO s[i] := 0;
    FOR i:=1 TO lx DO VAL(COPY(x, lx + 1 - i, 1), a[i], k);
    FOR i:=1 TO ly DO VAL(COPY(y, ly + 1 - i, 1), b[i], k);
    FOR i:=1 TO l DO BEGIN
        s[i] := s[i] + a[i] + b[i];
        IF s[i] >= n THEN BEGIN
           s[i] := s[i] - n; s[i + 1] := s[i + 1] + 1;
        END;
    END;
    IF s[l + 1] > 0 THEN l := l + 1;
    FOR i := l DOWNTO 1 DO BEGIN
        IF s[i] < 10 THEN zz := CHR(s[i] + 48) ELSE zz := CHR(s[i] + 55);
        z := z + zz;
    END;
    n_gjdadd := z;
END;
FUNCTION opposite(x: STRING): BOOLEAN;
VAR
   i, l: INTEGER; f: BOOLEAN;
BEGIN
    l := LENGTH(x); f := TRUE;
    FOR i := 1 TO (l DIV 2) DO BEGIN
        IF COPY(x, i, 1) <> COPY(x, l + 1 - i, 1) THEN BEGIN
           f := FALSE; BREAK;
        END;
    END;
    opposite := f;
END;
VAR
   i, j, ls, n: INTEGER; m, s, t: STRING;
BEGIN
    WRITE('n:'); READLN(n);
    WRITE('number:'); READLN(m);
    s := m;
    FOR i:=1 TO 30 DO BEGIN
        t := ''; ls := LENGTH(s);
        FOR j := ls DOWNTO 1 DO BEGIN
            t := t + COPY(s, j, 1);
        END;
        s := n_gjdadd(s, t, n);
        IF opposite(s) THEN BEGIN WRITELN(i); HALT; END;
    END;
    WRITELN('no');
END.

我来回复

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