C algoritmo do jogo da balança, como resolver?

28 de outubro de 2021

Os participantes precisam pegar alguns objetos e colocá-los na balança, e a balança precisa exibir com precisão os números exibidos pelo apresentador
Ex: o apresentador mostra o número 15 e 4 objetos, e seus respectivos pesos: 10kg, 4kg, 3kg, 5kg, o participante deve levar a balança os objetos que somado da exatamente o número mostrado pelo apresentador que nesse caso é 15
Nesse sentido, o programa deve ler um número NUM (número do apresentador), outro numero N (qtd. de objetos) e uma sequencia de pesos do objetos.
No final deve mostrar quais objetos deve ir a balança imprimindo uma sequencia de 0 e 1, o 1 indica que o objeto vai para balança e o 0 indica que não vai

Usando o exemplo acima, o programa vai se comportar da seguinte forma:

15 -> NUM escolhido pelo apresentador

4 -> qtd. objetos

10 4 3 5 -> sequencia de pesos

1 0 0 1 -> quais números vai para balança

Por enquanto eu implementei só a main, se alguém puder me ajudar a como resolver esse problema, ou pelo menos iniciar essa lógica eu agradeço!

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

int main (void){
    int M, n, i, j, aux;
    int* v;
    scanf ("%d", &M);
    scanf ("%d", &n);
    for (i=0;i<n;i++){
        scanf ("%d", &aux);
        v[i]=aux;
    }  
 
 
    return 0;
}

arfneto · 28 de outubro de 2021

1 hora atrás, Lima.c disse:

Por enquanto eu implementei só a main

Que faz esse código que "implementou"?

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

int main (void){
    int M, n, i, j, aux;
    int* v;
    scanf ("%d", &M);
    scanf ("%d", &n);
    for (i=0;i<n;i++){
        scanf ("%d", &aux);
        v[i]=aux;
    }   
    return 0;
}

v é int*, um ponteiro para int. Só isso. A linha v]i] = aux só vai cancelar seu programa, já que v não aponta para nada e assim v[i] também não.
TESTE o retorno de scanf(). SEMPRE. É ingênuo seguir adiante.
Se está lendo coisas considere avisar a quem está usando o programa sobre o que está lendo num dado momento
declare as variáveis de controle do loop DENTRO do loop
declare uma variável por linha e use nomes mais significativos.

1 hora atrás, Lima.c disse:

ou pelo menos iniciar essa lógica

Não escreva um programa interativo. Nunca. Só vai perder tempo. Já tem um exemplo dos pesos então comece pelo que já sabe.

A saída é o que se chama em geral um bitmap, 0 e 1 indicando se um certo peso vai ser usado ou não.

Claro que pode usar algo mais simples, como uma lista dos pesos.

Depois que funcionar você coloca a leitura em minutos. É muito chato a cada teste ficar digitando pesos...

Escreva em torno dos dados.

Sem pensar muito:

    int pesos[5] = { 1,2,3,5,10 };
    int usados[5] = 0;

Tem 5 pesos nesses valores. Pode ir alterando. Para testar pode fazer o óbvio: os pesos somam 21Kg certo?

Então usa um loop de 1 a 21 Kg e veja se seu programa funciona para esses

#include<stdio.h>
  
int calcula(int*,int*,int);

int main(void)
{

  int peso[5] = { 1,2,3,5,10 };
  int N = sizeof(peso) / sizeof(peso[0]); // quantos
  int usado[5] = {0};

  for( int p=1; p<=21; p+=1 )
  {
    printf("Alvo: %2dKg: ", p);
    for( int i=0; i<N; i+=1) printf("%d ", usado[i]);
    printf("\n");
  }
  return 0;
}

int calcula(int* pesos, int* usados, int alvo){ return 0;};

Por exemplo, que mostra

Alvo: 1Kg: 0 0 0 0 0 
Alvo: 2Kg: 0 0 0 0 0 
...
Alvo: 20Kg: 0 0 0 0 0 
Alvo: 21Kg: 0 0 0 0 0

Note que nem sempre pode dar pra pesar um certo valor...

28 de outubro de 2021

50 minutos atrás, arfneto disse:

Que faz esse código que "implementou"?

Primeiro ele lê o número que seria definido pelo apresentador do programa
Depois ele lê a quantidade de objetos que o jogo vai ter
e lê a sequencia de pesos de cada objeto e armazena em uma array

52 minutos atrás, arfneto disse:

Alvo: 1Kg: 0 0 0 0 0 
Alvo: 2Kg: 0 0 0 0 0 
...
Alvo: 20Kg: 0 0 0 0 0 
Alvo: 21Kg: 0 0 0 0 0

Não entendi essa parte muito bem, de ter um loop para cada kg

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

int main (void){
    int NUM; //Número escolhido pelo apresentador
    int n; // quantidade de objetos
    int* v; // sequencia de pesos n (cada objeto tem um peso)
    scanf ("%d", &NUM);
    scanf ("%d", &n);
    for (int i=0;i<n;i++){
        scanf ("%d", &v[i]);
    }  
 
    return 0;
}

Se NUM for 20
n for 5
a sequencia de peso for 5 6 2 3 10
quais desses números somando da 20? o 5, 2, 3 e 10 correto?
deverá ser impresso uma sequencia de 0 e 1, onde o 1 vai pra balança e o 0 não vai
então 5 6 2 3 10
- 1 0 1 1 1 → essa sequencia representa quais pesos vai para balança, que no caso é o 5, 2, 3 e 10

OBS: não estou colocando mensagens direcionando o usuário, pois foi pedido dessa forma.

arfneto · 28 de outubro de 2021

37 minutos atrás, Lima.c disse:

OBS: não estou colocando mensagens direcionando o usuário, pois foi pedido dessa forma

Não faz sentido. De todo modo como eu disse não há razão para ter um programa interativo se está testando.

37 minutos atrás, Lima.c disse:

Não entendi essa parte muito bem, de ter um loop para cada kg

São todos os pesos possíveis até o máximo que pode medir. Assim testa seu programa para todas as combinações e não precisa ler nada. Apenas chama a função que calcula e vê de dá pra pesar tais quilos com os pesos que tem.

Entendeu o que eu expliquei? Seu programa só vai cancelar.

40 minutos atrás, Lima.c disse:

quais desses números somando da 20? o 5, 2, 3 e 10 correto?

pode ter mais de uma combinacao que da o peso esperado

40 minutos atrás, Lima.c disse:

1 0 1 1 1 → essa sequencia representa quais pesos vai para balança, que no caso é o 5, 2, 3 e 10

Pois é: isso é chamado bitmask. E esses valores vão te dar todos os pesos possíveis. É só isso. Imagine 3 pesos Pode ter

000

001

010

011

100

101

110

111

Certo? Oito chances para 3 pesos. Como no seu caso 0 não faz sentido porque o cara não ai pesar 0Kg.

Para 4 pesos 15 combinações, para 5 pesos 31, e a vida segue. para 10 pesos serão 2^10 -1 = 1023 combinações, cada um a levando a um óbvio peso. Esses são todos os valores que pode pesar, então é só procurar o valor que o "apresentador" pediu.

Como te expliquei pode usar um loop e testar todos e já saberá que seu programa funciona.

Note que pode ter pesos impossíveis dependendo da combinação de pesos e por isso deixei a função retornando um int. Pode usar para sinalizar um peso impossível.

29 de outubro de 2021

23 horas atrás, arfneto disse:

São todos os pesos possíveis até o máximo que pode medir. Assim testa seu programa para todas as combinações e não precisa ler nada. Apenas chama a função que calcula e vê de dá pra pesar tais quilos com os pesos que tem.

Entendeu o que eu expliquei? Seu programa só vai cancelar.

A função calcula teria alguma recursividade?

arfneto · 29 de outubro de 2021

1 hora atrás, Lima.c disse:

A função calcula teria alguma recursividade?

Não. Não vejo razão. É uma coisa linear: basta seguir os possíveis pesos

31 de outubro de 2021

@arfneto até agora fiz assim, mas tem alguma forma de automatizar essas somas, porque desse jeito só ta somando dois valores, se tiver que somar 4, 8 ou ate mais valores simultaneamente esse programa vai dar pau

#include<stdio.h>
  
int calcula(int*,int*,int);
void zera (int,int*);
int main(void)
{

  int peso[5] = { 3,2,7,4,2 }, x;
  int N = sizeof(peso) / sizeof(peso[0]); // quantos
  int usado[5] = {0};

  for( int p=1; p<=21; p+=1 )
  {
    x = calcula(peso, usado, p);
    printf("Alvo: %2dKg: ", p);
    for( int i=0; i<N; i+=1){ printf("%d ", usado[i]);}
    printf("\n");
    zera(N, usado);
  }
  return 0;
}

int calcula(int* pesos, int* usados, int alvo){ 
    
    for (int i=0; i<alvo;i++){
        for (int j=i+1;j<alvo;j++){
            if (pesos[i]+pesos[j]==alvo){
                usados[i]=1;
                usados[j]=1;

            }
            if (pesos[i]+pesos[j]-alvo==0){
                return 0;
            }
        }

    }
   
    
    return 0;
}
void zera (int N, int* usados){

    for (int i=0;i<N;i++){
        usados[i]=0;
    }
}

arfneto · 31 de outubro de 2021

Acho que está misturando os pesos com a combinação dos pesos. Escreva o programa em torno da combinação dos pesos. O valor de cada um não é importante.

Veja onde eu expliquei sobre 3 pesos acima. Nada diz sobre os pesos em si.

31 de outubro de 2021

@arfneto Como eu faço esse mascaramento de bits em C, nunca mexi com isso... Tem algum artigo para indicar ou algum código que contenha isso?

arfneto · 31 de outubro de 2021

2 horas atrás, Lima.c disse:

@arfneto Como eu faço esse mascaramento de bits em C, nunca mexi com isso... Tem algum artigo para indicar ou algum código que contenha isso?

não precisa de nada. Basta contar. leu o que expliquei no post em que deixei o exemplo para 3 pesos?

Entendeu o que eu disse que não pode confundir a configuração dos pesos com os pesos em si?

Em 28/10/2021 às 18:31, arfneto disse:

Para 4 pesos 15 combinações, para 5 pesos 31, e a vida segue. para 10 pesos serão 2^10 -1 = 1023 combinações, cada um a levando a um óbvio peso. Esses são todos os valores que pode pesar, então é só procurar o valor que o "apresentador" pediu

Para 8 pesos por exemplo, vai ter 2^8 - 1 = 255 possibilidades. Veja o exemplo que mostrei para 3 pesos...

É a simples potência de 2, menos 1 porque o 0 não faz muito sentido, já que não vai usar peso algum....

31 de outubro de 2021

14 minutos atrás, arfneto disse:

não precisa de nada. Basta contar. leu o que expliquei no post em que deixei o exemplo para 3 pesos?

Entendeu o que eu disse que não pode confundir a configuração dos pesos com os pesos em si?

Sim, eu entendi a formula, mas não estou conseguindo aplicar ela, tipo onde ela vai entrar? como eu vou conseguir descobrir a sequencia exata contendo varias e varias combinações. Estou perdido

arfneto · 31 de outubro de 2021

8 minutos atrás, Lima.c disse:

Sim, eu entendi a formula, mas não estou conseguindo aplicar ela, tipo onde ela vai entrar? como eu vou conseguir descobrir a sequencia exata contendo varias e varias combinações

A fórmula é basicamente contar de 1 em 1 de 1 até 2^n - 1 onde n é o número de pesos, e ver que peso deu. Como são poucos pesos e não tem nenhum outro critério --- algo como por exemplo no caso de ter mais de uma maneira de chegar ao mesmo peso escolher a combinação com menos pesos --- nem compensa classificar. Apenas calcule e salve em um vetor.

Tem um limite para o total de pesos no enunciado?

31 de outubro de 2021

43 minutos atrás, arfneto disse:

Tem um limite para o total de pesos no enunciado?

Não tem.

43 minutos atrás, arfneto disse:

A fórmula é basicamente contar de 1 em 1 de 1 até 2^n - 1 onde n é o número de pesos, e ver que peso deu. Como são poucos pesos e não tem nenhum outro critério

vou tentar fazer isso, obrigado!

mas como eu acho a sequencia exata de 0 e 1?

arfneto · 1 de novembro de 2021

5 horas atrás, Lima.c disse:

mas como eu acho a sequencia exata de 0 e 1?

Que seria isso? Pode explicar de outro modo?

1 de novembro de 2021

19 horas atrás, arfneto disse:

Que seria isso? Pode explicar de outro modo?

Na vdd, como eu vou somar a combinação que resulta exatamente no peso alvo? Tipo dentre todas as combinações, como eu vou saber qual é a do peso alvo

JorgeGus · 2 de novembro de 2021

@Lima.c Um exemplo simples para demonstrar a ideia.

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

int main() {
    int tam = 3; // (numero de pesos)
    int comb = 5; // (combinacao a ser testada - em binário: 101)

    int mask = pow(2, tam - 1);

    if (comb & mask)
        printf("%s\n", "1");
    else
        printf("%s\n", "0");

    mask /= 2;
    if (comb & mask)
        printf("%s\n", "1");
    else
        printf("%s\n", "0");

    mask /= 2;
    if (comb & mask)
        printf("%s\n", "1");
    else
        printf("%s\n", "0");

    return 0;
}

Esse exemplo exibe individualmente o valor de cada bit de um número que no caso pode representar uma combinação com 1 bit para cada peso.

Você pode colocar isso dentro de um for para percorrer cada combinação independentemente do número de elementos, somar os valores dos pesos correspondentes às posições onde o resultado não for 0 e ao final comparar com o peso total escolhido.

E o resto acho que você precisa resolver por conta própria.

2 de novembro de 2021

2 horas atrás, JorgeGus disse:

if (comb & mask)
        printf("%s\n", "1");
    else
        printf("%s\n", "0");

Como ta funcionando esse if? o operador AND são dois & comerciais, quando você coloca apenas um & o que acontece?

JorgeGus · 2 de novembro de 2021

3 horas atrás, Lima.c disse:

Como ta funcionando esse if? o operador AND são dois & comerciais, quando você coloca apenas um & o que acontece?

Esse é o bitwise "AND", é feita uma comparação entre os bits na mesma posição de cada valor e criado um novo número com o resultado da comparação bit a bit, no caso como apenas um bit de mask é 1, o número gerado só será diferente de 0, se o bit na mesma posição de comb for também 1. E na linguagem C, 0 é considerado falso, e outros valores veradeiros.

arfneto · 2 de novembro de 2021

19 horas atrás, Lima.c disse:

Na vdd, como eu vou somar a combinação que resulta exatamente no peso alvo? Tipo dentre todas as combinações, como eu vou saber qual é a do peso alvo

Você parece estar pensando mais nos pesos do que nas combinações, acho que já escrevi isso.

Estamos falando de um programa de computador, então pode seguir pelo outro caminho e calcular todas as combinações e ir colocando em um vetor, por exemplo.

Ou ir calculando conforme apresentado o valor e ir salvando num vetor de soluções conhecidas para não ter que somar de novo.

Em 28/10/2021 às 14:53, Lima.c disse:

Ex: o apresentador mostra o número 15 e 4 objetos, e seus respectivos pesos: 10kg, 4kg, 3kg, 5kg, o participante deve levar a balança os objetos que somado da exatamente o número mostrado pelo apresentador que nesse caso é 15

A questão da recursividade

usando seu exemplo, considere que tem 4 pesos para chegar ao alvo. Se usar o peso de 10Kg inicialmente, vai fazer exatamente a mesma coisa a seguir, só que com 3 pesos e 5Kg. A mesma coisa pode ser a mesma função, e isso é a tal recursão: ao usar um peso chama a função de novo descontando o óbvio: um peso a menos e o valor do peso usado descontado do alvo. Eram 15Kg e 4 pesos. Usou um peso de 10Kg então são 3 pesos para achar os 5Kg que faltam