Subsequencia em Delphi

Delphi

03/02/2015

Olá pessoal, tenho o seguinte exercício:

Considere alguma sequência de elementos (difere de um mero conjunto de elementos por
de nir uma ordem entre os seus membros). a) Enumere, ent~ao, todas as subsequ^encias n~aocont
nuas de uma dada sequ^encia. b) Liste todas as permutac~oes do conjunto de elementos
da sequência.


1. Uma subsequência sempre contem algum subconjunto de elementos da sequência, na
mesma ordem.
2. Uma subsequência contínua e aquela em que nenhum elemento esta faltando, entre o
primeiro e o ultimo elemento da subsequência.
3. Exemplo de subsequ^encias n~ao contnuas:
(1,2,3,4) ) [[1, 2, 4], [1, 3, 4], [1, 3], [1, 4], [2, 4]]
4. Exemplo de permutacão:
(1,2,3,4) ) [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1]]

Não estou pedindo resposta, só quero uma ideia para clarear o racicínio. Como posso fazer para montar cada subsequência com os números digitados ? Não sei como poderia fazer com que os números digitados dentrdo TEdit sejam "separados" e dessa forma montar a sequência?

Não tenho experiência em Delphi, comecei a aprende a pouco tempo, mais uma vez, não estou pedindo resposta, só quer uma ideia para o raciocínio. Desde já, agradeço!
Roberto

Roberto

Curtidas 0

Respostas

Cauê Nishijima

Cauê Nishijima

03/02/2015

Ainda precisa da resposta?
GOSTEI 0
Roberto

Roberto

03/02/2015

Opa, amigo! Poxa, de uma ajuda sim...não consegui fazer ainda, se puder me dar uma ideia de como posso implementar, agradeço!
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

Antes de te responder, me tira algumas dúvidas...

1 - No primeiro caso de sequencia não continua, não é continua a numeração ou a posição dos números?

Ex.:
Ao invés dos números [1234] do exemplo...se eu digita-se os números [1235], 1235 já seria uma numeração já não continua já que falta o 4?

2 - No exemplo da permutação, a permutação é só com o primeiro número? Pois no seu exemplo ficou faltando algumas permutações:

(1,2,3,4)
[[1, 2, 3, 4]]
[[2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1]]
[[1, 3, 2, 4], [1, 3, 4, 2]]
[[3, 1, 2, 4], [1, 2, 4, 3]]
[[4, 1, 2, 3], [1, 4, 2, 3]]
GOSTEI 0
Roberto

Roberto

03/02/2015

Então, no primeiro caso continua quer dizer que entre o primeiro número e o último nenhum valor falta, no meu caso ela não é contínua, ou seja entre o primeiro e o último número nem todos os valores estão contidos. Nesse caso, eu acho que ela não é contínua na posição.

E no segundo caso, são todas as permutações, no exemplo dado só mostrado com o número 1, mas o certo seria com o resto também. Eu fiz até um código em Pascal para ele permutar, mas o algoritmo não dá todas as permutações. Se você quiser dar uma olhada, segue o código:

pROGRAM LE;

uses crt;

VAR
   j,I:INTEGER;
   avanca,seq:string;
   aux:string[1];
begin
   writeln('Digite abaixo a sequencia para trocar');
   read(seq);
for i:= 1 to length(seq) do
    begin
    if seq[i] <> ',' then
    avanca:=avanca + seq[i]
    end;
for i:=1 to length(avanca) do
begin
for j:=i+1 to length(avanca) do
    begin
    aux[0]:=avanca[i];
    avanca[i]:=avanca[j];
    avanca[j]:=aux[0];
    writeln(avanca);
    end;
end; 
readkey;
end.


E obrigado pela atenção, Cauê!
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

Segue resolução:

- Crie um novo projeto, deixei o formulario com o nome padrão Form1
- Adicione um Edit (eu chamei de edtSequencia)
- Adicione 2 ListBox, para receber o resultado da sequencia não continua e da permuta (eu chamei de lstSubSequenciaNaoContinua e de lstPermutacao)
- Adicione 2 Buttons, para efetuar os cálculos da sequencia não continua e da permuta (eu chamei de btnCalcularSubSequenciaNaoContinua e de btnCalcularPermuta


Vamos começar pela Permutação por ser mais simples, segue código do evento onClick do btnCalcularPermuta:

procedure TForm1.btnCalcularPermutaClick(Sender: TObject);
var
  caracterSelecionado: string;
  stringSemCaracterSelecionado: string;
  prefixo, sufixo: string;
  I: Integer;
begin
  caracterSelecionado := Copy(edtSequencia.Text, 1, 1);
  stringSemCaracterSelecionado := Copy(edtSequencia.Text, 2,
    length(edtSequencia.Text));

  for I := 0 to Length(stringSemCaracterSelecionado) do
  begin
    prefixo := Copy(stringSemCaracterSelecionado,0,I);
    sufixo := Copy(stringSemCaracterSelecionado,I+1, length(stringSemCaracterSelecionado));

    lstPermutacao.Items.Add(prefixo + caracterSelecionado + sufixo);
  end;
end;



Agora para o calculo da sequencia não continua crie 2 procedures, uma chamada calcularNumeros e outra verificaSeNumeroEntraNaLista

Código do calcularNumeros

procedure TForm1.calcularNumeros(numeros: string);
var
  tamanho, J, I: Integer;
  substring: string;

  sequencia: Boolean;
begin
  tamanho := length(numeros);
  for I := tamanho downto 3 do
  begin
    for J := 0 to I - 1 do
    begin
      substring := Copy(numeros, 0, I);
      substring := Copy(substring, 0, J) + Copy(substring, J + 2,
        length(substring));

      verificaSeNumeroEntraNaLista(substring);

      if length(substring) >= 3 then
        calcularNumeros(substring);
    end;
  end;
end;


Código do verificaSeNumeroEntraNaLista

procedure TForm1.verificaSeNumeroEntraNaLista(substring: string);
var
  numeroAtual, numeroAnterior, I: Integer;
begin
  numeroAnterior := StrToInt(Copy(substring, 1, 1));
  for I := 2 to length(substring) do
  begin
    numeroAtual := StrToInt(Copy(substring, I, 1));
    if numeroAnterior + 1 <> numeroAtual then
    begin
      if lstSubSequenciaNaoContinua.Items.IndexOf(substring) < 0 then
        lstSubSequenciaNaoContinua.Items.Add(substring);
      Break;
    end
    else
      numeroAnterior := numeroAtual;
  end;
end;


E finalmente no evento onClick do button btnCalcularSubSequenciaNaoContinua:

procedure TForm1.btnCalcularSubSequenciaNaoContinuaClick(Sender: TObject);
begin
  calcularNumeros(edtSequencia.Text);
end;


Qualquer dúvida, ou se entendi algo erroneamente me avise.
Espero ter ajudado, abraços

Att.Cauê Nishijima
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

Vou arrumar o código da permuta e já posto.
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

Arrumando a permuta:

- Crie a seguinte procedure : 

procedure TForm1.permutar(posicao: integer);
var
  I: integer;
  prefixo, sufixo, novaString: string;
  caracterSelecionado, stringSemCaracterSelecionado: string;
begin
  caracterSelecionado := Copy(edtSequencia.Text, posicao, 1);

  stringSemCaracterSelecionado := Copy(edtSequencia.Text, 1, posicao - 1) +
    Copy(edtSequencia.Text, posicao + 1, Length(edtSequencia.Text));

  for I := 0 to Length(stringSemCaracterSelecionado) do
  begin
    prefixo := Copy(stringSemCaracterSelecionado, 0, I);
    sufixo := Copy(stringSemCaracterSelecionado, I + 1,
      Length(stringSemCaracterSelecionado));
    novaString := prefixo + caracterSelecionado + sufixo;
    if lstPermutacao.Items.IndexOf(novaString) < 0 then
      lstPermutacao.Items.Add(novaString);
  end;
end;


E no onClick do btnCalcularPermuta :

procedure TForm1.btnCalcularPermutaClick(Sender: TObject);
var
  I: integer;
begin
  for I := 1 to Length(edtSequencia.Text) do
    permutar(I);
end;


Agora acho que esta certo, e vai te ajuda. Abraços!

Att. Cauê Nishijima
GOSTEI 0
Roberto

Roberto

03/02/2015

Poxa, sem palavra para agradecer, Cauê! Muito obrigado tanto pela atenção quando a boa vontade. Eu irei fazer o meu exercício e não copiar do seu, e entender a lógica do programa, vou tentar entender tudo. Obrigado, mais uma vez!
GOSTEI 0
Roberto

Roberto

03/02/2015

Po amigo, testei ele aqui só que ele imprime somente uma certa quantidade de permutações e de subsequências. No entanto, era preciso que todas fossem mostradas, pode me dar mais uma ajuda? Sem querer te explorar, não precisa fazer tudo não, só me dar uma "luz" do caminho que devo seguir, de qualquer forma eu to tentando aqui também e agradeço a ti por ter me ajudado!
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

E ai Roberto, beleza?
Então eu testei aqui e aparentemente faz todas as permutas e todas as subsequencias, qual seu email pra eu te mandar o fonte do meu
GOSTEI 0
Roberto

Roberto

03/02/2015

O meu é rfalves94@gmail.com. Obrigado pela atenção! =)
GOSTEI 0
Fabricio

Fabricio

03/02/2015

Caro Cauê,

Boa tarde.

Estou com problemas com o código de permutação. Você poderia mandar o fonte para meu e-mail - fabricioronaldo@globo.com?

Agradeço pela ajuda..

Obrigado.
GOSTEI 0
Priscila

Priscila

03/02/2015

Prezado Cauê,

Boa tarde.

Também estou com problemas com o código de permutação. Você poderia mandar o fonte para meu e-mail - pricalper@gmail.com?

Agradeço pela ajuda..

Obrigado
GOSTEI 0
Cauê Nishijima

Cauê Nishijima

03/02/2015

Olá Priscila te enviei o código por e-mail, mas de qualquer forma subi o arquivo no Google Drive e vou compartilhar o link aqui: Permutação e Subsequência
GOSTEI 0
POSTAR