Jump to content
Fórum Script Brasil
  • 0

Repetição


Question

Madame Rachel possui uma mansão onde ela recebe todos os seus descendentes (netos e bisnetos) durante as férias. Sua mansão possui exatamente N quartos (cada quarto é numerado de 1 a N), onde N é também a quantidade de netos e bisnetos (cada descendente é também numerado de 1 a N). Como toda criança, os descendentes de Madame Rachel são bastante travessos. Todo dia sempre fazem a mesma brincadeira: eles acordam de manhã cedo antes dela e se encontram no grande jardim. Cada descendente, um de cada vez, entra na mansão e troca o estado das portas dos quartos cujos números são múltiplos do seu identificador. Trocar o estado de uma porta significa fechar uma porta que estava aberta ou abrir uma porta que estava fechada. Por exemplo, o descendente cujo identificador é igual a 15 vai trocar o estado das portas 15, 30, 45, etc. Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão em uma ordem completamente aleatória, quais portas estarão abertas após a entrada de todos os descendentes na mansão?

Entrada vai ser o numero de quartos (e tmb descendentes)
Saida vai ser todas as portas que estarão abertas 

EX: 

1 4

Como faço isso? Eu não postei o código por que eu não consegui entender isso direito, digo como montar essa estrutura de repetição.

Link to post
Share on other sites

1 answer to this question

Recommended Posts

  • 0

Como todo descendente alterará o estado de todas as portas nais quais são múltiplas de seu identificador, as portas terão seus estado alterado div vezes, onde div é o número de divisores da porta. De fato, a porta 8 por exemplo, terá seu estado alterado 4 vezes, pelos descendentes 1, 2, 4 e 8 (divisores de 8). Desta forma, basta calcular a quantidade de divisores da porta para saber quantas vezes teve seu estado alterado e descobrir seu estado atual, visto que é dado o estado inicial (fechada). Repare que após uma quantidade par de mudança de estado, a porta sempre voltará a ficar fechada e, quando ímpar, esta estará aberta. Vamos ao código:

//Programa: Portas Madame Rachel
//Função: Calcular quais portas ficarão abertas na mansão da Madame Rachel
//Autor: Hazzu#7444
//Data: 15/06/2020

//Cabeçalhos
#include <stdio.h>
#include <locale.h>


//Função principal
int main(){
    //Declaração de variáveis
    int q, i, n, div;
    
    setlocale(LC_ALL, "Portuguese");    //Configurando terminal para português
	
	//Apresentação
	printf("------ Portas Madame Rachel ------\n");
	printf("Olá, esse programa irá calcular quais portas ficarão abertas na mansão da Madame Rachel.\n");

	//Solicitando número
	printf("-Digite a quantidade de quartos:\n");
	scanf("%d", &n);
	
    //Avaliando estado final
	printf("Portas que ficarão abertas:\n");
	for (q=1; q<=n; q++){	//Percorrendo quartos
		div = 0;
		for (i=1; i<=q; i++){		//Calculando numero de alterações de estado (divisores)
			if (q % i == 0) div++;
		}
		if (div % 2 == 1) printf("%d\n", q);
	}
	
    //Encerrando programa
	printf("Obrigado por utilizar o programa!\n");
    return 0;
}

Um fato curioso que você pode notar ao inserir um alto valor para é que todos os números são quadrados perfeitos. Isto ocorre porque todos números naturais com uma quantidade ímpar de divisores são quadrados perfeitos. De fato, como é demonstrado aqui. Sabendo disto, podemos otimizar nosso algorítimo imprimindo apenas os quadrados perfeitos de 1 a n. Vamos ao código:
 

//Programa: Portas Madame Rachel
//Função: Calcular quais portas ficarão abertas na mansão da Madame Rachel
//Autor: Hazzu#7444
//Data: 20/06/2020

//Cabeçalhos
#include <stdio.h>
#include <locale.h>


//Função principal
int main(){
    //Declaração de variáveis
    int r, n;
    
    setlocale(LC_ALL, "Portuguese");    //Configurando terminal para português
	
	//Apresentação
	printf("------ Portas Madame Rachel ------\n");
	printf("Olá, esse programa irá calcular quais portas ficarão abertas na mansão da Madame Rachel.\n");

	//Solicitando número
	printf("-Digite a quantidade de quartos:\n");
	scanf("%d", &n);
	
    //Avaliando estado final
	printf("Portas que ficarão abertas:\n");
	for (r = 1; r*r <= n; r++){	//Percorrendo raízes
		printf("%d ", r*r);
	}
	
    //Encerrando programa
	printf("\n\nObrigado por utilizar o programa!");
    return 0;
}

Você pode comprovar a diferença gritante de eficiência ao informar o valor 999999999 para às duas versões.

Edited by Hazzu
Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Cloud Computing


  • Forum Statistics

    • Total Topics
      148868
    • Total Posts
      644896
×
×
  • Create New...