Задачи на палиндромы, палиндромы!Помогите пожалуста срочно! |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задачи на палиндромы, палиндромы!Помогите пожалуста срочно! |
Snake08 |
6.11.2008 17:01
Сообщение
#1
|
Группа: Пользователи Сообщений: 2 Пол: Мужской Реальное имя: Николай Репутация: 0 |
Палиндромы 1!
Задана строка, которая составляется из малых латинских букв. Разрешается удалять из строки определенные буквы. Сколькими разными образами можно при этом получить палиндром? Входные данные: заданная строка находится в файле palindrome1.dat, длина его не превышает 30 символов Исходные данные: в первую строку файла palindrome1.sol надо вывести искомое количество образов получения палиндрому Пример входных и исходных данных: palindrome1.dat aab palindrome1.sol 4 Объяснение: палиндром можно получить, удалив символы 1) 1 і 2; 2) 1 і 3; 3) 2 і 3; 4) 3! Палиндромы 2! Задана строка, которая составляется из малых латинских букв. Нужно разбить его на минимальное возможное количество палиндромов. Входные данные: заданная строка находится в файле palindrome2.dat, длина не превышает 2000 символов Исходные данные: в первую строку файла palindrome2.sol надо вывести минимальное количество палиндромов, на которые можно разбить строку Пример входных и исходных данных: palindrome2.dat abbacbb palindrome2.sol 3 Объяснение: abbacbb = abba + c + bb |
Rian |
6.11.2008 21:19
Сообщение
#2
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
ну не знаю задача может мудрёная но не сложная
что не знаешь? можешь определить являетя ли отрывок строки палиндромом? можешь перебрать все возможные отрывки строк? и ещё почему надо определить МИНИМАЛЬНОЕ количество, это сколько 1,2,3... не понятно -------------------- Objective-C, Unity3d
|
volvo |
6.11.2008 21:26
Сообщение
#3
|
Гость |
Цитата и ещё почему надо определить МИНИМАЛЬНОЕ количество, это сколько 1,2,3... Потому что любую строку можно разбить на палиндромы, если они будут минимальной длины (по одной букве)... В задании же требуется разбить строку на минимальное количество палиндромов, соответственно, их длины должны быть максимально возможными... Вот, в примере строка разбита на 3 палиндрома, а можно было бить нане понятно 5: abbacbb = a + bb + a + c + bb 6: abbacbb = a + b + b + a + c + bb и даже на 7... МЕНЬШЕ чем на 3 палиндрома приведенную строку разбить нельзя. |
Snake08 |
6.11.2008 21:47
Сообщение
#4
|
Группа: Пользователи Сообщений: 2 Пол: Мужской Реальное имя: Николай Репутация: 0 |
Я в паскале ноль можете мне написать в паскале! Пожалуста я буду очень благодарен!
|
Lapp |
7.11.2008 2:20
Сообщение
#5
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Я в паскале ноль можете мне написать в паскале! Значит ли это, что ты просишь готовую программу целиком? С начала и до конца? Боюсь, здесь ты это не получишь (разве что в "Задачах на заказ"). Как я понимаю, ты "в Паскале ноль" потому, что ты лоботряс. Напрягись, и стань в Паскале хотя бы 0.001. Начни писать программу. Или хотя бы задай конкретный вопрос по написанию. Тогда приходи - поможем обязательно. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Rian |
7.11.2008 8:19
Сообщение
#6
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
слушайте, задумался, чтобы найти минимальное количество надо найти максимально длинную строку, исключить её из анализа и в оставшейся части дробить её на более мелкие, мелкие...
но как хранить данные об исключениях (сначала думал просто удалять, но нельзя) создать динамический массив? для всех отрывков строк? -------------------- Objective-C, Unity3d
|
Lapp |
7.11.2008 8:52
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
но как хранить данные об исключениях (сначала думал просто удалять, но нельзя) создать динамический массив? для всех отрывков строк? Рекурсия? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Rian |
7.11.2008 18:18
Сообщение
#8
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
Рекурсия? Да, рекрсия это круто и у меня с ней всегда был напряг. это посложнее, чем отслеживание бесконечных циклов пол дня не работал а мозги крутил... переполнение стека ,переполнение стека,переполнение стека... но кажется решил (может и неправильно...)
кажется ещё можно не проверять длины строк, а сами строки if tpal<>'' then begin ну а подойдёт ли решение Snake08 не знаю Сообщение отредактировано: feniks25 - 7.11.2008 18:31 -------------------- Objective-C, Unity3d
|
volvo |
7.11.2008 18:44
Сообщение
#9
|
Гость |
Цитата кажется решил Возможно, что это даже отработает на 32-битном компиляторе. В случае с Турбо-Паскалем (все-таки раздел-то для него, а не для 32-бит) вылезают как минимум 2 проблемы:1) может не хватить стека при большой длине входной последовательности (в условии указано до 2000 символов); 2) String хранит до 256 символов, но никак не 2000. Кстати, если принимать строки в качестве параметра по константной ссылке (как Const st: string), то можно значительно уменьшить использование стека. |
Rian |
7.11.2008 19:29
Сообщение
#10
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
хм... ну тогда можно не использовать рекурсию, а сделать проще.
создадим массив [1..2000] заполним его нужными символами найдём в этой строке наибольший палендром перепишем этот отрезок нолями найдём новый непрерывный отрезок между нолями, проверим его на палендром... ну и будем заодно считать сколько штук нашли -------------------- Objective-C, Unity3d
|
Lapp |
8.11.2008 7:50
Сообщение
#11
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
хм... ну тогда можно не использовать рекурсию, а сделать проще. Дык. Тогда можно и до Питера не использовать поезд - пешком проще! Перемудрил, ты, однако.. Реально именно рекурсия всегда проще (алгоритмически) и короче. Если, конечно, подумать сначала var Ну, что может быть проще? Если заменить первый цикл на while или хотя бы вставить в него break, то можно сэкономить 50% времени. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Rian |
8.11.2008 9:29
Сообщение
#12
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
Если заменить первый цикл на while или хотя бы вставить в него break, то можно сэкономить 50% времени. ? странно, слушай ты тестировал свою прогу? короче вот что я намерял test='ghjaaabbbjjjioklk'; количество 9 мой вариант:память-12кб время при 1000 повторах 62 мс твой :память-12кб время при 1 повторе 8609мс тестировал Delphi7. учёл совет volvo про константы но это всё равно не выход для задачи требуется обработать 2000 символов, а при рекурсии на паскале... думаю даже при идеальной проработке нереально. к тому же строки действительно 255 символов, надо создавать массив, а это ещё больше памяти... -------------------- Objective-C, Unity3d
|
volvo |
8.11.2008 9:55
Сообщение
#13
|
Гость |
feniks25, как говорил один из героев Ж.Верна "не следует смешивать статику с динамикой, это может привести к серьёзным промахам."
Цитата надо создавать массив, а это ещё больше памяти... Да, надо... Но только учти, что массив (длиной 2000 символов) описывается глобально 1 раз, плюс добавляется еще 3 целочисленных массива (третий - для сохранения позиций этих самых палиндромов, так что можно в принципе обойтись и двумя) тоже по 2000 Integer-ов, итого в худшем случае все это удовольствие стоит тебе 14000 байт. А уж 2000 уровней рекурсии Паскаль как-нибудь осилит с (учётом того, что на каждом витке в стек кладётся не огромная строка, и не ещё бОльший массив, а всего несколько целочисленных переменных):{ Ну, это не обязательно, это моя старая привычка имитации X++ и X-- } Сообщение отредактировано: volvo - 8.11.2008 9:56 |
Rian |
8.11.2008 17:26
Сообщение
#14
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
а зачем ещё три массива, если все нужные операции можно сделать в пределах одного
и зачем хранить позиции палендромов -------------------- Objective-C, Unity3d
|
volvo |
8.11.2008 17:45
Сообщение
#15
|
Гость |
Цитата а зачем ещё три массива, если все нужные операции можно сделать в пределах одного Если ты на 100% уверен, что следующим же вопросом не последует "А как мне вывести сами палиндромы, составляющие исходную строку?", то можно обойтись и одним. |
Текстовая версия | 25.04.2024 10:00 |