1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Combinações em C

Discussão em 'Programação' iniciada por Simao, 8 de Dezembro de 2006. (Respostas: 3; Visualizações: 2244)

  1. Simao

    Simao Power Member

    Existe alguma função para calcular combinações em C?


    É que calcular à pata tem uma complexidade temporal brutal para números grandes

    Obrigado.
     
  2. Rui_Carlos

    Rui_Carlos 1st Folding then Sex

    mesmo que o C tenha uma função para calcular combinações, a complexidade não deve ser mais pequena do que numa função implementada por ti...
    e assim à primeira vista a complexidade é "apenas" linear no tamanho do número maior.

    mas se não precisares de valores exactos (até porque dada a dimensão dos números vais ter que usar float/double, logo nunca vais ter valores exactos) pode fazer as coisas de uma forma mais eficiente, usando esta função para calcular o factorial dos valores: http://en.wikipedia.org/wiki/Stirling's_formula
     
  3. Simao

    Simao Power Member

    A complexidade seria exponencial, visto que tinha q calcular 3 factoriais.
    A não ser que usasse programação dinamica.

    Obrigado pela ajuda, ja resolvi o meu problema.
     
  4. Rui_Carlos

    Rui_Carlos 1st Folding then Sex

    admitindo que o tempo que uma multiplicação demora a ser realizada é constante a complexidade era linear.

    o factorial de n seria um ciclo de n iterações, logo é linear no tamanho do número.
    ter que calcular 3 factoriais ou 1 (ou 10 ou 100 ou outro valor qualquer desde que seja fixo) não altera a complexidade do problema (O(3n)=O(n)=O(10000n)=...).
    e por acaso só preciavas de calcurar o factorial do maior número, os outros 2 podiam ser determinados no cálculo do maior.
     

Partilhar esta Página