Jump to content

[Resolvido] Maior sequencia crescente


askazy
 Share

Recommended Posts

O objetivo do programa é encontrar o tamanho da maior subsequencia crescente, dado uma sequência de tamanho n:

exemplo:

Entrada 8 4 1 2 3 0 5 7 8

Saída: 4

O número 8 representa o tamanho da sequência. Não sei porque não está dando certo.

#include <stdio.h>
int main (){
  int n,i,vet[50],cont=1,maior=0;
     scanf ("%d",&n);
     for (i=0;i<n;i++) scanf ("%d",&vet[i]);
     for (i=1;i<n;i++){
         if (vet[i] > vet[i-1])
             cont++;
         else{
             if (cont > maior)
                 maior = cont;

             cont=1;
         }
     }			  
     printf ("A maior sequencia crescente tem tamanho %d\n",maior);
     system ("pause");
     return 0;
}
Link to comment
Share on other sites

Ah percebi o problema, ele só copiava a variável cont para o maior caso ele chegasse em um que quebra da sequencia, então se eu tivesse uma sequência infinita maior ele ia pegar a última sequência maior que teve uma quebra. Não sei se é a melhor solução mas ai está.

#include <stdio.h>
int main ()
{
 int n,num,aux,cont=1,maior=0,i;
 scanf ("%d",&n);
 scanf ("%d",&aux);
 for(i=1; i<n; i++)
 {
 scanf ("%d",&num);
 if (num >aux)
 {
	 cont++;
	 if (cont>maior) maior=cont;
 }

 else
 {
	 if (cont>maior) maior=cont;
	 cont=1;
 }
 aux=num;
 }
 printf ("A maior subsequencia tem tamanho %d\n",maior);
 return 0;
}
Link to comment
Share on other sites

bem ... a meu ver, como estás demasiado verde na matéria acho que o melhor é apresentar a solução a ver se aprendes com o exemplo:

#include <stdio.h>
#include <limits.h>

int main (){
 int n = 0, i = 0, count = 0, cur = 0, prev = INT_MIN;

 // saber o número de valores que serão lidos
 scanf ("%d", &n);

 // ciclo de leitura dos n valores
 while (i < n) {
   // ler o valor
   scanf (" %d", &cur);

   // se o valor lido for maio que o anterior
   if (cur > prev)
     // incrementar a contagem da sequência crescente
     count++;
   else {
     // verificar se a sequência actual é maior que a anterior
     if (max < count)
       // guardar o tamanho da sequência actual
       max = count;

     // iniciar a contagem da próxima sequência
     count = 0;
   }

   // guardar o valor lido
   prev = cur;
 }

 printf ("A maior sequencia crescente tem tamanho %d\n", max);

 return 0;
}
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Happy o seu código usa uma estrutura com coisas que agente não aprende na disciplina. Agente não usa essa biblioteca <limits.h>. As vezes as minhas soluções não são tão boas, por causa que o curso é tipo um introdutório em linguagem C padrão, então eu só escrevo baseado no que eu aprendi.

Link to comment
Share on other sites

Happy: o teu bug tem o mesmo bug que o código inicial dele. Também não acho que seja mais simples.

askazy: uma forma de dares a volta ao problema que estavas a ter é, em vez de verificares se é maior que o máximo sempre que incrementas, podes adicionar uma verificação no exterior do ciclo de forma a evitar verificar todas as iterações.

Link to comment
Share on other sites

Happy: o teu bug tem o mesmo bug que o código inicial dele.

sim, além de :

- count estar a ser atribuído a zero em vez de 1

- não estou a fazer a verificação final

- nem estou a incrementar o i

mas como o código foi feiro de cabeça ...

Também não acho que seja mais simples.

eu quando disse que se podia resolver com menos código era em relação a isto :

#include <stdio.h>

int main (void) {
 int n = 0, i = 0, prev = 0, cur, count, max;

 scanf ("%d", &n);
 max = count = scanf("%d", &prev);
 for (i = 1; i < n; ++i) {
   if (scanf(" %d", &cur))
     count = (cur > prev) ? (count + 1) : ((max = max > count ? max : count), 1);
   prev = cur;
 }
 max = max > count ? max : count;

 printf ("A maior sequencia crescente tem tamanho %d\n", max);
 return 0;
}

agora imagina o que seria o @askazy olhar para esta código ...

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

HappyHippiHippo sua logica está incorreta, o problema nao e tao simples como imaginastes, primeiro deves aprender o que é uma subsequencia, leia atentamente esse site que nele é explicado o problema e a resoluçao http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/sscm.html

O algoritmo para resolver é esse:

/* Igor Duarte - 08/05/2016
 * MAIOR SUBSEQUENCIA CRESCENTE MAXIMA
 * Em outras palavras, B[1..k] é uma subsequência de A[1..n] se existem índices i1,i2,…,ik tais que 1 ≤ i1 < i2 < … < ik ≤ n
 * e B[1] = A[i1], B[2] = A[i2], … , B[k] = A[ik] .
 */

#include <stdio.h>
#define maxSeq 200

int vetProgDinamica [maxSeq + 1];
int sequencia[maxSeq +1];

int main(){
  int i, j, tam, maior;
  while(scanf("%d", &tam), tam) {
    //lendo os elementos da sequnecia:
    for(i=1; i<=tam; i++){
      scanf("%d", &sequencia[i]);
    }

    //inicio da programaçao dinamica:
    for(j = 1; j <= tam; j++) {
      //com esse elemento ja tenho certeza que consigo subsequencia de tamanho 1:
      vetProgDinamica[j] = 1;
      //calculando a maior subsequencia que consigo com esse elemento:
      for( i=j-1; i > 0; i--) {
        if(sequencia < sequencia[j] && vetProgDinamica[i] + 1 > vetProgDinamica[j]) { //caso dois elementos iguais formem subsequencia mudar < para <=
          vetProgDinamica[j] = vetProgDinamica[i] + 1;
        }
      }
    }
    
    //percorrendo o vetor gerado na programaçao dinamica para encontrar a maior subsequencia:
    maior = 0;
    for(i=1; i<=tam; i++){
      if(vetProgDinamica[i] > maior){
        maior = vetProgDinamica[i];
      }
    }

    //imprimindo a maior:
    printf("%d\n", maior);
  }
}
Link to comment
Share on other sites

a este tipo de problema (académicos) está associado um conjunto de testes.

se a solução apresentada não foi contradita, então é de assumir que está correcta, isto porque, novamente, aqui a unica pessoa que está a assumir o que quer que seja sem ter a informação exacta do problema, és tu.

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <vector>
#include <stdio.h>
#define fori(i, n) for (int i = 0; i < (n); i++)
using namespace std;

// Longest Increasing Subsequence - LIS O(n log n)
// Fonte: http://www.maratona.dcc.ufmg.br/UFMG-TRD-2011.pdf
// Adaptado por: Jonatas Laet
void lis( const vector< int > & v, vector< int > & asw )
{
	vector<int> pd(v.size(), 0), pd_index(v.size()), pred(v.size());
	int maxi = 0, x, j, ind;
	fori(i, v.size())
	{
		x = v[i];
		j = lower_bound( pd.begin(), pd.begin() + maxi, x ) - pd.begin();
		pd[j] = x;
		pd_index[j] = i;
		if( j == maxi )
		{
			maxi++;
			ind = i;
		}
		pred[i] = j ? pd_index[j - 1] : -1;
	} // return maxi;
	int pos = maxi - 1, k = v[ind];
	asw.resize( maxi );
	while ( pos >= 0 )
	{
		asw[pos--] = k;
		ind = pred[ind];
		k = v[ind];
	}
}

int main(int argc, char *argv[])
{
	vector< int > v; //8, 4, 1, 2, 3, 0, 5, 7, 8
	vector< int > v2;
	v.push_back(8);
	v.push_back(4);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(0);
	v.push_back(5);
	v.push_back(7);
	v.push_back(8);
	lis(v, v2);
	int t = v2.size();
	//Mostrando o vetor com os valores da maior subsequencia crescente
	fori(i, t)
	{
		printf("%d ", v2[i]);
	}
	printf("\n");
	
	//Mostrando o tamanho desse vetor
	printf("%d\n", v2.size());
	
	return 0;
}

Mais informações sobre como funciona o Longest Increasing Sequence: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Link to comment
Share on other sites

10 hours ago, Jonatas Laet said:

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <vector>
#include <stdio.h>
#define fori(i, n) for (int i = 0; i < (n); i++)
using namespace std;

// Longest Increasing Subsequence - LIS O(n log n)
// Fonte: http://www.maratona.dcc.ufmg.br/UFMG-TRD-2011.pdf
// Adaptado por: Jonatas Laet
void lis( const vector< int > & v, vector< int > & asw )
{
	vector<int> pd(v.size(), 0), pd_index(v.size()), pred(v.size());
	int maxi = 0, x, j, ind;
	fori(i, v.size())
	{
		x = v[i];
		j = lower_bound( pd.begin(), pd.begin() + maxi, x ) - pd.begin();
		pd[j] = x;
		pd_index[j] = i;
		if( j == maxi )
		{
			maxi++;
			ind = i;
		}
		pred[i] = j ? pd_index[j - 1] : -1;
	} // return maxi;
	int pos = maxi - 1, k = v[ind];
	asw.resize( maxi );
	while ( pos >= 0 )
	{
		asw[pos--] = k;
		ind = pred[ind];
		k = v[ind];
	}
}

int main(int argc, char *argv[])
{
	vector< int > v; //8, 4, 1, 2, 3, 0, 5, 7, 8
	vector< int > v2;
	v.push_back(8);
	v.push_back(4);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(0);
	v.push_back(5);
	v.push_back(7);
	v.push_back(8);
	lis(v, v2);
	int t = v2.size();
	//Mostrando o vetor com os valores da maior subsequencia crescente
	fori(i, t)
	{
		printf("%d ", v2[i]);
	}
	printf("\n");
	
	//Mostrando o tamanho desse vetor
	printf("%d\n", v2.size());
	
	return 0;
}

Mais informações sobre como funciona o Longest Increasing Sequence: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

é sempre "interesante" apresentar uma solução em C++ na secção de C ...

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.