Problema

[•ucc_5]

Deci am gasit o problema pe care pur si simplu nu o pot rezolva , desi la inceput pare usoara.
Fie un sir de litere mici ale alfabetului englez. Oricare 2 (sau mai multe) caractere alaturate, de acelasi fel, pot fi eliminate din sir. Se cere eliminarea cat mai multor caractere astfel incat sirul obtinut sa fie cat mai mic si sa se afiseze sirul. Daca exista mai multe siruri se vor afisa toate.
Ex1: abbfggh => afh
Ex2: abbaab => b sau a

[•alexandru92]

Mie problema mi se pare extrem de simpla.

Cod:

#include<stdio.h>
#include<string.h>
char s[100],c;
int i,n;
int main()
   {
        gets(s); //citesc sirul
        n=strlen(s)-1; //lungimea sirului
        for(i=0;i<n;++i)
            if(s[i]==s[i+1])  //daca am dat peste 2 litere asemanatoare
              {c=s[i];
                while(c==s[i]) strcpy(s+i,s+i+1);  //sterg elementul din sir
                 i=-1; n=strlen(s)-1; //incep de la inceput
              }
        puts(s); //afisez sirul :D
        return 0; 
  }

[•sima_cotizo]

Ce te faci daca ai ceva gen "aaabbbacaa" ? Cred ca algoritmul tau iti zice ca ramane "ac", dar de fapt raspunsul este "c".

[•alexandru92]

Oricare 2 (sau mai multe) caractere alaturate, de acelasi fel, pot fi eliminate din sir.

[•sima_cotizo]

Oricare 2 (sau mai multe) caractere alaturate, de acelasi fel, pot fi eliminate din sir.

Hint: elimini intai "b"-urile

[•ucc_5]

Pai pot fi eliminate oricare 2 , dar trebuie eliminate astfel incat sa se obtin un sir cat mai mic.
Programul tau pentru aabbacaa afisaza ac, cand ar trebui sa afiseze c. Si pentru siruri mai mari se impute treaba   

[•wefgef]

Hint: Problema se rezolva cu programare dinamica .

[•ucc_5]

Hint: Problema se rezolva cu programare dinamica .

M-am gandit si la asta, dar n-am gasit recurenta.

[•alexandru92]

Dar daca am retine intr-o stiva sirurile pe care le stergem consecutiv.Adica daca avem aaabbb, in stiva sa retinem doar a si b.
Apoi cand dam de un caracter care nu este egal cu urmatorul sa vad daca in spatele lui ar fi fost un sir care l-ar fi incadrat. Adica daca luam sirul dat de Simo Cotizo: "aaabbbacaa".
In stiva punem : 'a'. Si inlocuim in sir 'a' cu . si vom aveam "...bbbacaa"
Urmeaza :'b'.  Punem si pe b in stiva si modificam sirul "......acaa"
Pai acum 'a'!='c'. Dar in spatele lui a este un '.' deci vedem daca in stiva avem un sir  a. Si avem, il inlocuim pe a cu '.' Si continuam. Vine 'c'!='a' si cum nici in stiva nu se afla un sir care sa inceapa cu 'c', golim stiva si nu inlocuim 'c' cu '.' .Continuam cu parcursul vectorului. Dam de 'a' si punem 'a' in stiva si il inlocuim peste tot cu '.' si obtinem sirul '......c..'
N-am testat ideea decat pe  sirurile mentionate mai sus

Cod:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[100],v[100],c;
int n,i=1,vf=-1;
int main()
{
	gets(s);
	n=strlen(s)-1; 
	for(i=0;i<n;++i)
		if(s[i]!='.'&&s[i+1]!='.')
		  {if(s[i]==s[i+1])
		     {
				 c=s[i];
				 while(c==s[i]&&i<=n) s[i++]='.';
				 v[++vf]=c; i=0;
		     }else if(vf) {vf=-1; memset(v,0,sizeof(v));}
		  }else if(s[i]=='.'&&s[i+1]!='.')
		          {if(strchr(v,s[i+1])) s[i+1]='.',i=0;
				   else if(vf) vf=-1,memset(v,0,sizeof(v));
		          }else if(s[i]!='.'&&s[i+1]=='.')
		                  {if(strchr(v,s[i])) s[i]='.',i=0;
						   else if(vf)vf=-1,memset(v,0,sizeof(v));
				          }
	for(i=0;i<=n;++i)
		if(s[i]!='.') printf("%c",s[i]);
	system("PAUSE>NULL");
	return 0;
}

[•wefgef]

Ideea e proasta. Asa cum am mentionat mai sus, e nevoie de programare dinamica.

[•Mishu91]

Hint: Problema se rezolva cu programare dinamica .

M-am gandit si la asta, dar n-am gasit recurenta.

Pai iti tii un sir in care tii minte ultima aparitie a fiecarui caracter, si acel caracter il poti elimina doar daca intre pozitia lui si pozitia ultimei aparitii poti elimina toate caracterele
Cam ceva de genu asta ar fi.

[•ucc_5]

Cred ca ai dreptate mishu, am incercat si se pare ca merge. Totusi, nu stiu daca solutia asta trateaza toate cazurile.
Intre timp mai am o rugaminte. Poate sa-mi demonstreze cineva "Problema specatacolelor". Am stat mult sa ma gandesc de ce e asa si pur si simplu nu inteleg logica solutiei. Ma poate ajuta cineva?

[•toni2007]

Problema se rezolva sortand intervalele dupa capatul din dreapta, apoi luand pe rand intervalele care au capatul din stanga mai mare decat ultimul capat din dreapta. Demonstrez intai de ce voi lua primul interval.

Demonstratia se face prin metoda reducerii la absurd:

Presupunem prin reducere la absurd ca nu vom lua primul interval, si vom lua un interval cu capatul din dreapta Dr. Atunci Dr va fi mai mare decat capatDr[1], caz in care vom avea mai putine sanse de a obtine maximul, sau Dr va fi egal cu capatDr[1], caz in care nu se influenteaza cu nimic (sunt sortate). (Contradictie).

Demonstratia ca la fiecare pas, avand fixat capatDreaptaUltim, vom alege elementul j minim astfel incat capatSt[j] > capatDreaptaUltim, se face analog. (Daca nu intelegi detaliez).

[•ucc_5]

Am inteles putin, dar daca poti sa detaliezi mai mult as fi recunoscator 

Gata, am inteles treaba cu problema spectacolelor


Mai am o intrebare. Daca avem doua siruri x,y formate din litere mari si mici ale alfabetului englez , cum le sortam lexicografic ? "a" e mai mic ca "A" , nu ? daca da atunci nu mere sa compar codul fiecarei litere (cu strcmp) . Cum se aranjeaza lexicografic in cazul asta ? cu strcmp sau fac functie separata ca sa considere "a" < "A" (analog pt toate literele) ?

[editat] Foloseste butonul "Modifica"

[•sima_cotizo]

Ti-am mai spus o data sa-ti editezi mesajele. Chiar nu ai citit ce era cu rosu? 

Ca sa iti raspund la intrebare: in mod normal 'A'<'a' (ceea ce e indicat si de codurile ASCII), deci 'Abc'<'abc'. Daca tu vrei ca 'a'<'A' atunci faci o functie de comparare de mana. Daca 'a'=='A' atunci poti sa compari cuvintele dupa ce le-ai trecut la uppercase (dar poate fi mai complicat decat sa faci compararea de mana daca, de exemplu, trebuie sa le afisezi la sfarsit in forma in care le-ai citit).

[•ucc_5]

Am inteles, si scuze pentru treaba cu editatul, sunt obijunuit prost de pe alte forumuri unde nu zice nimeni nimic pentru ca ai voie sa-l editezi in maxim 5 minute.