Adding the items in an array automatically [closed]

Question

Adding the items in an array automatically [closed]

Navigation

#1 by (2 votes)

-6

I have these values:

x = 5;

long[] b = new long[]{5,1,2,3};

I need to make a program that adds the items in the b array so that the result is always equal to 5 (x). You can repeat the items, type: [1,1,1,1,1] or [5] or [2,3] or [1,1,3] or [1,1,1,2] or [2,2,1] output would be 6, the answer should be the qde of possibilities. My question would be how to do this sum separately.

EDIT1

This is the original problem

You are working at the cash counter at a fun-fair, and you have different types of coins available to you in infinite quantities. The value of each coin is already given. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

For example, if you have types of coins, and the value of each type is given respectively, you can change the units in three ways:, and.

Complete the function getWays that takes the number of coin types and the value of each coin type the input, and return the number of ways to make change for units using any number of coins.

Input Format

The first line contains two space-separated integers describing the respective values of and, where:    is the number of units    is the number of coin types   The second line contains space-separated integers describing the respective values of each coin type: (the list of distinct coins available in infinite amounts).

Constraints

Each is guaranteed to be distinct.   Hints

Solve overlapping subproblems using Dynamic Programming (DP):   You can solve this problem recursively but will not pass all the tests without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times. * Consider the degenerate cases:   - How many ways can you make change for cents? - How many ways can you make change for cents if you have no coins? * If you're having trouble defining your solutions store, then think about it in terms of the base case. - The answer may be larger than a -bit integer.

Output Format

Print a long integer denoting the number of ways we can get from the infinite supply of types of coins.

Sample Input 0

4 3

1 2 3

Sample Output 0

4

Explanation 0

There are four ways to make change for using coins with values given by:

So, we print as our answer.

Sample Input 1

10 4

2 5 3 6

Sample Output 1

5

Explanation 1

There are five ways to make change for units using coins with values given by:

So, we print as our answer.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static long getWays(long n, long[] c){
        // Complete this function
    }

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int m = Convert.ToInt32(tokens_n[1]);
        string[] c_temp = Console.ReadLine().Split(' ');
        long[] c = Array.ConvertAll(c_temp,Int64.Parse);
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        long ways = getWays(n, c);
    }
}

c#

asked by anonymous 07.05.2018 / 21:37

1 answer

Evaluate game-of-the-old code [closed] Error in IMC code [closed]

score 2 · Answer 1

The algorithm that satisfies your request is trivial to implement. Here is an example I wrote:

// Essa função gera recursivamente toda a árvore de possibilidades para
// todos os trocos iguais ou menos que o objetivo.
static int GetWays(int objetivo, IEnumerable<int> moedas, int trocoParcial)
{
    // Se o troco parcial é o troco que procuramos, então este caminho
    // na árvore de possibilidades é uma resposta válida.
    if (trocoParcial == objetivo)
    {
        return 1;
    }

    // Se já não houver mais moedas ou se o troco parcial ultrapassar
    // o troco que procuramos, significa que esse caminho na árvore de
    // possibilidades não nos levou a uma resposta válida.
    if (!moedas.Any() || trocoParcial > objetivo)
    {
        return 0;
    }

    // Se não foi possível decidir se a resposta é ou não válida, temos
    // que recursivamente verificar as alternativas que seguem ambos os
    // galhos. Vamos somar todas as respostas válidas para todas as
    // possíveis alternativas que podemos tomar.:
    return GetWays(objetivo, moedas, trocoParcial + moedas.First()) + GetWays(objetivo, moedas.Skip(1), trocoParcial);
}

I've put a lot of comments throughout the code to help with understanding, though that's probably not necessary because it's a pretty simplistic algorithm. All it does is to recursively generate all possible changes, accumulating +1 if the change is valid (equal to the goal), or +0 otherwise.

Looking at the code you can quickly see that this function would generate a binary tree (the tree of possibilities). The tree is binary because each non-terminal node makes a choice of 2 possibilities:

Currency is used in exchange; or
Currency is not used in exchange

Now it's obvious the work done on each of the recursive calls and why there are exactly two calls.

However, as exposed in the English text that you pasted on the question, this implementation is extremely inefficient, as the entire tree of possibilities accumulates on the computer stack.

Analyzing the computational complexity of the above function will be left as an exercise you resolve, if you are interested (and I strongly recommend that you do).

The English text still gives an excellent tip on how to avoid stack accumulation. You should follow from there.

I gave you a functional solution. Now you just have to make it work.

I hope that my code code and my explanation can help you and other marketers.

Hugs and good luck!