三色三角形 [英] Three colors triangles
问题描述
我正在尝试为该问题编写代码:
(来源:
为了避免整数溢出，我们将需要应用以下
但是我们如何计算
...没有直接计算系数本身(这可能导致溢出)?
由于3是质数，因此可以使用
...，其中
n_i，m_i是在 base-3 中n，m的i个数字em>.通过整数除法可以轻松地转换为base-3:
//将数字转换为以3为底的数字//并返回数字unsigned conv_base_3(unsigned n，unsigned max，unsigned * out){无符号i = 0;而(i< max& n> 0){out [i] = n％3;n/= 3;i ++;}返回我}请注意，由于
n_i，m_i始终在[0，2]范围内(因为它们是以3为基数的数字)，因此C(n_i，m_i)非常容易计算://计算n< n的二项式系数.3unsigned binom_max_2(unsigned n，unsigned k){如果(n ＜k)返回0;开关(n){案例0:情况1:返回1;情况2:返回1 +(k == 1);//不应该发生默认:返回0;}}现在是定理本身:
//p = 3的卢卡斯定理无符号lucas_3(unsigned len_n，const unsigned * dig_n，无符号len_k，const无符号* dig_k){//使用积乘积规则://prod [i]％3 =((prod [i-1]％3)* value [i])未签名的prod = 1;for(unsigned i = 0; i< len_n; i ++){无符号n_i = dig_n [i];unsigned k_i =(i< len_k)?dig_k [i]:0;prod =(prod * binom_max_2(n_i，k_i))％3;}返回产品％3;}字符转换:
//从012转换为RGBchar int_2_char(int i){切换(i){情况0:返回'R'；情况1:返回"G"；情况2:返回"B"；//不应该发生默认:返回'\ 0';}}//从RGB转换为012未签名的char_2_int(char c){开关(c){情况'R':返回0;情况'G':返回1;情况'B':返回2;//不应该发生默认:返回3;}}最后，三角算法:
//问题约束表明n< = 10 ** 5//以3为基数的最大位数#define MAX_N_LOG_3 11//主要算法功能字符三角形(const char *输入){无符号和= 0;const int n = strlen(input);//计算n-1的数字无符号dig_n [MAX_N_LOG_3];无符号len_n = conv_base_3(n-1，MAX_N_LOG_3，dig_n);for(无符号km1 = 0; km1< n; km1 ++){//计算k-1的位数无符号dig_k [MAX_N_LOG_3];无符号len_k = conv_base_3(km1，MAX_N_LOG_3，dig_k);//计算C(n-1，k-1)mod 3无符号Cnk_mod3 = lucas_3(len_n，dig_n，len_k，dig_k);//使用取模规则添加sum =(sum + Cnk_mod3 * char_2_int(input [km1]))％3;}//(-1)**(n-1)的值//(不需要pow；只需要知道n是奇数还是偶数)整数符号=(n％2)* 2-1;//对于负数，必须解决差异//在C的％运算符和数学mod之间int sum_mod3 =(3 +(符号*(int)(总和％3))％3;返回int_2_char(sum_mod3);}上面的代码通过了所有测试；请注意，它是为了清晰而不是性能而写的.
那么，为什么这段代码能够在指定的时间内通过所有测试，而基于表的简单方法却没有呢?由于其时间复杂度 :
基于表的方法处理三角形的所有级别，即
O(n ^ 2)(请参阅https://www.codewars.com/kata/insane-coloured-triangles/train/c)A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.
For example, different possibilities are:
Colour here: G G B G R G B R Becomes colour here: G R B G With a bigger example: R R G B R G B B R B R G B R B G G B R G G G R G B G B B R R B G R R B GYou will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given
'RRGBRGBB', and you should return'G'.Constraints:
1 <= length(row) <= 10 ** 5The input string will only contain the uppercase letters '
B', 'G' or 'R'.The exact number of test cases will be as follows:
100 tests of 100 <= length(row) <= 1000 100 tests of 1000 <= length(row) <= 10000 100 tests of 10000 <= length(row) <= 100000Examples:
triangle('B') == 'B' triangle('GB') == 'R' triangle('RRR') == 'R' triangle('RGBG') == 'B' triangle('RBRGBRB') == 'G' triangle('RBRGBRBGGRRRBGBBBGG') == 'G'
So I have made this code and it works for all the sample tastes but when it comes for length of row > 25 it fails due my factorial function,and the length in some cases is up to 100,000, so any suggestion to fix this problem at least any mathematic formula that can solve the problem or a small hint.
by the way I have made this code after I found a mathematic way to solve the problem in this site :
https://math.stackexchange.com/questions/2257158/three-color-triangle-challenge
long long factorial(long long num)
{
long long fact = num;
if (fact == 0)
fact = 1;
while (num > 1)
{
num--;
fact *= num;
}
return (fact);
}
long long combination(long long n, long long k, long long fact_n)
{
long long fact_k = factorial(k);
long long comb = ( fact_n / (fact_k * factorial(n - k)) );
return (comb);
}
char triangle(const char *row)
{
long long len = strlen(row);
long long n = len - 1;
long long k = 0;
int sign = pow(-1,n);
long long sum = 0;
char *result = "RGB";
int a;
long long fact_n = factorial(n);
while (k < len) //This while calculate Segma (∑).
{
if (row[k] == 'R')
a = 0;
else if (row[k] == 'G')
a = 1;
else if (row[k] == 'B')
a = 2;
if (a != 0)
sum = sum + (combination(n,k,fact_n) * a);
k++;
}
sum = sign * (sum % 3);
if (sum == -1 || sum == -2)
sum += 3;
return (result[sum]);
}
I will assume that the formula in the link you provided is correct:
In order to avoid integer overflow, we will need to apply these modulo arithmetic rules:
(a * b) mod c = ((a mod c) * (b mod c)) mod c
(a ± b) mod c = ((a mod c) ± (b mod c)) mod c
Applying them to the formula:
But how do we calculate
... without directly calculating the coefficient itself (which can cause overflow)?
Since 3 is a prime number, this can be accomplished with Lucas's theorem:
... where n_i, m_i are the i-th digits of n, m in base-3.
Conversion to base-3 is easy with integer division:
// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
unsigned i = 0;
while (i < max && n > 0)
{
out[i] = n % 3;
n /= 3;
i++;
}
return i;
}
Note that since n_i, m_i are always in the range [0, 2] (because they are base-3 digits), C(n_i, m_i) are very easy to calculate:
// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
if (n < k)
return 0;
switch (n)
{
case 0:
case 1:
return 1;
case 2:
return 1 + (k == 1);
// shouldn't happen
default:
return 0;
}
}
And now the theorem itself:
// Lucas's theorem for p = 3
unsigned lucas_3(
unsigned len_n, const unsigned * dig_n,
unsigned len_k, const unsigned * dig_k
)
{
// use modulo product rule:
// prod[i] % 3 = ((prod[i - 1] % 3) * value[i])
unsigned prod = 1;
for (unsigned i = 0; i < len_n; i++) {
unsigned n_i = dig_n[i];
unsigned k_i = (i < len_k) ? dig_k[i] : 0;
prod = (prod * binom_max_2(n_i, k_i)) % 3;
}
return prod % 3;
}
Character conversion:
// convert from 012 to RGB
char int_2_char(int i)
{
switch (i) {
case 0: return 'R';
case 1: return 'G';
case 2: return 'B';
// shouldn't happen
default:
return '\0';
}
}
// convert from RGB to 012
unsigned char_2_int(char c)
{
switch (c) {
case 'R': return 0;
case 'G': return 1;
case 'B': return 2;
// shouldn't happen
default:
return 3;
}
}
Finally, the triangle algorithm:
// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11
// main algorithm function
char triangle(const char * input)
{
unsigned sum = 0;
const int n = strlen(input);
// calculate digits of n - 1
unsigned dig_n[MAX_N_LOG_3];
unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);
for (unsigned km1 = 0; km1 < n; km1++)
{
// calculate digits of k - 1
unsigned dig_k[MAX_N_LOG_3];
unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);
// calculate C(n - 1, k - 1) mod 3
unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);
// add using the modulo rule
sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
}
// value of (-1) ** (n - 1)
// (no need for pow; just need to know if n is odd or even)
int sign = (n % 2) * 2 - 1;
// for negative numbers, must resolve the difference
// between C's % operator and mathematical mod
int sum_mod3 = (3 + (sign * (int)(sum % 3)) % 3;
return int_2_char(sum_mod3);
}
The above code passes all tests; note that it was written in favor of clarity, not performance.
So why was this code able to pass all tests in the allocated time, whereas the simple table-based approach wasn't? Because of its time complexity:
The table-based approach processes all levels of the triangle, which is
O(n^2)(see Triangle Numbers).Of course, using Lucas's algorithm, only the top level has to be processed; however the algorithm itself is
O(log n), because it loops through every digit ofn(regardless of the base). The overall complexity isO(n log n), which still represents a significant improvement.
这篇关于三色三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
