[Sequencial] Distribuição

[scifie]

Olá pessoal,

alguém poderia me indicar o que estudar para resolver um problema - particularmente chamo de distribuição - que manualmente é de fácil resolução mas não sei como fazê-lo matematicamente.

Eis o problema:

Tendo X bolinha, distribuir as bolinhas em N caixas de forma sequencial, tal que os valores presentes nas caixas fiquem uniformemente e sequencialmente distribuídos.

Um exemplo p/ descrever melhor o enunciado confuso:

Quantidade de bolinhas: 7 Quantidade de caixas: 4
Assim sendo, a caixas terão as seguintes qtde de bolinhas: [2][2][2][1]

Outro exemplo:

Quantidade de bolinhas: 13 Quantidade de caixas: 3
Assim sendo, a caixas terão as seguintes qtde de bolinhas: [5][4][4]

A idéia básica é ir colocando as bolinhas uma por uma nas caixas, qndo chegar na última caixa, volta p/ primeira e continua o processo até que as bolinhas acabem.


Alguém poderia me ajudar?

[LuizAquino]

Olá pessoal,

alguém poderia me indicar o que estudar para resolver um problema - particularmente chamo de distribuição - que manualmente é de fácil resolução mas não sei como fazê-lo matematicamente.

Eis o problema:

Tendo X bolinha, distribuir as bolinhas em N caixas de forma sequencial, tal que os valores presentes nas caixas fiquem uniformemente e sequencialmente distribuídos.

Um exemplo p/ descrever melhor o enunciado confuso:

Quantidade de bolinhas: 7 Quantidade de caixas: 4
Assim sendo, a caixas terão as seguintes qtde de bolinhas: [2][2][2][1]

Outro exemplo:

Quantidade de bolinhas: 13 Quantidade de caixas: 3
Assim sendo, a caixas terão as seguintes qtde de bolinhas: [5][4][4]

A idéia básica é ir colocando as bolinhas uma por uma nas caixas, qndo chegar na última caixa, volta p/ primeira e continua o processo até que as bolinhas acabem.

Alguém poderia me ajudar?

Basta aplicar o princípio de divisão.

Exemplo 1) Quantidade de bolinhas: 7. Quantidade de caixas: 4.

Dividindo 7 por 4 obtemos quociente 1 e resto 3. Ou seja, 7 = 4*1 + 3. Isso significa que primeiro vamos colocar 1 bolinha em cada uma das 4 caixas, mas sobrarão 3 bolinhas. Cada bolinha que sobrou colocaremos em uma das 3 primeiras caixas. Ficamos então com: [2][2][2][1].

Exemplo 2) Quantidade de bolinhas: 13. Quantidade de caixas: 3.

Dividindo 13 por 3 obtemos quociente 4 e resto 1. Ou seja, 13 = 3*4 + 1. Isso significa que primeiro vamos colocar 4 bolinhas em cada uma das 3 caixas, mas sobrará 1. A bolinha que sobrou colocaremos na primeira caixa. Ficamos então com: [5][4][4].

[scifie]

Valeu

Com isso é possível criar um algoritmo que distribua as bolinhas em apenas O(n) - sendo n a qtde de caixas. Claro que a aplicação para o meu caso não tem nada a ver com bolinhas, hehehe. A questão é determinar quantos espaços deverão ser acrescentados ao espaços já existentes em uma linha de texto de forma que a linha seja apresentada de forma justificada.

Sei que não é um fórum de programação, mas eis aqui o algoritmo utilizando para o problema das bolinhas:

Código: Selecionar todos

#include "stdafx.h"
#include <process.h>

int main(int argc, char* argv[])
{
    int bolinhas, caixas;

    printf("Informe a qtde de bolinhas e caixas!\n");
    int n = scanf("%d %d", &bolinhas, &caixas);
    if (n != 2)
        return 0;

    int qtdePorCaixa = bolinhas / caixas;
    int qtdeRestante = bolinhas - (caixas * qtdePorCaixa);
   
    for (int c = 0; c < caixas; c++)
        printf("Caixa %d contém %d bolinhas\n", c + 1, qtdePorCaixa + (c < qtdeRestante ? 1 : 0));

    system("pause");
    return 0;
}