ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Maydell                        2:5030/744.179 27 May 2003  02:40:49
 To : Michael Medvedev
 Subject : Палиндром
 -------------------------------------------------------------------------------- 
 

 26 May 03 23:28, you wrote to All:
 
  MM> Дана строка символов. Дописать к ней наименьшее количество символов
  MM> чтоб получился палиндром.
 
 #include <stdio.h>
 #include <string.h>
 
 #define maxN 1024
 #define NOT_DEFINED -1
 
 char s[maxN];
 short a[maxN][maxN];
 char b[maxN][maxN];
 
 int f(int i,int j)
 {
 int v1,v2;
 
 if (i > j) return 0;
 
 if (a[i][j] == NOT_DEFINED)
   {
   if (s[i] == s[j])
     {
     a[i][j] = f(i+1,j-1);
     b[i][j] = 2;
     }
   else
     {
     v1 = f(i+1,j);
     v2 = f(i,j-1);
     if (v1 < v2)
       {
       a[i][j] = v1;
       b[i][j] = 0;
       }
     else
       {
       a[i][j] = v2;
       b[i][j] = 1;
       }
     a[i][j]++;
     }
   }
 return a[i][j];
 }
 
 void print(int i,int j)
 {
 if (i == j)
   {
   putchar(s[i]);
   return;
   }
 
 if (i > j) return;
 
 switch(b[i][j])
   {
   case 0:
     putchar(s[i]);
     print(i+1,j);
     putchar(s[i]);
     break;
   case 1:
     putchar(s[j]);
     print(i,j-1);
     putchar(s[j]);
     break;
   case 2:
     putchar(s[i]);
     print(i+1,j-1);
     putchar(s[j]);
     break;
   }
 }
 
 void Test(void)
 {
 int i,j,l;
 l = strlen(s);
 for(i=0;i<l;i++) for(j=i;j<l;j++) a[i][j] = NOT_DEFINED;
 for(i=0;i<l;i++) {a[i][i] = 0;b[i][i] = 2;}
 printf("%d ",f(0,l-1));
 print(0,l-1);
 printf("\n");
 }
 
 int main(void)
 {
 while(gets(s)!=NULL) Test();
 return 0;
 }
 
 Anton
 
 --- GoldED/W32 3.0.1-asa8
  * Origin:  (2:5030/744.179)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Палиндром   Michael Medvedev   26 May 2003 23:28:46   Палиндром   Konstantin Yegupov   27 May 2003 01:23:32   Палиндром   Anton Maydell   27 May 2003 02:40:49