Detectie secventa intr-un sir

[Vizitator]

nu stiu cum sa denumesc problema in sine, și sper ca voi reuși sa pun problema inteligibil dar.... sa presupunem ca avem un sir de numere aleatorii, dar in care apare o secventa pe care vrem sa o delectam. exemplu :(2,8,2,7,3,1,2,8,1,7,3,2,0,8,7,5,0,7,2,8,4,5,3,2,0,8,7,1,2,8)secventa ar fi 3208. in C, cum ar trebui sa facem sa detectam asta?

[UDAR]

La modul general problema nu are (cred) soluție. 

Ar trebui niște restricții - de pildă lungimea secvenței și ”distanța” maximă între două apariții dacă șirul este dinamic  sau lungimea lui dacă este static , etc.

De asemenea domeniul de definiție al valorilor numerelor aleatorii contează : sunt întregi de o cifră ca în exemplu, sunt valori hexazecimale , etc .

[core]

pare o problema de cautare substring intr-un string.

probabil cautarea se face pornind de la inceput si comparnad primul caracter din substring, daca coincide se verifica urmatorul din substring, daca nu coincide se trece la urmatorul din sir si se reia de la primul din substring.

probabil exista si cod pe internet daca cauti. Nu cred ca se pot folosi sortari sau optimizari prea mari pentru problema asta.

[UDAR]

Păi eu am înțeles că substringul nu se cunoaște . Dace s-ar cunoaște ar fi relativ trivial.

[rlodina]

Cand nu ai o idee/solutie eleganta (sau bazata pe un algorirm cunoscut) - apuc-o muncitoreste.

#include <iostream>int src[] = {2,8,2,7,3,1,2,8,1,7,3,2,0,8,7,5,0,7,2,8,4,5,3,2,0,8,7,1,2,8};int target[] = {3,2,0,8}; int main(){	//nr. de elemente 	int ccSrc = sizeof(src)/sizeof(src[0]);	int ccTar = sizeof(target)/sizeof(target[0]);	int idxSrc=0;		while(idxSrc < ccSrc){		if (src[idxSrc] == target[0]){ //posibil candidat 			//verificam tot target-ul			int i = 0;			while (i + idxSrc<ccSrc && i<ccTar){				if (src[idxSrc+i] != target[i]) break;				i++;			}			if (i == ccTar){			//gasit 				std::cout << "Secv gasita incepand cu idx:" << idxSrc << 'n';							}								}		idxSrc ++;	} 	return 0;}

Sper ca ai prins ideea - daca nu da-mi un semn si detaliez.

 

Succes

 

Păi eu am înțeles că substringul nu se cunoaște . 

 

Ops - nu am fost atent la enunt.

[Vizitator]

UDAR ai inteles foarte bine. substringul NU se cunoaste.

daca s-ar cunoaste ar fi floare la ureche...

 

sti, noi ochiometric, daca privim sirul ala putem detecta cateva secvente in repetitie. cred ca vizual.

ei bine si arduino ar trebui sa poata...doar ca am PANA DE IDEI

 

oricum si enuntul meu e varza.

ideea este ca sirul ala de numere...reprezinta cam asa in real:

 

{2,8,2,7, ..............................}; : 2,8 = [milisecunde ON, milisecunde OFF], 2,7 = [milisecunde ON, milisecunde OFF]

 

semnalul asta il capturez prin Analog0 de la un receiver 433MHz. (stiu ca exista rc-switch pe net, dar nu ma ajuta la remote asta)

 

mai departe, as vrea sa pot detecta un buton apasat, si de acolo alte chestii..

ceea ce nu pot face, daca eu nu pot recunoaste semnalul ala...

 

cica exista in java un cod, care tot cica ar face asta.

dar cum ar trebuii convertit codul in C++ (arduino ide) nu stiu..am incercat si returneaza baliverne. nu stiu daca din vina mea...dar codul e aici.

Editat Octombrie 28, 2015 de Vizitator

[UDAR]

Da, deci totuși ceva restricții putem aplica , din fericire . Se încadrează în a doua variantă pomenită de mine adică un string static , finit . Mai departe se poate scrie un cod . O să mă uit peste link-ul postat de tine . Din păcate putința mea de a scrie cod în C++ este zero - mă descurc doar ( și nu excelent ) cu C-ul pentru PIC mai exact cu MikroC. Dar o deslușire a algoritmului și eventual un pseudocod ( metacod ) poate va ieși. 

[Bandi Szasz]

Idea e simpla.

 

Daca acele numere sunt de la 0-9 merge mai bine ca sirul sa fie transformat in String, daca sunt numere si peste 9 atunci trebuie un array de int.

 

Idea e in felul urmator.

 

- Se ia sirul si se inparte in multiple subsiruri. Daca ai {2,8,7,2,6,1} se inparte in felul urmator {2} {2,8} {2,8,7} {2,8,7,2} {2,8,7,2,6} deci se obtin n-1 siruri.

- Se iau subsirurile obtinute si pentru fiecare in parte este efectuata o cautare in sirul original deci se numara de cate ori apre {2} in sirul original, dupa  se numara {2,8} .... {2,8,7} ... etc.... 

- Se verifica care subsir a aparut de cele mai multe ori si gata cautarea.

 

Acuma e bine sa existe niste limite pentru marimea subsirului cautat daca nu la un sir de 32 numere o sa dureze pana se cauta toate cele 31 de subsiruri. 

Codul postat in java face acelas lucru doar ca java are deja  functii gata facute pentru stringuri, poate numara singur de cate ori apare un substring doar apeland o functie fara a fii nevoie sa faci tu o functie pentru cautare, acuma depinde ce functii are arduino IDE. 

Editat Octombrie 29, 2015 de bandi12

[Vizitator]

- numerele depasesc [9]. nu stiu exact pana unde merge "scala" dar am intalnit si [90]

- nu inteleg, cum va face el detectia asta

  if ([2,8,2,7,3,1,2,8,1,7,3,2,0,8] isin [2,8,2,7,3,1,2,8,1,7,3,2,0,8,7,5,0,7,2,8,4,5,3,2,0,8,7,1,2,8]  ) ==> va gasi o singura data...habar nu are de     [3,2,0,8]

      nu stiu de ce dar sunt complet in bezna..ca niciodata.

 

oare chiar sa nu se poata ?...

poate reuseste UDAR ceva..

Editat Octombrie 29, 2015 de Vizitator

[Bandi Szasz]

Pai este si logic sa gaseasca o singura data, el cauta ce e in fata lui "isin"(acel sir de numere) in ce este dupa si il gaseste o singura data mai precis la inceput. Codul acela ii spune cauta "ab" in "abcdealap" si este normal sa iti zica l-am gasit o data findca "ab" este o singura data prezent in sirul in care se face cautarea mai precis la inceput.

 

Ce nu inteleg eu este ca cum vrei ca el sa ghiceasca ca tu vrei sa cauti "3,2,0,8" ? Dupa cum stim un sistem de calcul face ce ii spunem noi sa faca, daca ii spunem cauta "asta" cum vrei sa iti gaseasca el de capul lui "ala" ?

 

Trebuie sa existe o metoda prin care sa ii spui ca tu de fapt vrei sa gasesti 3,2,0,8 , prin a mentiona ca eu caut acel lucrcu care apare de cel mai multe ori sau de cel mai putine ori sau de x ori ,etc...  Codul trebuie sa stie ca trebuie sa caute "asta" prin a spune cauta "ala" nu o sa iti gaseasca "asta". Trebuie sa existe un tipar care sa se repete si cu ajutorul acelui tipar el sa geaseasca acel "3,2,0,8"

Editat Octombrie 29, 2015 de bandi12

[UDAR]

Sigur se poate  (?!). Cât de rapid și/sau eficient ? Cine știe ... Ideea e să nu ne blocăm în tipare . E posibil să nu existe funcții dedicate pentru asta . Nu-i nimic, le creem . E important , cum spuneam , domeniul de definiție pentru valorile din șir. Dacă acesta reprezintă o mulțime finită - sigur - și relativ restrânsă (?) algoritmul se poate optimiza . Deci - caut după X . dacă nu-l găsesc , nu mai caut după XY , XYZ , etc . Deasemenea , dacă știm exact ce reprezintă acele valori se poate face o ”comprimare” a domeniului de definiție - care poate fi eventual vitală pentru reușita algoritmului . În cazul nostru , din câte am înțeles , avem niște durate . E deci foarte probail ca 2,73 == 2,75 . Și atunci ? Nu caut nici după 2,73 nici după 2,75 ci după 2,7 cu toleranța respectivă . În fine , aștept ceva mai multe detalii dar sunt tot mai convins că se poate .

[bcristian]

Evident ca se poate. Dar in primul rand trebuie explicat clar ce si cum face dispozitivul, si ce vrea sa obtina. Rezolvarea problemei la modul general este extrem de lenta, orice optimizare permisa de contextul real conteaza.

[Vizitator]

nu stiu de ce am impresia ca nu sunt inteles.

acel 3,2,0,8 este un exemplu !

de fapt, el este o necunoscuta.

 

procedura trebuie sa .... hai sa simplificam putin lucrurile sa ne intelegem.

 

PROBLEMA:

 

priviti sirul de numere: {2,8,2,7,3,1,2,8,1,7,3,2,0,8,7,5,0,7,2,8,4,5,3,2,0,8,7,1,2,8}

exista secvente repetate ?

daca da, care secventa este cea mai lunga ?

 

cum ati obtinut asta ?

 

PS: acum stiu sigur ca sunt inteles.

Sigur se poate  (?!). Cât de rapid și/sau eficient ? Cine știe ... Ideea e să nu ne blocăm în tipare . E posibil să nu existe funcții dedicate pentru asta . Nu-i nimic, le creem . E important , cum spuneam , domeniul de definiție pentru valorile din șir. Dacă acesta reprezintă o mulțime finită - sigur - și relativ restrânsă (?) algoritmul se poate optimiza . Deci - caut după X . dacă nu-l găsesc , nu mai caut după XY , XYZ , etc . Deasemenea , dacă știm exact ce reprezintă acele valori se poate face o ”comprimare” a domeniului de definiție - care poate fi eventual vitală pentru reușita algoritmului . În cazul nostru , din câte am înțeles , avem niște durate . E deci foarte probail ca 2,73 == 2,75 . Și atunci ? Nu caut nici după 2,73 nici după 2,75 ci după 2,7 cu toleranța respectivă . În fine , aștept ceva mai multe detalii dar sunt tot mai convins că se poate .

 

din nou, te-ai prins. eu ma gandeam sa fac ajustarea asta in cod, dar prima data sa ma lamuresc cum sa obtin..."ce caut"..in asa fel incat ..sa iau toate combinatiile posibile si imposibile...

 exemplu: "a,b,c,d,e,f,g,h,i" => a | ab | abc | bc | abcd | bcd | abcde | cd | bcde | .........etc

Editat Octombrie 29, 2015 de Vizitator

[Bandi Szasz]

int array={1,2,3,4,5,6,7,8,9}int combinatii[][];#define min 2#define max 5for(int i=0;i<array.size;i++) for(int j=i+min;j<i+min+max;j++)  {     if(i > array.size || j > array.size)       break;     combinatii[i+j][] = Array.copy(array,i,j);  }

Ceva de genul acesta o sa iti returneze toate combinatiile intre min si max deci combinatii formate din minim doua numere si maxim 5. 

 

Array.copy insamna ca se copieaza toate numerele incepand de la pozitia "i" pana la pozitia "j". 

 

Este doar un pseudocod, nu stiu ce are si ce nu Arduino IDE  ( are functie de copiat array sau trebuie facut manual, etc... )

Editat Octombrie 30, 2015 de bandi12

[Vizitator]

nu are. probabil trebuie facut cu memcpy.

am abandonat ideea din cauza ca...chiar daca as gasi o rezolvare, nu ar fi suficient de rapida, sa-mi citeasca radio..

 

ramane doar ca studiu de caz.

 

vroiam sa capturez si recunosc cheia originala a unei masini, nu pentru prostioare, dar ca sa pot prelua comanda direct de la ea..

eu vad cheia, cu codurile aferente, dar...in lipsa unei decodari..ma rog. nu sunt suficient de bun pentru asta.