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

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

Por enquanto eu implementei só a main

Expandir

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.

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

ou pelo menos iniciar essa lógica

Expandir

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

Em 28/10/2021 às 19:34, arfneto disse:

Que faz esse código que "implementou"?

Expandir

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

Em 28/10/2021 às 19:34, 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

Expandir

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

Em 28/10/2021 às 20:44, Lima.c disse:

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

Expandir

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

Em 28/10/2021 às 20:44, Lima.c disse:

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

Expandir

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.

Em 28/10/2021 às 20:44, Lima.c disse:

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

Expandir

pode ter mais de uma combinacao que da o peso esperado

Em 28/10/2021 às 20:44, 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

Expandir

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

Em 28/10/2021 às 21:31, 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.

Expandir

A função calcula teria alguma recursividade?

arfneto · 29 de outubro de 2021

Em 29/10/2021 às 21:21, Lima.c disse:

A função calcula teria alguma recursividade?

Expandir

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

Em 31/10/2021 às 18:44, 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?

Expandir

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 21: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

Expandir

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

Em 31/10/2021 às 20:51, 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?

Expandir

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

Em 31/10/2021 às 21:10, 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

Expandir

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

Em 31/10/2021 às 21:22, arfneto disse:

Tem um limite para o total de pesos no enunciado?

Expandir

Não tem.

Em 31/10/2021 às 21:22, 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

Expandir

vou tentar fazer isso, obrigado!

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

arfneto · 1 de novembro de 2021

Em 31/10/2021 às 22:03, Lima.c disse:

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

Expandir

Que seria isso? Pode explicar de outro modo?

1 de novembro de 2021

Em 01/11/2021 às 03:10, arfneto disse:

Que seria isso? Pode explicar de outro modo?

Expandir

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

Em 02/11/2021 às 10:25, JorgeGus disse:

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

Expandir

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

Em 02/11/2021 às 13:25, Lima.c disse:

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

Expandir

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

Em 01/11/2021 às 22:34, 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

Expandir

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 17: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

Expandir

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