I cannot prepare the calculation to solve the problem proposed by the enunciation

Question

I cannot prepare the calculation to solve the problem proposed by the enunciation

Asked 6 years, 11 months ago

Viewed 249 times

-8

I need to develop a program in C language, but I am beginner. :(

Follows the statement:

That is the context of the programme:

A smart cat walked into a messy room that needed cleaning. Instead of doing the job alone, he decides to transfer the work to his sidekick cats. The smart cat has a number of helper cats (smaller than him) inside his hat. Each helper cat also has its own helper cats (smaller than them) inside their hats. Thus, each helper cat transfers the work to be done to its own helpers. Eventually the helper cats reach a minimum size of 1. These cats of minimum size have no helpers in their hats: they are workers who must do the work themselves. Given the size of the first smart cat and the number of working cats (size 1), you should find the number of cats that do not perform any work (i.e., lazy cats larger than 1) and also determine the sum of the sizes of all cats.

Objective of the programme:

Make a program that reads from the keyboard two positive integers, T and Q. The first integer, T, indicates the size of the first smart cat and the second integer, Q, indicates the amount of working cats.

For each pair of numbers your program must produce the following output:
Quantidade de gatos que nao trabalham: 999
Tamanho total dos gatos: 999
Where 999 represents the values calculated by the program, according to the description of the problem, for the numbers read T and Q.

After printing the calculated values, your program must print a blank line and restart the procedure, ending only when 0 (zero) is entered for the T number. At the end of the processing your program should print the message "End of program".

Assumptions and restrictions

1) Before reading the T number, your program should print, on the same line, the message "Smart cat size: ", re-reading the T number (printing the orientation message again), if the entered value is negative.

2) Before reading the Q number, your program should print, on the same line, the message "Number of working cats: ", re-reading the Q number (printing the orientation message again), if the entered value is negative or zero.

3) For each pair of T and Q numbers the following rules apply: The number of cats inside each hat (of the cats that have helpers) is constant and equal to N. The size of cats inside a hat is 1/(N + 1) times the size of the cat that has the hat they are in. (For example, if N is equal to 3, the size of cats in a cat’s hat of size 16 is 4).

4) The numbers T and Q will always reflect a valid situation. That is, starting from a cat of size T, considering the cats in his hat and the cats in the hats of each helper, eventually one arrives at a quantity Q of working cats (size 1).

Example A)
The following output illustrates a valid execution of the program:
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

Here’s the code I already have:

#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;
}

Doubt: I can’t imagine what would be the calculation to be performed to execute the output of the program example.

6

Danilo, I didn’t deny it, but let me explain, the goal here is not to do everything, in case your biggest problem is the initial calculation (at least that’s what I understood), if you edit the question and give a focus on the isolated problem the question could be saved, of course it’s just my opinion and I don’t know if the other members of the site will agree.

– Guilherme Nascimento

2017/10/13 at 14:37
2

I agree as @Guilhermenascimento you can post the full code but the question must understand an isolated part of it, and when it was solved yet another question would be to open a new question.

– WMomesso

2017/10/13 at 16:49
1

This question seems valid to me. Could someone explain to me what is so wrong with it?

– Victor Stafusa

2017/10/13 at 17:32
@Victorstafusa I did not find clear the question, and it is very difficult to isolate the problem of it and lack objectivity in relation to the calculation, at least for me this. So I voted as unclear, because I believe that there is no need to negative it, just a close and wait for the AP to make the question clearer.

– gato

2017/10/13 at 17:37
@The cat problem is from the Q and the T reach the N and then the number of cats that do not work and the total size of cats. And turn that formula into an algorithm.

– Victor Stafusa

2017/10/13 at 17:41
@Victorstafuses an issue by removing what is irrelevant in the question and addressing this formula and how to apply it in an algorithm would make it an optimal question.

– gato

2017/10/13 at 17:44
2

@The problem is that this looks like college exercise, so anything that was removed could compromise the program’s understanding, and there’s a lot of teachers out there who go through very difficult exercises to decipher. In this case, I do not believe that it is the author’s fault.

– Victor Stafusa

2017/10/13 at 17:57
@Victorstafusa think that giving a focus on the formulae on the part of the algorithm corresponding to it would help a lot, even keeping the text that this profuse just not to change the meaning of the question, at least separates the problem.

– gato

2017/10/13 at 18:04
1

+1 for all irony related to the lazy cats in the hat.

– Lacobus

2017/10/13 at 18:11
@Lacobus is very "hate" against cats ;P

– gato

2017/10/13 at 18:30
2

@Vitorstafusa you’re right, it’s college issue. I did not understand the reasoning of the teacher and I can not imagine a formula to arrive at the results of the example that has in the description of the problem ://

– Danilo Antônio

2017/10/13 at 20:21
3

@Daniloantônio posted the answer. In fact, these formulas were something very difficult to get. Your teacher must be crazy.

– Victor Stafusa

2017/10/13 at 20:37
2

@Daniloantônio @gato @Victorstafusa: This problem is called The Cat in the Hat and was originally proposed by a website called Uva Online Judge. I found in the github a code in C++ that maybe solve the problem.

– Lacobus

2017/10/14 at 00:39

Show 8 more comments

1 answer

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.

by Victor Stafusa • **63,338** points · Answer 1 · 2017-10-13T20:26:41+00:00

First, define this function to simplify your code:

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

And then you can use it that way:

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

You may be wondering why long long. It turns out that long long is a 64-bit integer for storing very large numbers. And if you look down at the math, you’ll see that you’re dealing with really big numbers.

We know that the cats that work are size 1. Let’s try based on this to reach the size of other cats:

The size of cats inside a hat is 1/(N + 1) times the size of the cat that has the hat they are in.

That is, if $G_k$ is the size of the cat inside the hat and $G_{k+1}$ is the size of the cat that has the hat, so:

$G_k=G_{k+1}/(N+1)$

Knowing that working cats are size 1, so:

$G_0=1$

And therefore:

$G_0=G_1/(N+1)$
$1=G_1/(N+1)$
$G_1=N+1$

$G_1=G_2/(N+1)$
$N+1=G_2/(N+1)$
$G_2=(N+1)^2$

$G_2=G_3/(N+1)$
$(N+1)^2=G_3/(N+1)$
$G_3=(N+1)^3$

By induction we have to:

$G_k=(N+1)^k$

Your problem is finding the values of $N$ and $k$ , where $k$ would be the smart cat level.

Let’s try the first case:

$G_k=(N+1)^k$

Replacing $G_k$ for $T$ :

$216=(N+1)^k$

Fatorando the $T$ :

$2^3\times3^3=(N+1)^k$
$6^3=(N+1)^k$
$k=3$
$N=5$

Number of working cats: $Q=N^k=5^3=125$

To calculate the number of cats that don’t work, if we have 125 working cats and N is 5, then those are in the hat of 25 cats that are in the hat of 5 cats that are in the hat of the smart cat. Soon:

$z=25+5+1=31$

Let’s try to generalize the formula:

$z=N^2+N^1+N^0$
$z=\sum_{i=0}^{k-1}N^i$

Total size of cats:

$f=125\times 1+25\times 6+5\times 36+216=125+150+180+216=671$

Generalizing:

$f=\sum_{i=0}^{k}N^{k-i}\times(N+1)^i$

Now let’s look at the second case:

$G_k=(N+1)^k$
$5764801=(N+1)^k$
$7^8=(N+1)^k$
$k=8$
$N=6$
$Q=6^8=1679616$
$z=\sum_{i=0}^{k-1}N^i$
$z=\sum_{i=0}^{7}6^i$
$z=6^0+6^1+6^2+6^3+6^4+6^5+6^6+6^7$
$z=1+6+36+216+1296+7776+46656+279936$
$z=335923$
$f=\sum_{i=0}^{k}N^{k-i}\times(N+1)^i$
$f=\sum_{i=0}^{8}6^{8-i}\times 7^i$
$f=6^8\times 7^0+6^7\times 7^1+6^6\times 7^2+6^5\times 7^3+6^4\times 7^4+6^3\times 7^5+6^2\times 7^6+6^1\times 7^7+6^0\times 7^8$
$f=1679616\times 1+279936\times 7+46656\times 49+7776\times 343+1296\times 2401+216\times 16807+36\times 117649+6\times 823543+1\times 5764801$
$f=1679616+1959552+2286144+2667168+3111696+3630312+4235364+4941258+5764801$
$f=30275911$

Well, now that we know the mathematical theory, how can it be implemented?

You will need a function to calculate power. For example:

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;
}

Calculating these summations can also be a little tricky, but you can do something like this:

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;
}

Having these functions, the problem is reduced to finding the $k$ and the $N$ . You know that $T$ and $Q$ are powers and the $k$ is the exponent of the two, so you should look for the roots and finding, you have the $N$ .

However, there may be several whole roots. To know which one you want, you use the one that works with both. Do something more or less like this:

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;
}

If that function gives k and n the values of -1, so there is no solution to the problem and you should abort (use a if for this). If not, proceed with the calculations of gatos_que_nao_trabalham and tamanho_total_dos_gatos.