Перейти до вмісту

Розвязання завдань з програмування


Повідомлень в темі: 191

#121 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 01.11.2008 – 13:02

Привіт!!! Допоможіть розв`язати задачку, якщо зможете.
Задано рядок, який складається з малих латинських літер. Потрібно розбити його на мінімальну можливу кількість паліндромів.
Наприклад: abbacbb
Відповідь:3
Пояснення: abbacbb = abba + c + bb
  • 0

#122 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 01.11.2008 – 14:58

Цитата

Потрібно розбити його на мінімальну можливу кількість паліндромів.
Де ви такіх слів набрались "паліндромів"? Шо воно таке?
  • 0

#123 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 01.11.2008 – 18:38

Перегляд дописуFT232BM (1.11.2008 15:58) писав:

Де ви такіх слів набрались "паліндромів"? Шо воно таке?



Паліндром - це число що читається з ліва на право та з права на ліво однаково.
  • 0

#124 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 01.11.2008 – 20:07

ІМХО тут пахне динамічним програмуванням... Читай відповідну літературу.
  • 0

#125 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 01.11.2008 – 22:33

Логіка роботи проги повинна бути така:
1. Пишемо функцію, що обертає рядок навпаки. Думаю з цим ти справишся
2. Повертаємо першу половину повного рядку. Та звіряємо її з іншою. Не катить? Робимо теж саме з рядком на один сивол менше. і т.д. Коли знаходимо те що треба, збільшуємо "указатєль" на рядок на довжину паліндрому і починаємо все заново.

Повідомлення відредагував FT232BM: 01.11.2008 – 22:35

  • 0

#126 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 01.11.2008 – 23:22

Простенький тест на якому твій алгоритм(наскільки я його зрозумів) заженеться...
"abaab"
результат алгоритму: aba + a + b
відповідь: a + baab

П.С. перевернення і порівняння теж в принципі неоптимально...
  • 0

#127 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 01.11.2008 – 23:40

Без перевертання поки що не здогадуюсь як зробити.
А алгоритм можна виправити, порівнюючи обернений фрагмент рядку з кожним іншим фрагментом, а потім зменшувати його на одиницю та повотрювати все знову. Інша справа що робити з після того як знайдено необхідний фрагмент. Не нулями ж його забивати та і пререписувати в стрічку, що аналізуєтся в нову область пам‘яті не охота, отже тре написати хитрожопу функцію, що пропускає вже використані фрагменти. Можна ці фрагменти заміняти одним символом, що не використовуєтся, наприклад чимось з ескейп послідовності.
  • 0

#128 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 02.11.2008 – 00:17

динамічне програмування... та задача походу інакше не розвязується.... А навіть якщо розвязується то складність буде огого...

Без перевертання?

bool IsPolindrom(int startIndex, int endIndex, string str)
{
// тут перевіряємо параметри на правильність і кидаєм ексепшини
while(endIndex > startIndex)
{
if (str[endIndex] != str[startIndex])
return false;
endIndex--;
startIndex++;
}
return true;
}


П.С. Нагадує задачу про рюкзак...

П.П.С. Література: Роберт(?) Седжвік "Алгоритми "Фундаментальні Алгоритми на (якійсь мові, в мене С++)"
  • 0

#129 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 02.11.2008 – 12:37

Omg. це ж скільки разів її викликати треба?
  • 0

#130 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 13:46

З половиною неполучиться, потрібно прочитати його в строку, далі кожен символ є паліндромом, якщо є два чи більше однакових символів то є ще паліндроми, а так як брати половину рядка теж можливо тільки може пробувати з першого символу. І от коли я пишу на мові паскаль у мене з цим проблеми. Напишіть рішення. Рятуйте!!! Допоможіть!!! Ви ж геніальні люди!!!
  • 0

#131 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 14:27

Перегляд дописуLactarius (aka Ivan Metal!) (2.11.2008 00:22) писав:

Простенький тест на якому твій алгоритм(наскільки я його зрозумів) заженеться...
"abaab"
результат алгоритму: aba + a + b
відповідь: a + baab

П.С. перевернення і порівняння теж в принципі неоптимально...


Неправильно, нам потрібно знайти максимальну кількість паліндромів на які можна розбити цю стрічку. Отже aba + a + b=3 - правильна відповідь.
  • 0

#132 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 02.11.2008 – 14:32

Цитата

Неправильно, нам потрібно знайти максимальну кількість паліндромів на які можна розбити цю стрічку. Отже aba + a + b=3 - правильна відповідь.
o_O Чому не a+b+a+a+b?
  • 0

#133 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 02.11.2008 – 14:52

Цитата

Неправильно, нам потрібно знайти максимальну кількість паліндромів на які можна розбити цю стрічку. Отже aba + a + b=3 - правильна відповідь.
Тоді задача дійсно нелогічна...

Цитата

З половиною неполучиться, потрібно прочитати його в строку, далі кожен символ є паліндромом, якщо є два чи більше однакових символів то є ще паліндроми, а так як брати половину рядка теж можливо тільки може пробувати з першого символу. І от коли я пишу на мові паскаль у мене з цим проблеми. Напишіть рішення. Рятуйте!!! Допоможіть!!! Ви ж геніальні люди!!!
нічого не зрозумів....

Цитата

Omg. це ж скільки разів її викликати треба?
Зате вона працює в кілька разів швидше ніж перевернути-порівняти... Отже виграш в швидкості буде досить великим...

Цитата

Питання по Джава...
Як в аплеті вивести текст? Якщо можна шматок коду з суто функцією виводу. Наперед вдячний.
Лейблами хіба не можна?
П.С. Є окрема тема для запитань по Джаві http://www.tereveni....?showtopic=6822
  • 0

#134 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 14:53

Перегляд дописуFT232BM (2.11.2008 15:32) писав:

o_O Чому не a+b+a+a+b?


Вибачте, це я винен рядок потрібно розбити на мінімальну кількість паліндромів. Вибачаюся!!!
  • 0

#135 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 02.11.2008 – 15:34

%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5м

http://acm.timus.ru/...pace=1&num=1635
http://acm.timus.ru/...pace=1&num=1635
  • 0

#136 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 15:44

Перегляд дописуLactarius (aka Ivan Metal!) (2.11.2008 16:34) писав:


Але там немає відповіді!???
  • 0

#137 Lactarius

    Генеральний писар

  • Користувачі
  • PipPipPipPipPipPipPipPipPip
  • 976 повідомлень
  • Стать:Чоловік
  • Місто:Львів

Відправлено 02.11.2008 – 15:46

А на готову програму навіть не надійся. Там чітко написано що розвязується динамічним програмуванням. В вікіпедії написано, що воно таке. працюй.
  • 0

#138 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 16:04

Проблема у тому що мені потрібна прога, як би я міг сам написати яб уже написав. Мені потрібна допомога людей які це добре знають???
  • 0

#139 FT232BM

    私は人々嫌い

  • Користувачі
  • PipPipPipPipPipPipPipPipPipPip
  • 3435 повідомлень
  • Стать:Чоловік
  • Місто:Київ->НТУУ "КПІ"

Відправлено 02.11.2008 – 17:18

Люди, які добре знають безкоштовно нічого не роблять. Адже на якісну прогу потрібен час. Тут тобі можуть допомогти порадою, а не розв‘язки давати
З.І. Особисто я за гроші лаби не роблю...
  • 0

#140 -=Українець=-

    Профі

  • Користувачі
  • PipPipPipPipPipPipPip
  • 369 повідомлень
  • Стать:Чоловік
  • Місто:Хмельницького

Відправлено 02.11.2008 – 17:25

Ні, звичайню просто так ніхто робити небуде, просто я думав що ви мені напишете головну частину проги а яб усе доробив, ну і натому дякую. ;)

УКРАЇНА - the Best!!!
  • 0



Кількість користувачів, що читають цю тему: 1

0 користувачів, 1 гостей, 0 анонімних