Instantly share code, notes, and snippets.

# lscoder/SimpleCombination

Last active October 2, 2015 03:08
Show Gist options
• Save lscoder/2158654 to your computer and use it in GitHub Desktop.
Combinação simples (Triângulo de Pascal)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // Cálculo de combinação simples utilizando o triângulo de Pascal, onde: // // Relação de Stifel // // | n-1 | + | n-1 | = | n | // | k-1 | | k | | k | // // Ex.: Quantidade de jogos da Mega Sena // var quantity = SimpleCombination(60, 6); // // Simples de fazer, mas com alta complexidade! // Experimente calcular algo como SimpleCombination(60, 15) ;P int SimpleCombination(int n, int p) { if((n == 0) || (p == 0) || (p == n)) return 1; return SimpleCombination(n - 1, p - 1) + SimpleCombination(n - 1, p); }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // Solução para o Triângulo de Pascal de forma otimizada // // 60 choose 15 = 53194089192720 (0ms) // 60 choose 30 = 118264581564861424 (0ms) // public long SimpleCombination(int n, int p) { return SimpleCombination(n, p, new long[n + 1, p + 1]); } public long SimpleCombination(int n, int p, long[,] dp) { if ((n == 0) || (p == 0) || (n == p)) return 1; if (dp[n, p] == 0) dp[n, p] = SimpleCombination(n - 1, p - 1, dp) + SimpleCombination(n - 1, p, dp); return dp[n, p]; }