Ir ao conteúdo
  • Cadastre-se
Jessé P. de Melo

C Otimizar este código - exercício quadrado perfeito

Recommended Posts

Boa noite. Estou estudando para programar em microcontroladores, esses aparelhos tem recursos bem limitados, ou seja quanto mais otimizado melhor. 

Fiz o exercício:

Faça uma função para verificar se um numero é um quadrado perfeito. Um quadrado  perfeito e um  numero inteiro não negativo que pode ser expresso como o quadrado de outro numero inteiro. Ex: 1, 4, 9... (Definição mais completa).

Quero otimizar esse código.

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

int main(void){//2,3,5,7
    int num;
    int quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
int quadrado_perfeito(int x){
   int exp_n2=0;
   int exp_n3=0;
   int exp_n5=0;
   int exp_n7=0;
   int teste1=0;
   int teste2=0;
   int teste3=0;
   int teste4=0;

    while(x>1){
        while (x%2==0){
            x=x/2;
            exp_n2++;
        }
        while (x%3==0){
            x=x/3;
            exp_n3++;
        }
        while (x%5==0){
            x=x/5;
            exp_n2++;
        }
        while (x%7==0){
            x=x/7;
            exp_n7++;
        }
    }
    if(exp_n2==0||exp_n2%2==0){
        teste1=1;
    }
    if(exp_n3==0||exp_n3%2==0){
        teste2=1;
    }
    if(exp_n5==0||exp_n5%2==0){
        teste3=1;
    }
    if(exp_n7==0||exp_n7%2==0){
        teste4=1;
    }

    if(teste1&&teste2&teste3&&teste4==1){
        printf("E' um quadrado perfeito");
    }
    else{
        printf("Nao e' um quadrado perfeito");
    }
}

.

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Tem como só fazer por inteiros e usando um algoritmo básico para achar raiz. Mas se quiser uma maneira rápida tenho esse código:

 

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

void is_square_num(unsigned int S)
{
	unsigned int tmp = sqrt(S);
    if (tmp*tmp == S)
        puts("É quadrado");
    else
        puts("Não é quadrado");
}

int main(void)
{
	unsigned int num, raiznum;
	puts("Digite número: ");
	scanf("%u", &num);
	is_square_num(num);
	return 0;
}

Lembrando que ele usa a biblioteca `math.h` então deve ser compilado com o parâmetro `-lm`.

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

@Davi Silva Santos Sim, mas acho que o desafio é fazer sem usar a biblioteca math.h .

 

@Jessé P. de Melo O método de fatoração limita ao conjunto de números primos usados para verificar, e vai fazer sua função parar de funcionar conforme o número cresce.

 

A propriedade de quadrados perfeitos que uso para fazer uma função simples que funciona para qualquer número, é a de que todo quadrado perfeito é uma soma de números ímpares sequenciais, começando em 1.

 

Veja:

 

12 = 1 = 1

22 = 1 + 3 = 4

32 = 1 + 3 + 5 = 9

42 = 1 + 3 + 5 + 7 = 16

52 = 1 + 3 + 5 + 7 + 9 = 25

 

Tente fazer essa função usando essa propriedade.

 

(A função não é muito eficiente, pois demora mais tempo calculando quanto maior for o número, mas funciona para qualquer número. Existem outros métodos mais eficientes, mas são mais complexos, e não é necessário para o que o exercício pede.)

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

@isrnick Esse método parece bom. Eu pensei que ao fazer a verificação com números 2,3,5,7 seria o suficiente por que todos os que vem apos desses na fatoração poderiam ser divididos entre esses principais, se der você poderia ser mais claro ? porque fiz testes com o numero 81, depois (81*81)=6561 e depois com (6561*6561)=43046721 deram certo, no entanto o 43046720 ficou travado consumindo processador.

 

Mas vejo isso só amanha, estou desde as 12:00 estudando.

Compartilhar este post


Link para o post
Compartilhar em outros sites

@Jessé P. de Melo Quaisquer números que contenham números primos que não sejam 2, 3, 5 e 7 como divisores falhariam no seu programa.

 

Quadrados perfeitos de outros números primos são os mais fáceis de verificar, teste 121 por exemplo, que é 112. Seu programa vai ficar num loop infinito.

 

O mesmo ocorre com 26 = 2 * 13.

  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Desculpe a demora. Disse que começaria estudar as 12:00 mas comecei depois da 13:00, alem do mais por algum motivo que eu não lembro qual eu queria desenvolver um bloco só para números compostos e números primos. Enfim só aumentei isso na função para realizar cálculos para números primos:

int quadrado_perfeito(int x){
int soma_impares=1;
while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
    }
}

O código completo ficou:

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

int main(void){//2,3,5,7
    int num;
    int quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
int quadrado_perfeito(int x){
    int soma_impares=1;
    int exp_n2=0;
    int exp_n3=0;
    int exp_n5=0;
    int exp_n7=0;
    int teste1=0;
    int teste2=0;
    int teste3=0;
    int teste4=0;

    while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
        exit(0);
    }

    while(x>1){
        while (x%2==0){
            x=x/2;
            exp_n2++;
        }
        while (x%3==0){
            x=x/3;
            exp_n3++;
        }
        while (x%5==0){
            x=x/5;
            exp_n2++;
        }
        while (x%7==0){
            x=x/7;
            exp_n7++;
        }
    }
    if(exp_n2==0||exp_n2%2==0){
        teste1=1;
    }
    if(exp_n3==0||exp_n3%2==0){
        teste2=1;
    }
    if(exp_n5==0||exp_n5%2==0){
        teste3=1;
    }
    if(exp_n7==0||exp_n7%2==0){
        teste4=1;
    }

    if(teste1&&teste2&teste3&&teste4==1){
        printf("E' um quadrado perfeito");
    }
    else{
        printf("Nao e' um quadrado perfeito");
    }
}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Esse código não está somando os ímpares, está apenas obtendo números ímpares:

int quadrado_perfeito(int x){
int soma_impares=1;
while(soma_impares<x){
        soma_impares+=2;
    }
    if(soma_impares==x){
        printf("E' quadrado perfeito");
    }
}

O que resulta que seu código vai responder que qualquer número ímpar é um quadrado perfeito.

 

E use "return 0;" no lugar de onde você colocou "exit(0);",  a função exit() serve para finalizar o programa imediatamente, enquanto return retorna a execução do programa para o escopo que chamou esta função.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Depois de muita luta terminei.

Estava quase desistindo do exercício, fiquei gastando tempo e paciência tentando readequar meu código a solução proposta.

21 horas atrás, isrnick disse:

A propriedade de quadrados perfeitos que uso para fazer uma função simples que funciona para qualquer número, é a de que todo quadrado perfeito é uma soma de números ímpares sequenciais, começando em 1.

 

Veja:

 

12 = 1 = 1

22 = 1 + 3 = 4

32 = 1 + 3 + 5 = 9

42 = 1 + 3 + 5 + 7 = 16

52 = 1 + 3 + 5 + 7 + 9 = 25

Sendo que era muito mais simples começar a função do zero. Aparentemente esta funcionando e ficou assim:

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

int main(void){//2,3,5,7
    int num;
    void quadrado_perfeito(int x);

    printf("Digite um numero para saber se e um quadrado perfeito: ");
    scanf("%i",&num);
    quadrado_perfeito(num);
}
void quadrado_perfeito(int x){
    int n1=1;
    int n_total=1;
    int valida=0;

    while(n1<x){
        n1+=2;
        n_total=n_total+n1;
        if (n_total==x){
            valida=1;
        }
    }
    if (valida==1){
        printf("E' quadrado perfeito");
    }
    else{
        printf("Nao e' quadrado perfeito");
    }
}

 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

A lógica está correta, agora só está errando em 2 casos, 0 e 1 são quadrados perfeitos, mas seu programa responde que não são, o motivo é que que seu programa começa testando a partir do número 4.

 

Vou fazer algumas mudanças na sua função e comentar o que fiz:

 

void quadrado_perfeito(int x){
    int n1=1;
    int n_total=1;
    //Não precisaremos dessa variável de validação
    //int valida=0;
    
    //Queremos comparar o total com x, não os número ímpares:
    //while(n1<x){
    while(n_total < x){
        n1+=2;
        n_total=n_total+n1;
        
        //Não é necessário checar dentro do while e usar
        //uma variável para verificar, pois podemos comparar
        //n_total com x após o ciclo, e já imprimir a mensagem
        //if (n_total==x){
        //    valida=1;
        //}
    }
    
    //Retirei este if:
    //if (valida==1){
    //Pois podemos comparar n_total com x aqui diretamente,
    //e já adicionei para também checar o caso específico do 0
    //assim todas as possibilidades estão cobertas:
    if (x == n_total || x == 0){ 
        printf("E' quadrado perfeito");
    }
    else{
        printf("Nao e' quadrado perfeito");
    }
}

 

Lembre-se também de colocar o return 0; na última linha do main(), pois o main() uma função do tipo int, logo espera-se que retorne um valor inteiro e finalizar a função (quando o main() retorna 0 está indicando para sistema operacional que o programa foi concluído corretamente, e retorna algo diferente de 0 se ocorrer um erro durante a execução).

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×