Софтуерно Инженерство
Loading...
+ Нов въпрос
StanimirStankov avatar StanimirStankov 18 Точки

Търся оптимален алгоритъм за решаване на задача с игрални карти

На входа ни се подава стринг с 5 карти разделени с интервал, например $inp = "2c Kc 7h Ac Qc";

Първия знак е силата на картата от 2 - А, а втория боята - c, d, h, s.

Програмата трябва да върне дали има или няма терца(три поредни от една боя) от картите.

 

Тагове:
2
PHP Fundamentals
MartinBG avatar MartinBG 1260 Точки

Сещам се за няколко алгоритъма, като най-ефктивният за тази задача (и на теоря, и на практика) е със сложност O(N) и ползва константно количество памет (52 елемента - колкото са картите в тестето, плюс 1 брояч).
 
 Понеже не съм писал на PHP, само ще обясня алгоритъма, а оставям на теб да напишеш кода. smiley
 
За решаването на задачата ти трябва линейна структура, която може да се достъпва чрез индекс - масив, или каквото аналогично има в PHP, с 52 елемента (най-добре от булев тип или 0/1), в която структура да отбелязваме дали дадена карта е била подадена чрез входните данни. 
Първо инициализираш структурата с False (или 0).
После обработваш всеки елемент от входните данни като го преобразуваш в индекс (0-51 - според типа и боята на картата) и променяш стойността в масива за този индекс на True (или 1).
 
Дотук сложността на алгоритъма е O(N), където N = брой карти във входните данни.
 
Като приключиш с обработката на входните данни, ти остава само да обходиш еднократно масива, започвайки от индекс 0 и с брояч = 0.

При всяко срещане на True/1 - увеличаваш брояча с 1, а при срещане на False/ 0 - го нулираш.

На всяка стъпка проверяваш дали брояча е равен на  3. Ако е равен, значи имаме терца и може да прекъснеш изпълнението на цикъла и да отпечаташ успешен резултат. Ако това не се е случило нито веднъж при обхождането на масива, значи нямаме терца.
 
Надявам се, че съм успял да го обясня достатъчно ясно.
 
Успех!

2
07/01/2018 15:06:42
Thedi avatar Thedi 200 Точки

Аз не разбирам много от сложности на алгоритми, но не е ли по добре да се направи един Regex който да види дали в стринг-а има три карти от една боя и ако има да вземе този мач който е с 3 или повече от една боя.

След това може да имаш само един масив който е картите от 2 - А (Няма значение боята това Regex-a го е проверил) и след това може да се продължи с проверката дали са една до друга ?

0
07/01/2018 16:32:49
MartinBG avatar MartinBG 1260 Точки

Зависи какво разбираш под "по-добре" :)

Ако това е решението, което е най-удобно за реализиране (за теб и за екипа, който би поддържал този код) и същевеременно отговаря на изискванията по отношение на количество входни данни, използвана памет и време за изпълнение, то тогава това сигурно ще е "по-доброто" решение. :)

Ако го разпишеш, може да сравним двата подхода - както като количество и структура на кода, така и като бързодействие.

0
dvdty avatar dvdty 472 Точки

Едит: Имаше бъг, мисля, че го оправих, трябва да работи нормално сега

0
MartinBG avatar MartinBG 1260 Точки

Да, поне доколкото успях да се ориентирам в PHP синтаксиса. yes

0