Задача Палиндроми државен '14

This message was edited 2 times. Last update was at 12/04/2017 19:58:00

Го преземав првиот тест пример: s=9 e=756
Мојата програма оди по чекорите :
9 + 8 => 17
17 + 11 => 28
28 + 22 => 50
50 + 44 => 94
94 + 88 => 182
182 + 181 => 363
363 + 353 => 716
716 + 33 => 749
749 + 7 => 756
И печати решение 9, но точниот одговор според тест примерот е 8. Програмата работи додавајќи го на S најголемиот палиндром P таков што P <= Si , P <= E-Si , P!=E-Si-1.

За темава се има дискутирано и порано: http://mendo.mk/jforum/posts/list/388.page

Greedy не проаѓа за оваа задача, ќе треба со динамичко програмирање да ја решиш.

Благодарам

А како заклучивте дека 'Greedy' не поминува на оваа задача?

This message was edited 1 time. Last update was at 14/04/2017 22:14:40

.

HoulaHulaHoop wrote:А како заклучивте дека 'Greedy' не поминува на оваа задача?

Проблемов го нема алчното својство, односно не мора да значи дека ако при секој чекор го земеме 'оптималниот' палиндром, дека тој мора да биде земен и во оптималното решение.

This message was edited 1 time. Last update was at 15/04/2017 19:18:19

Но како тоа? Нели 'оптималниите' палиндроми се оние кои го формираат оптималното решение?

HoulaHulaHoop wrote:Но како тоа? Зар 'оптималниот' палиндром не е оној кој се избира во оптималното решение?

За 'оптимален' мислев тој што делува дека е најдобро да се одбере во еден чекор со некој алчен критериум, пример најголемиот, најмалиот, итн. Не мора да значи ако еден палиндром делува дека е најдобар во еден момент, дека тој спаѓа во оптималното решение.