[Lập trình newbie] Mỗi ngày một bài toán (số 12)

[09520281]

Hi all :look_down:. Chúng ta tiếp tục với bài 12, một bài chuỗi đối xứng nhưng hơi khác 1 chút :sunglasses:.
Bài toán:

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn


Chuỗi s có độ dài không vượt quá 2000.
Ví dụ:

Dữ liệu mẫu
lmevxeyzl
Kết qủa
level
Have fun :shy:

[11520132]

là muốn xóa thế nào thì xóa miễn sao in ra chuỗi đối xứng có độ dài dài nhất phải không anh ?
Cái này buồn ngủ quá viết đại, test thử mấy cái đúng

#include <stdio.h>
#include <string.h>
void xuly(char s[])
{
    int m=0,i,j,k;
    char s2[2000];
    int a[1000];
    // tim cac chuoi doi xung va luu do dai vao mang a
    while (m<=strlen(s))
    {
        i=m,j=strlen(s),k=0;
        while (i<=j)
        {
            if (s[i]==s[j])
            {
                k++; i++; j--;
            }
            else j--;
        }
        a[m++]=k;
    }
    // tim so lon nhat trong mang a
    for (m=0,i=0;m<strlen(s);m++)
        if (a[m]>a[i]) i=m;
    j=strlen(s),k=0;
    // dua chuoi dai nhat vao chuoi s2
    while (i<=strlen(s)&&j>=0)
        {
            if (i<=j)
            {
                if (s[i]==s[j])
                {
                    s2[k++]=s[i++];
                    j--;
                }
                else j--;
            }
            else
            {
                if (s[i]==s[j])
                {
                    s2[k++]=s[i++];
                    j--;
                }
                else i++;
            }
        }
    s2[k]='\0';
    puts(s2);
}
void main()
{
    char s[2000];
    gets(s);
    xuly(s);
} 

[quoctinvn]

cái đoạn

  if (s[i]==s[j]) 
            { 
                k++; i++; j--; 
            } 
            else j--;

có vẻ như không ổn lắm :amazed:
theo em bài này mình giải = quy hoạch động :sexy:
gọi f[i,j] là độ dài xâu con palin dài nhất trong chuỗi con từ s[i]...s[j].
Xét i từ length(s) -> 1, j từ i+1-> length(s)
nếu s[i] = s[j] thì f[i,j] = max(f[i+1,j-1]+2,f[i,j-1],f[i+1,j]). nếu s[i] # s[j] thì f[i,j] = max(f[i+1,j-1],f[i,j-1],f[i+1,j]).
Việc xuất xâu thì có thể dựa vào mảng F mà trace ra :sure:

[08520001]

Quy hoạch động là gì nhỉ giay luoi nam. Có bạn nào biết về cái này hok?

[11520132]

Quy hoạch động là gì nhỉ? Có bạn nào biết về cái này hok?

em cũng không biết, thường thì e giải bài tập bí quá mới tìm hiểu thuật toán bên ngoài chứ ít khi tự đi đọc tìm hiểu các thuật toán lắm

[quoctinvn]

Công thức dãy fibo là quy hoạch động đấy ạ :love:
cái gọi là công thức truy hồi trong dãy số ở toán cấp III chính là QHĐ :sure:

[11520132]

Công thức dãy fibo là quy hoạch động đấy ạ :love:
cái gọi là công thức truy hồi trong dãy số ở toán cấp III chính là QHĐ :sure:

vẫn chưa rõ lắm áp dụng ra sao, hay cậu viết code đi, có khi nhìn vào code dễ hiểu hơn :funny:
mà bài của mình viết sai rồi, đã check lại

[quoctinvn]

uses math;
const
  fi = 'PALIND.INP';
  fo = 'PALIND.OUT';
var
  f1,f2 : text;
  s : ansistring;
  f : array[1..2000,1..2000] of longint;
  si,sj,len : longint;

procedure openfiles;
begin
  assign(f1,fi); reset(f1);
  assign(f2,fo); rewrite(f2);
end;

procedure closefiles;
begin
  close(f1); close(f2);
end;

procedure init;
var
  i : longint;
begin
  readln(f1,s);
  for i := 1 to length(s) do f[i,i] := 1;
end;

procedure solve;
var
  i,j : longint;
begin
  len := 1;
  for i := length(s)-1 downto 1 do
    for j := i+1 to length(s) do
      if s[i] = s[j] then
        f[i,j] := max(f[i+1,j-1]+2,max(f[i+1,j],f[i,j-1]))
      else
        f[i,j] := max(f[i+1,j-1],max(f[i+1,j],f[i,j-1]));
  for i := 1 to length(s)-1 do
    for j := i+1 to length(s) do
      if len < f[i,j] then
        begin
          len := f[i,j];
          si := i; sj := j;
        end;
end;

procedure trace;
var
  st : ansistring;
  lentmp,i : longint;
begin
  st := ''; lentmp := len;
  while si <= sj do
    begin
      if s[si] = s[sj] then
        begin
          st := st + s[si];
          dec(len,2);
          inc(si); dec(sj);
          if len <= 0 then break;
        end
      else
        if f[si,sj-1] = len then dec(sj) else inc(si);
    end;
  write(f2,st);
  if lentmp mod 2 = 0 then
    for i := length(st) downto 1 do write(f2,st[i])
  else
    for i := length(st)-1 downto 1 do write(f2,st[i]);
end;

begin
  openfiles;
  init;
  solve;
  trace;
  closefiles;
end.

Em mới test thử test ví dụ ra OK. Thuật toán nói chung là có CT như trong thủ tục solve :sogood: phần trace thì dựa vào mảng F mà ra. Hiểu được phần xây dựng mảng F thì phần truy ngược ra sẽ dễ ạ :sure:
@ Chắc trong thời gian này em phải tranh thủ học C thôi ạ ps: Cho em hỏi IDE nào code C tốt ạ, debugger dễ nhìn 1 tí ạ

[truonganpn]

@ Chắc trong thời gian này em phải tranh thủ học C thôi ạ ps: Cho em hỏi IDE nào code C tốt ạ, debugger dễ nhìn 1 tí ạ

Tôi dùng code::blocks: http://sourceforge.net/projects/code...ingw-setup.exe

[11520132]

Tôi dùng code::blocks: http://sourceforge.net/projects/code...ingw-setup.exe

Em cũng dùng cái này

[quoctinvn]

Em thấy trong bộ Visual Studio có C udency: không biết xài đc ko ạ :shot:

[quoctinvn]

Ep 13 chưa ạ :d