Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

[C/C++] строки палиндром

271
21 мая 2007 года
MrXaK
721 / / 31.12.2002
Дана символьная строка, составленная из букв латинского алфавита . Определите наименьшее количество символов , которые необходимо удалить , чтобы из оставшихся получлся палиндром. Укажите удаляемые символы. Текст : "DAKFQNFSK". Рузльтат : нужно выбросить 4 символа , например, N, S, D, A, получится палиндром FKQKF
622
21 мая 2007 года
nilbog
507 / / 19.12.2006
простейшее что можно придумать правда долгое
выкидываем по очереди всевозможные комбинации букв длин 1,2,3...
плюсы - легко реализовать перебором
ну и будет долго работать - если подумать то наверно как то процесс можно оптимизировать

кстати можно и рекурсивно
выкидываем символ смотрим палиндром или нет
если нет то рекурсивный вызов от оставшегося
242
22 мая 2007 года
Оlga
2.2K / / 04.02.2006
для начала можно выкинуть все символы которые встречаются в слове один раз. дальше надо будет думать.
функция, которая определяет, что строка полинром есть в FAQ'е.
361
22 мая 2007 года
Odissey_
661 / / 19.09.2006
Нет, выкидывать ничего не стоит. Приведенный Mr.Hacker пример на это указывает.
Рекурсивный метод (теория и алгоритм) можно стрельнуть на википедии - Задача "Сделай Палиндром".
Табличный метод, исходник у меня валялся, вроде даже рабочий , правда решал не я ..., но будут вопросы задавай.
Код:
#include <stdio.h>
#include <string.h>


int max(int value1, int value2) {
  return ( (value1 > value2) ? value1 : value2);
}

int main() {

  int k[100][100];
  const char *s1 = "ASDDFSA"; // Здесь - твои символы (до 100 штук)
  int L = strlen(s1);

  char *s2 = strdup(s1);
  strrev(s2);

  for(int i = 0; i <= L; ++i)
    k[0] = k[0] = 0;

  for(i = 1; i <= L; ++i)
    for(int j = 1; j <= L; ++j)
      if(s1[i - 1] == s2[j - 1]) k[j] = k[i - 1][j - 1] + 1;
      else k[j] = max(k[i - 1][j], k[j - 1]);
  printf("You should delete %i char(s)\n", (L - k[L][L]));

  i = L; j = L;
  while(k[j]) {
    while (k[j - 1] == k[j]) j -= 1;
    if(s1[i-1] == s2[j-1]) {
      printf("%c", s1[i-1]);
      j -= 1;
    }
    i -= 1;
  }
  printf("\n");

  return 0;
}
361
03 июня 2007 года
Odissey_
661 / / 19.09.2006
По просьбам трудящихся, как и обещал, выкладываю хоть какое-то объяснение привиденного выше кода.

Решение базируется на поиске наибольшей общей подпоследовательности (НОП), алгоритм прямой прогонки. В самом деле, если взять слово в прямом порядке и в обратном порядке, и найти их НОП, то она (подпоследовательность) и будет искомым палиндромом. Массив k - хранит значение максимальных НОП. Очень подробное описание с доказательством можно посмотреть здесь.
По поводу вывода тех букв, которые необходимо удалить тоже невижу особых проблем. Удали из исходной строки те буквы которые есть в палиндроме, оставшиеся выведи.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог