• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

suzy

[C] Ajuda: Permutação

28 mensagens neste tópico

Considere que um número a é uma permutação de um número b se os dígitos

de a formam uma permutação dos dígitos de b, isto é, possui os mesmos

dígitos, eventualmente por outra ordem.

Exemplo: 5412 é uma permutação de 4215, mas não é uma permutação de

4155.

Obs.: Considere que o dígito 0 (zero) não aparece nos números.

Usando a função da alínea anterior, faça um programa que lê dois inteiros

positivos a e b e responda se a é permutação de b. :( como faço isto??

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens de contar o número de vezes que cada dígito aparece em cada número, uma maneira de o fazer é transformar o número para uma string, percorrer todos os caracteres e somar num array o número de ocorrências de cada um. Depois comparas o array dos dois números para ver se são semelhantes.

//Corrigidos alguns erros ortográficos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

uma solução consiste em converter os números numa string, para cada algarismo na primeira string, verificava-se se ele também existia na segunda. se não existia, o resultado era falso, se existia passava o algarismo na segunda string para 0 (por exemplo, para saber que aquele já foi utilizado) e continuava o processo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se pode transformar os inteiros em strings, e tendo em conta que uma string é um (masculino) array de caracteres, pode trabalhar logo a partir desses arrays:

- se os arrays tiverem tamanhos diferentes, não é permutação;

- se tiverem o mesmo tamanho, percorre o array com o número a e para cada algarismo de a procura no array que contém b a ver se existe; se existir, modifica o valor dessa posição do array b (não convém alterar para 0 porque ia dificultar a procura seguinte, pode alterar-se por exemplo para o caracter a); se não existir, não é permutação.

P.S. Enquanto estava a escrever, o Rui Carlos postou. Enquanto a solução é praticamente igual, resolvi postar na mesma por causa do problema irritante de "a" array.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:( malta!! então vou ter de criar 2 vectores e colocar os numeros para dentro de cada vector. Uma questão tendo eles a mesma dimensão, um pode ter 3 numeros e o outro 4  ;), mas como vou contar o tamanho de cada vector, visto terem a mesma dimensão?? :shocking:

#include<stdio.h>
# define N 6

main()
{
int n1[N], n2[N], tamanho=0,i;

   printf(" introduza o 1 numero inteiro\n");
   scanf("%d",&n1[i]);
   printf(" introduza o 2 numero inteiro\n");
   scanf("%d",&n2[i]);
     
      for (i=0;i<N;i++);
         {
         tamanho=tamanho+1

tenho que fazer 2 ciclos? certo?, mas como diferencio cada um dos vectoresm, se tem a mesma dimensão??  :-[ thanks

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

;) é so definir 2 contanstes diferentes, né?

tipo

#define N 6

# define A 6

e assim vou contar o tamanho de cada vector :( certo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para contar o tamanho de um vector podes usar o strlen

int tamanho = 0;

tamanho = strlen(vector);

printf("O tamanho do vector e %d ", tamanho);

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

suzy, sempre que meteres código no fórum usa a ferramente GeSHi para facilitar a leitura do código. Obrigado! :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:wallbash: nao tou a perceber como se faz isto, o perceber ate percebo agora passar para a lngugen  :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:hmm: mas qd se #define N 6 E COLOCA-SE  int vetor [N], já se ta a definri o vector certo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vou tentar explicar o que foi dito:

	char vector[6];		//Guarda espaço em memoria para 6 caracteres
int x=5478, pos_ocupadas;
sprintf(vector, "%d", x);
pos_ocupadas=strlen(vector);	//Quantos caracteres estão no vector?
printf("o numero de posiçoes ocupadas no vector é %d", pos_ocupadas);

O que a função strlen faz é contar quantos caracteres estão antes de um caracter '\0' (caracter terminador), que está sempre no fim de uma string de C. Os profs não explicaram isto?

EDIT: já agora, em pos_ocupadas fica o valor 4. E atenção ao tamanho que escolhes na declaração do vector! Tem que ser pelo menos o comprimento máximo do número que vais aceitar +1. Se vais usar uma variável do tipo int para pedir os números, deves declarar o vector com 12 posições, visto que um valor sem sinal a 32 bits está entre -2.147.483.648 e 2.147.483.647 (10 algarismos + 1 caracter para o sinal).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mas a função strlen so server para caracteres certo? o que eu quero sao digitos :( provalvemente vou ter de pedri ao utilizador os numeros, garda-los num vector de inteiros e depoiis fazer se v!=0 conta++;  :eek: é assim?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O método que estávamos a dizer era transformares o inteiro que recebes numa string, o que facilitava o resto do problema. Não pode ser assim? é que também se arranja solução...! :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A maneira mais fácil de resolver este problema é a seguinte:

Ler ambos os números para dois vectores.

(ou ler o número e converter para vector, usando o sprintf por exemplo)

Ordenar os dois vectores.

Comparar se ambos os vectores são iguais.

Além de mais rápido, parece-me bastante mais simples.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:hmm: mas para dois vectores serem iguais, teria que cada indice do vector v[ i ], ter o numero igual ao do outro vector

o que nao acontece neste problema :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

:hmm: mas para dois vectores serem iguais, teria que cada indice do vector v, ter o numero igual ao do outro vector

o que nao acontece neste problema :(

Por isso é que ordenas o vector antes de os comparar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A maneira mais fácil de resolver este problema é a seguinte:

Ler ambos os números para dois vectores.

(ou ler o número e converter para vector, usando o sprintf por exemplo)

Ordenar os dois vectores.

Comparar se ambos os vectores são iguais.

Além de mais rápido, parece-me bastante mais simples.

Depende dos vectores, e depende da utilização. Não me parece que, em geral, ordenar e depois comparar seja mais rápido, porque tens que ordenar os 2 vectores e depois percorrê-los, enquanto que pelo método descrito pelo Rui Carlos e por mim, um dos vectores é percorrido apenas uma vez.

E com algumas optimizações pode tornar-se ainda mais eficiente. Por exemplo, quando se encontra um algarismo pretendido coloca-se o ultimo algarismo do 2º vector nessa posição e coloca-se um '\0' na ultima posição.

E ainda a vantagem de que quando se encontra um algarismo que não existe no 2º vector, termina a execução.

Para números muito extensos talvez o que dizes aconteça... mas como neste caso são no máximo 10 algarismos, penso que não.

Agora fiquei curioso e vou experimentar qual dos dois é mais rápido... :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

em termos de complexidade, o melhor ainda é o do Triton, pois terá complexidade linear. a do Warrior terá complexidade n*log n (poderia ter complexidade linear mas tornaria a ordenação mais complexa...)  e o nosso terá complexidade quadrática, mas vamos trabalhar com inteiros, que em princípio nunca terão mais de 10 dígitos, logo qualquer um dos algoritmos é perfeitamente aceitável.

quanto ao que é mais simples, é muito relativo, mas ordenar um array também não me parece muito simples, pelo menos para o autor do tópico (mesmo usando as funções que já existem).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Confesso que percebo pouco de complexidade de algoritmos (o que é grave porque vou ter um teste sobre isso dentro de 2 dias :(), mas parece-me que para dados desta magnitude andar a mexer com algoritmos de ordenação aumenta a complexidade...

Citando um engenheiro, "é matar moscas com um canhão"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

complicações...complicações.....

Lê dois inteiros.

Converte-os para string.

Falha se o tamanho das strings for !=

Falha Se a string B contém algum char que não esteja na String A

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

int  length(char string[])
{
    int             index;      
    for (index = 0; string[index] != '\0'; ++index)
        continue; 
    return (index);
}


/* ANSI C itoa */
char* itoa(int val, int base){
	static char buf[32] = {0};
	int i = 30;
	for(; val && i ; --i, val /= base)
		buf[i] = "0123456789abcdef"[val % base];
	return &buf[i+1];
}


int main()
{    

   int C1=45432,C3=54428;

  char Original[5];
  char Teste[5];

  strcpy(Original,itoa(C1,10));
  strcpy(Teste,itoa(C3,10));

  if (length(Original)!=length(Teste)){
    printf("Permutação invalida\n");
    exit(0);
  }

  for (int index = 0; Teste[index] != '\0'; ++index){			
   if (!strchr(Original, (int)Teste[index])){
      printf("Permutação invalida\n");
      exit(0);
   }  
  }

  printf("Permutação valida\n");    
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso foi basicamente o que nós dissemos... mas com código, que era suposto ser ela a fazer :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

para quê definir uma função 'itoa' se vais trabalhar em base 10? para quê definir a função 'length'? "complicações...complicações....."

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não é querer ser mauzinho nem deitar mais achas para a fogueira mas esse código para quem está a iniciar na linguagem C e/ou algoritmia é quase chinês.

Penso que devia estar o mais simples possível usando os métodos ensinados no 1º ano como deve ser o caso dela. :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

para quê definir uma função 'itoa' se vais trabalhar em base 10? para quê definir a função 'length'? "complicações...complicações....."

->Base 10 .

Procura a assinatura da função itoa em ANSI C.

->length

ANSI C...

Se quiseres tmb te explico o porque do ansi C.

Podes dizer que poderia ter feito isto com sprintf...

Sim, tens razão, mas prefiro esta abordagem.

Não é querer ser mauzinho nem deitar mais achas para a fogueira mas esse código para quem está a iniciar na linguagem C e/ou algoritmia é quase chinês.

Penso que devia estar o mais simples possível usando os métodos ensinados no 1º ano como deve ser o caso dela. 

-Tens razão.Se bem que se ele/ela tiver algum interesse em aprender , estuda o código e tenta fazer variantes deste mais simples.

/ing

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora