1

Boa noite, pessoal. Preciso implementar um programa que imprima sempre uma sequência de três números onde não pode haver nenhuma repetição.

Ex.: t = 4.

Output esperado: (0 1 2) (0 1 3) (0 2 3) (1 2 3)

O programa executa para t = 4, no entanto, para t = 10, ele executa apenas até certo ponto (até i = 6). Já testei cada parte do código e não consigo encontrar o erro, será que alguém poderia me ajudar?

Obrigada! :)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct{
  int v1;
  int v2;
  int v3;
}Triangulo;

int main(){
int n;
scanf("%d", &n);

Triangulo T[n];

int t;
t = (n*(n-1)*(n-2))/6;
printf("t = %d\n", t);

int c = 0;
int f = c+1;
int s = f+1;

for(int i = 0; i < t; i++){
  T[i].v1 = c;
  T[i].v2 = f;
  T[i].v3 = s;

if(s != n-1){
  s++;
}else if((s == n-1)&&(f == n-2)){
  c++;
  f = c+1;
  s = f+1;
}else if(s == n-1){
  f++;
  s = f+1;
}
}

for(int j = 0; j < t; j++){
  printf("%d %d %d\n", T[j].v1, T[j].v2, T[j].v3);
}


  return 0;
}

3
  • Você pode colocar o código completo? No parte que postou não está sendo definido n, T e t. Você deseja só as triplas com valores diferentes ou as permutações? Por exemplo, você quer que tenha (0 1 2) e (2 1 0) na saída, ou basta (0 1 2)? Commented 7/05/2019 às 0:30
  • Olá. Com o exemplo que você deu, apenas (0 1 2) basta. Vou atualizar o post e colocar o código completo :) Commented 7/05/2019 às 0:51
  • Você quer todas as permutações que são do tipo (i j k) tal que i < j < k, correto? Eu deixei uma resposta que faz isso, mas ainda não tenho certeza se é exatamente isso que você quer. Commented 7/05/2019 às 1:02

1 Resposta 1

1

Você quer todas as permutações que são do tipo (i j k) tal que i < j < k, correto? Você não vai conseguir fazer isso usando apenas um for. Observe que quando fixamos valores para i e j, por exemplo, ainda temos os valores de j+1 até t-1 para atribuir a k. Vejamos um exemplo:

Considere que em determinado momento do algoritmo i = 1 e j = 3, e que t = 10. As sequências possíveis fixando esses valores seriam:

(1 3 4)
(1 3 5)
(1 3 6)
(1 3 7)
(1 3 8)
(1 3 9)

Note que precisamos de um for que vai de j+1 até t-1 apenas para iterar os possíveis valores de k. Da mesma forma, se fixarmos apenas o valor i, precisamos de um for para percorrer os possíveis valores para j e, para cada valor de j, um novo for para valores de k. Acho que já ficou claro que precisamos de um for para cada variável.

Segue uma implementação:

#include <stdio.h>

int main(void) {

    int t;

    scanf("%d", &t);

    // Considera todos os valores de 0 até t-1
    for(int i = 0; i < t; i++){

        // Considera todos os valores de i+1 até t-1 para impedir que os valores se repitam
        for(int j = i+1; j < t; j++){

            // Considera todos os valores de j+1 até t-1 para impedir que os valores se repitam
            for(int k = j+1; k < t; k++){
                printf("(%d %d %d) ", i, j, k);
            }
        }
    }

    printf("\n");
    return 0;
}

Demonstração aqui.

24
  • Entendi! Meu problema é que preciso encontrar uma solução em até ordem linear, ou seja, não poderei executar esses 3 loops. Você teria alguma sugestão de como eu poderia resolver isso? Commented 7/05/2019 às 1:17
  • Então acho que você não precisa imprimir todas as sequências, já que o número de subconjuntos de tamanho 3 em n elementos é da ordem de n^3, então não dá para imprimir todos em tempo linear. Você pode verificar se é exatamente isso que precisa fazer? É uma questão? Se sim, poderia adicionar o enunciado? Commented 7/05/2019 às 1:29
  • Então, eu tenho um trabalho para entregar sobre Árvore Geradora Mínima e eu tenho que executar em tempo O(m), onde m é o número de arestas. Eu quero usar esse trecho para gerar subconjuntos de tamanho 3 que seriam vértices de triângulos dentro do meu grafo original. Nesse trecho eu uso o for em função de n, basicamente, então ele acaba ficando maior que o número de arestas e isso, pela especificação, não poderia acontecer. Commented 7/05/2019 às 1:35
  • Entendi. Existe alguma propriedade particular no grafo de entrada? Não existe algoritmo O(m) para o problema da MST em grafos arbitrários (ao menos não conheço e não achei nada sobre nas buscas que fiz). Existem algoritmos para a MST que são lineares no grafo, isto é O(m + n) e é possível achar uma árvore geradora em O(m), mas não a mínima. Também não consegui ver como o algoritmo acima te ajuda com a árvore geradora mínima. Você tá seguindo algum algoritmo específico? Commented 7/05/2019 às 11:14
  • Na verdade eu estava tentando coisas sem base em nenhum algoritmo, porque minhas buscas também me indicaram isso que você encontrou. Reli a especificação do trabalho e tentarei resolver com caminhos mínimos ao invés de MST's. De toda forma, obrigada pela atenção e pelas respostas! Commented 9/05/2019 às 0:44

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .