C algoritmo: Escolher quais números somar para chegar ao resultado desejado

[ZecaUrubu]

Olá pessoal, estou com um trabalho cabuloso em C que esta quebrando minha cabeça, pois segundo o professor tem que usar RECURSIVIDADE e não tenho facilidade com essa bagaça.

 

O complicado está sendo encontrar a lógica, se alguém tiver uma luz, somente pra dar um norte de onde seguir, já está ótimo.

 

Aqui vai o problema:

 

• O programa devera ler da entrada padrão do sistema da seguinte forma.

 

     (Exemplo de ENTRADA):

      15 --------------------- Primeiro input: Soma desejada.

       5 ---------------------- Segundo input: Quantidade de números a serem somados.

       8 5 6 2 10 ---------- Terceiro input:  Números a serem somados (Perceba que é a quantidade exata do segundo input).

 

• O programa deverá identificar quais números do terceiro input somados chegam ao resultado do primeiro input.

• Na saída o programa deverá imprimir um valor 1 ou 0 para cada item [i] (terceiro input), representando se ele foi usado(1) ou não(0).

 

     (SAÍDA do exemplo acima):

       0 1 0 0 1 ------------ No caso, representa que foi usado o número 5 e 10, de acordo com a posição dele no terceiro input

 

OBS: Todas as entradas (primeiro, segundo e terceiro input) serão lidas por scanf, e não diretamente colocadas no código, pois tem alguns casos testes que o programa deve passar para ser considerado aceito!

 

Alguns casos teste:

 

Entrada:                          Saída: 0 1 0 1 1 

8
4
3 4 1 2  2

 

Entrada:                          Saída: 1 0 1 1 0 

24
5
8 6 7 9 5 

[devair1010]

@ZecaUrubu  esse exercicio parece ser do Uri  online judge ,  poste o link dele ,  e creio que usando um vetor para armazenar esse terceiro input ajudaria , pois voce poderah usar dois loop para percorrer o vetor e  somar cada numero com os outros e comparar com o primeiro input .

[ZecaUrubu]

2 minutos atrás, devair1010 disse:

@ZecaUrubu  esse exercicio parece ser do Uri  online judge ,  poste o link dele ,  e creio que usando um vetor para armazenar esse terceiro input ajudaria , pois voce poderah usar dois loop para percorrer o vetor e  somar cada numero com os outros e comparar com o primeiro input .

Não sei dizer se foi tirado do UriOnline (parece estar fora do ar), o professor enviou.

 

Eu pensei em usar um vetor para armazenar, mas como vou o primeiro numero do vetor com todos os outros, e depois o segundo e terceiro? e além disso, pode ser mais de 2 números somados, exemplo:

Desejado: 10

Pode ser: 3 6 1

[arfneto]

8 horas atrás, ZecaUrubu disse:

OBS: Todas as entradas (primeiro, segundo e terceiro input) serão lidas por scanf, e não diretamente colocadas no código, pois tem alguns casos testes que o programa deve passar para ser considerado aceito

 

Que isso tem a ver com scanf()? quer dizer que só pode ler com essa função?

 

Entenda que você pode e deve começar a testar com constantes colocadas diretamente no código, como as do seu enunciado. Só coloque a leitura depois de passar por todos os testes. 

 

Ao usar scanf() não leia do teclado. Use fgets ou fscanf() e leia de um arquivo . É muito mais fácil. E de todo modo stdin é um arquivo.

 

Esse problema é o mesmo descrito aqui: 

 

Talvez ajude você se ler o que eu expliquei lá.

 

8 horas atrás, ZecaUrubu disse:

Olá pessoal, estou com um trabalho cabuloso em C que esta quebrando minha cabeça, pois segundo o professor tem que usar RECURSIVIDADE e não tenho facilidade com essa bagaça.

 

O complicado está sendo encontrar a lógica, se alguém tiver uma luz, somente pra dar um norte de onde seguir, já está ótimo

 

Sobre a "lógica"

 

Esse não é um problema recursivo. Não há uma razão para usar recursão aqui, é um simples loop. Mas dá para usar, já que é um loop e qualquer loop pode ser considerado recursivo.

 

Não precisa misturar as coisas. Pode resolver o problema primeiro e depois aplicar a recursão.

 

A ideia da recursão aqui é simples, é como o sorteio da loteria:

• Você tem dois valores, um alvo e uns pesos. Na Caixa Econômica teria as bolinhas
• Ao usar um peso você fica com um saldo menor de peso e um peso a menos. Na loteria a bolinha sorteada fica na canaleta para não sair de novo
• Se passou do peso você desiste dessa combinação de pesos
• Se usou todos os pesos possíveis e não deu desiste dessa combinação
• Se ainda falta peso você chama a mesma função de novo mas sem o peso que usou e descontando o que já pesou, o simples

Se tem pesos de 2 4 6 e 8 kilos e quer pesar 7 kilos por exemplo:

• Se tentar com o 8Kg já passou e desiste
• Se tentar com o 6Kg vai ficar com 2 para pesar e 3 pesos: 2 4 e 6 kilos. Isso é a recursão. Só isso.
• Se tentar com 4 kg vai ficar com 3kg para pesar e 3 pesos. Nova recursão.

 

Como você tem N pesos é trivial saber ate onde pode pesar: é só usar todos. Se tem 2 pesos pode ter 3 valores. Se tem 3 pesos pode ter 7 valores. Se tem x pesos já deu para ver que pode pesar 2^x -1. São os bits, os valores que vai mostrar na saída. 

 

Se tem 256 pesos vai poder pesar 255 combinações, como em um char.