-9

Preciso desenvolver um programinha em linguagem C, porém sou iniciante. :(

Segue o enunciado:

O contexto do programa é esse:

Um gato esperto entrou em uma sala bagunçada que precisava de limpeza. Em vez de fazer o trabalho sozinho, ele decide transferir o trabalho para os seus gatos ajudantes. O gato esperto possui uma quantidade de gatos ajudantes (menores que ele) dentro do seu chapéu. Cada gato ajudante também possui seus próprios gatos ajudantes (menores que eles) dentro dos seus chapéus. Assim, cada gato ajudante transfere o trabalho a ser feito para os seus próprios ajudantes. Eventualmente os gatos ajudantes atingem um tamanho mínimo igual a 1. Estes gatos de tamanho mínimo não possuem ajudantes em seus chapéus: são trabalhadores que devem fazer o trabalho eles mesmos. Dados o tamanho do primeiro gato esperto e a quantidade de gatos trabalhadores (de tamanho 1), você deve encontrar o número de gatos que não realizam trabalho algum (isto é, os gatos preguiçosos de tamanho maior que 1) e também determinar a soma dos tamanhos de todos os gatos.

Objetivo do programa:

Faça um programa que leia do teclado dois números inteiros positivos, T e Q. O primeiro inteiro, T, indica o tamanho do primeiro gato esperto e o segundo inteiro, Q, indica a quantidade de gatos trabalhadores.

Para cada par de números seu programa deve produzir a seguinte saída:

Quantidade de gatos que nao trabalham: 999
Tamanho total dos gatos: 999

Onde 999 representa os valores calculados pelo programa, segundo a descrição do problema, para os números lidos T e Q.

Após a impressão dos valores calculados, seu programa deve imprimir uma linha em branco e reiniciar o procedimento, terminando apenas quando o 0 (zero) for digitado para o número T. Ao final do processamento seu programa deve imprimir a mensagem "Fim de programa".

Assunções e restrições

1) Antes da leitura do número T, seu programa deve imprimir, na mesma linha, a mensagem "Tamanho do gato esperto: ", voltando a ler o número T (imprimindo a mensagem de orientação novamente), caso o valor digitado seja negativo.

2) Antes da leitura do número Q, seu programa deve imprimir, na mesma linha, a mensagem "Quantidade de gatos trabalhadores: ", voltando a ler o número Q (imprimindo a mensagem de orientação novamente), caso o valor digitado seja negativo ou zero.

3) Para cada par de números T e Q valem as seguintes regras: A quantidade de gatos dentro de cada chapéu (dos gatos que possuem ajudantes) é constante e igual a N. O tamanho dos gatos dentro de um chapéu é 1/(N + 1) vezes o tamanho do gato que possui o chapéu no qual eles estão. (Por exemplo, se N é igual a 3, o tamanho dos gatos no chapéu de um gato de tamanho 16 é 4).

4) Os números T e Q sempre refletirão uma situação válida. Isto é, partindo-se de um gato de tamanho T, considerando os gatos em seu chapéu e os gatos nos chapéus de cada ajudante, eventualmente chega-se a uma quantidade Q de gatos trabalhadores (de tamanho 1).

Exemplo A)
A seguinte saída ilustra uma execução válida do programa:

Tamanho do gato esperto: -32
Tamanho do gato esperto: -961
Tamanho do gato esperto: 216
Quantidade de gatos trabalhadores: 125
Quantidade de gatos que nao trabalham: 31
Tamanho total dos gatos: 671

Tamanho do gato esperto: 5764801
Quantidade de gatos trabalhadores: 0
Quantidade de gatos trabalhadores: -2148
Quantidade de gatos trabalhadores: 1679616
Quantidade de gatos que nao trabalham: 335923
Tamanho total dos gatos: 30275911

Tamanho do gato esperto: 0
Fim de programa

Eis aqui o código que já tenho:

#include<stdio.h>

int main (void){

    int T, Q;

    do{
        do{
            printf("Tamanho do gato esperto: ");
            scanf("%d", &T);
        } while(T < 0);

        if(T != 0){
            do{
                printf("Quantidade de gatos trabalhadores: ");
                scanf("%d", &Q);
            } while(Q <= 0);

            if((T > 0) && (Q > 0)){

                /* não consigo imaginar o calculo para descobrir os valores 
                de saída do programa */

                printf("Quantidade de gatos que nao trabalham: \n");
                printf("Tamanho total dos gatos: \n\n");

            }
        }
    } while(T != 0);

    if(T == 0){
        printf("Fim de programa\n");
    }

    return 0;
}

Dúvida: Não consigo imaginar qual seria o cálculo a ser realizado para executar as saídas do exemplo do programa.

13
  • 6
    Danilo, eu não negativei, mas deixa te explicar, o objetivo aqui não é fazer tudo, no caso o seu maior problema é o calculo inicial (ao menos foi o que eu entendi), se você editar a pergunta e der um foco no problema isolado a pergunta poderia ser salva, claro que é apenas opinião minha e não sei se os outros membros do site irão concordar.
    – Syzoth
    13/10/2017 às 14:37
  • 2
    Concordo como @GuilhermeNascimento você pode postar o código completo mas a pergunta deve compreender um parte isolada do mesmo, e quando resolvesse ainda ficasse outra questão seria abrir uma nova pergunta.
    – WMomesso
    13/10/2017 às 16:49
  • 2
    @gato O problema é que isso tem cara de exercício de faculdade, então qualquer coisa que fosse removida poderia comprometer a compreensão do programa, e tem muito professor por aí que passa exercícios bem difíceis de se decifrar. Neste caso, não acredito que a culpa seja do autor da pergunta. 13/10/2017 às 17:57
  • 2
    @VitorStafusa você tem razão, é problema de faculdade. Eu não compreendi o raciocínio do professor e não consigo imaginar uma fórmula para chegar aos resultados do exemplo que tem na descrição do problema :// 13/10/2017 às 20:21
  • 3
    @DaniloAntônio Postei a resposta. De fato, essas fórmulas foram algo bem difícil de se obter. O seu professor deve ser um maluco. 13/10/2017 às 20:37

1 Resposta 1

7

Primeiro, defina essa função para simplificar o seu código:

long long ler_numero(const char *mensagem) {
    long long n = -1;
    do {
        printf("%s: ", mensagem);
        scanf("%lld", &n);
    } while (n < 0);
    return n;
}

E então você pode usar dessa forma:

long long t = ler_numero("Tamanho do gato esperto");
long long q = ler_numero("Quantidade de gatos trabalhadores");

Você pode estar se perguntando o porquê de long long. Ocorre que long long é um inteiro de 64 bits para armazenar números bem grandes. E se você olhar a matemática mais abaixo, você vai ver que está lidando com números bem grandes.

Nós sabemos que os gatos que trabalham têm tamanho 1. Vamos tentar com base nisso chegar ao tamanho dos demais gatos:

O tamanho dos gatos dentro de um chapéu é 1/(N + 1) vezes o tamanho do gato que possui o chapéu no qual eles estão.

Ou seja, se Gk é o tamanho do gato que está dentro do chapéu e Gk+1 é o tamanho do gato que tem o chapéu, então:

Gnrec

Sabendo-se que os gatos trabalhadores têm tamanho 1, então:

G0=1

E portanto:

G1=xxx1
G1=xxx2
G1=xxx3

G2=xxx1
G2=xxx2
G2=xxx3

G3=xxx1
G3=xxx2
G3=xxx3

Por indução temos que:

Gk=xxx

O seu problema é achar os valores de N e k, onde k seria o nível do gato esperto.

Vamos tentar o primeiro caso:

Gk=xxx

Substituindo Gk por T:

Gk=216a

Fatorando o T:

Gk=216b
Gk=216c
Gk=216d
Gk=216e

Número de gatos trabalhadores: N^k

Para calcular o número de gatos que não trabalham, se temos 125 gatos trabalhadores e N é 5, então esses estão no chapéu de 25 gatos que estão no chapéu de 5 gatos que estão no chapéu do gato esperto. Logo:

25+5+1

Vamos tentar generalizar a fórmula:

N^2+N^1+N^0
z

Tamanho total dos gatos:

total1

Generalizando:

totalx

Agora vamos ver o segundo caso:

Gk=xxx
Gk=5764801a
Gk=5764801b
Gk=5764801d
Gk=5764801e
Gk=5764801f
z2a
z2b
z2c
z2d
z2e
total2a
total2b
total2c
total2d
total2e
total2f

Bem, agora que já sabemos a teoria matemática, como isso pode ser implementado?

Você vai precisar de uma função para calcular potências. Por exemplo:

long long potencia(long long base, long long expoente) {
    long long resposta = 1;
    // Use um for aqui para multiplicar base por base repetidas vezes.
    return resposta;
}

Calcular esses somatórios também pode ser um pouco complicado, mas dá para fazer com algo assim:

long long gatos_que_nao_trabalham(long long k, long long i) {
    long long resposta = 0;
    // Use um for para fazer cada etapa do somatório. Veja a fórmula do z.
    return resposta;
}

long long tamanho_total_dos_gatos(long long k, long long i) {
    long long resposta = 0;
    // Use um for para fazer cada etapa do somatório. Veja a fórmula do f.
    // Lembre-se que em cada passo você tem que calcular tanto o N^(k-i) quanto o (N+1)^i.
    return resposta;
}

Tendo essas funções, o problema se reduz a achar o k e o N. Você sabe que T e Q são potências e o k é o expoente das duas, então deve buscar pelas raízes e achando, você tem o N.

Entretanto, poderão existir várias raízes inteiras. Para saber qual é a que você quer, você usa aquela que dá certo com os dois. Faça algo mais ou menos assim:

long long raiz(long long a, long long b) {
    // Faça uma busca binária no intervalo de 2 até a
    // procurando por um número x tal que potencia(x, b) == a.
    // Se achar, retorne x.
    // Se não achar, retorne -1.
}

void acha_k_e_n(long long q, long long t, long long *k, long long *n) {
    for (*k = 0; *k < 64; *k++) {
        *n = raiz(t, *k) - 1;
        if (*n > 0 && potencia(*n, *k) == q) return;
    }
    *k = -1;
    *n = -1;
}

Se essa função der para k e n os valores de -1, então não há solução para o problema e você deve abortar (use um if para isso). Se não, prossiga com os cálculos de gatos_que_nao_trabalham e tamanho_total_dos_gatos.

8

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 .